A Problem Similarity Approach to Devising Heuristics: First Results

Abstract

Here we describe an approach, based upon a notion of problem similarity, that can be used when attempting to devise a heuristic for a given search problem (of a sort represented by graphs). The proposed approach relies on a change in perspective: instead of seeking a heuristic directly for a given problem P1, one seeks instead a problem P2 easier to solve than P1 and related to P1 in a certain way. The next step is to find an algorithm for finding paths in P2, then apply this algorithm in a certain way as a heuristic for P1. In general, the approach is to consider as candidates problems P2 that are “edge subgraphs” or “edge supergraphs” of the given problem P1. As a non–trivial application, we show that a certain restricted form of sorting problem (serving as P2) is an edge supergraph of the 8-puzzle graph (P1). A simple algorithm for solving this sorting problem is evident, and the number of swaps executed in solving an instance thereof is taken as a heuristic estimate of distance between corresponding points in the 8-puzzle graph. Using the A * * This research was sponsored by the Defense Advanced Research Projects Agency (DOD), ARPA Order No 3597, monitored by the Air Force Avionics Laboratory Under Contract F33615-78-C-1551. algorithm, we experimentally compare the performance of this “maxsort” heuristic for the 8-puzzle with others in the literature. Hence we present evidence of a role for exploiting certain similarities among problems to transfer a heuristic from one problem to another, from an “easier” problem to a “harder” one.