Characterizing Search Spaces
No Thumbnail Available
Links to Files
Permanent Link
Collections
Author/Creator
Author/Creator ORCID
Date
Type of Work
Department
Program
Citation of Original Publication
Roy Rada, Characterizing Search Spaces, https://www.ijcai.org/Proceedings/83-2/Papers/045.pdf
Rights
This item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.
Subjects
Abstract
A heuristic is good on a search space to the extent that it llows 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 heuristic on a given search space. The measure sheds light on characteristics of the Traveling Salesman Problem that make it computationally more difficult to solve than the Minimum Spanning-Tree Problem.