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 Pl, 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 Pl. In general, the approach is to consider as candidates problems P2 that are "edge subgraphs" or "edge supergraphs" of the given problem Pl. As a non-tr i vial application, we show that a certain restricted form of sorting problem (serving Ill> 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 solvi,,g an Instance thereof is taken as a heuristic estimate of distance between corresponding points in the 8-puzzle graph. Using the At algorithm, we experimentally compare the performa.,ce of this "maxsort" heuristic for the 8-puzzle with others in the literature. Hence we present evidence of a role for e :<ploitlng certain similarities among problems to transfer a heuristic from one problem to another, from an "easier• problem to a "harder" one.