A unified approach to problem solving search procedures

摘要

Problem solving search algorithms have found wide use in many areas of computer science and engineering. Applications abound in such diverse areas as game playing, decision analysis, pattern recognition, robotics and theorem proving. Because of the somewhat differing requirements of the various problems in which search algorithms are used, different search procedures have evolved. For example, Alpha-Beta, SSS*, and B* for minimax search; A* and other heuristic search procedures for state space search; AO* for problem reduction search; and various Branch-and-Bound and Dynamic programming procedures for combinatorial optimization problems. Although many of these procedures have been thought to be related to each other, considerable confusion has existed regarding their true nature and their interrelationships. This dissertation presents a general model for discrete optimization problems. Using certain relationships between formal grammars, problem reduction representations, and game trees, it is shown that a large number of search problems in Artificial Intelligence can be formulated in this model. Two general classes of algorithms are discussed, and it is shown how most of the existing search algorithms to solve problems formulated by this model fall into one of the two categories. This approach to formulating and solving discrete optimization problems makes it possible to view most of the procedures mentioned before in a unified manner. It reveals the true nature of these procedures, and clarifies their relationships to each other. The approach also aids in synthesizing new variations as well as generalizations of the existing search procedures.