A new toolkit for non-admissible heuristic search

Abstract

A collection of tools for finding good solutions to cost-minimization problems by means of nonadmissible heuristic search is discussed. The origin of these tools lies in the assumption that many biased heuristics are orderly. Their usefulness will depend upon how well the orderliness assumptions are realized. Therefore, domain-dependent knowledge must be applied in selecting a good search strategy. This work was initially inspired by a real problem in mainframe capacity planning for computing centers. Since that problem set is too complex to be described adequately, a much simpler problem set, called Quadratic Sort, which is used to illustrate, discuss, and test some of the node-selection and tree-pruning methods is created. Most of the result presented are not demonstrably optimal. The primary requirements for using search effectively to solve any set of optimization problems are therefore given, as follows: (1) adequately define the problem set, (2) have good representations of the problem states and the search tree nodes, (3) adequately define the state transformation operators, and find as good a heuristic as circumstances permit. When these requirements have been met, it may be found that optimization is possible and worthwhile. If this is not the case, some optimization methods should be considered.