Heuristic search for target-value path problem

Abstract

In this paper, we introduce a new class of search problems in which the objective is to find a path whose total cost is as close as possible to a target cost, called the ideal cost. As a result, we refer to these problems as ideal-cost path problems, which do not fit well with any of the existing optimization criteria used with A. We show that, with appropriate extensions, A can handle this new type of cost function. It is worth noting that the classic shortest (or least-cost) path problems can be formalized as ideal-cost path problems for which the cost ideal is zero. Thus, this new class contains the traditional shortest-path problems as special cases.