Best-First Minimax Search

本文研究了一种基本的问题求解方法——启发式搜索，以及一种重要的启发式搜索算法——最佳优先搜索。提出了一种新的最佳优先搜索算法，该算法的内存需求仅在搜索深度上是线性的，但代价是需要对某些节点进行多次扩展。该算法结构简单，开销小，运行速度快于经典的最佳优先搜索。它消除了最佳优先搜索的内存限制，并开辟了许多新的应用：组合优化问题，实时约束下的最优决策，双人游戏的选择性搜索算法，以及困难约束满足问题。

This research is concerned with a fundamental problem solving method - heuristic search, and an important heuristic search algorithm - the best-first search. A new best-first search algorithm is developed, whose memory requirement is only linear in the search depth, at the cost of expanding some nodes more than once. The algorithm runs faster than classical best-first search due to its simple structure and reduced overhead. It removes the memory limitation of best-first search, and opens up a host of new applications: combinatorial optimization problems, optimal decisions under real-time constraints, selective search algorithms for two-player games, and difficult constraints satisfaction problems.