A Formal Basis for the Heuristic Determination of Minimum Cost Paths
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
复制标题
DOI：
--
复制
发表时间：
1967
期刊：
影响因子：
--
通讯作者：
J. E. Falk;R Fletcher;M. J. D. Powell;Peter E Hart;Nils J Nilsson;Bertram Raphael
中科院分区：
文献类型：
--
作者：
J. E. Falk;R Fletcher;M. J. D. Powell;Peter E Hart;Nils J Nilsson;Bertram Raphael
虽然确定通过图的最小成本路径的问题在许多有趣的应用中自然出现，但一直没有基础理论来指导有效搜索过程的发展。此外，目前还没有一个适当的概念框架，可以用来比较迄今提出的各种临时搜索战略。本文介绍了如何启发式信息从问题域可以被纳入一个正式的数学理论图搜索，并证明了一类搜索策略的最优性。
Although the problem of determining the minimum cost path through a graph arises naturally in a number of interesting applications, there has been no underlying theory to guide the development of efficient search procedures. Moreover, there is no adequate conceptual framework within which the various ad hoc search strategies proposed to date can be compared. This paper describes how heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching and demonstrates an optimality property of a class of search strategies .