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.