Heuristically guided search and chromosome matching

摘要

Heuristically guided search is a technique which systematically takes into account information from the problem domain for directing the search. The problem is to find the shortest path in a weighted graph from a start vertex Va to a goal vertex Vz: For every intermediate vertex, an estimate is available of the distance to Vz. If this estimate satisfies a consistency assumption, an algorithm by Hart, Nilsson, and Raphael is guaranteed to find the optimum, looking at the priori minimum number of vertices. In this paper, a version of the algorithm mentioned above is presented which is guaranteed to succeed with the minimum amount of storage. An application of this technique to the chromosome matching problem is then shown. Matching is the last stage of automatic chromosome analysis procedures, and can also solve ambiguities in the classification stage. Some peculiarities of this kind of data suggest the use of a heuristically guided search algorithm instead of the standard Edmonds' algorithm. The method that we obtain in this way is proved to exploit the clustering of chromosome data: A linear-quadratic dependence on the number of chromosomes is obtained for perfectly clustered data. Finally, some experimental results are given.