Characterizing Search Spaces
Roy Rada · Maryland Shared Open Access Repository (USMAI Consortium) · 2020
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.