---
title: "Characterizing Search Spaces"
authors:
  - "Roy Rada"
doi: ""
url: "https://ijcai.org/proceedings/1983/189"
pdf: "https://ijcai.org/proceedings/1983/0189.pdf"
venue: "Proceedings of the Eighth International Joint Conference on Artificial Intelligence"
year: 1983
pages: "780-781"
track: "Planning and Search"
keywords:
---

# Characterizing Search Spaces

Roy Rada

*Proceedings of the Eighth International Joint Conference on Artificial Intelligence*, pages 780-781.

## Abstract

A heuristic is good on a search space to the extent that it allows the prediction of which states are near to the goal. In this paper heuristics are investigated on several different search spaces. A measure is proposed for assessing the predictive accuracy of a given heuri stic on a given search space. Themeasure sheds light on characteristics of the Traveling Salesman Problem that make it computationally mor e difficult to solve than the Minimum Spanning-Tree Problem.