Cost-Algebraic Heuristic Search
Cost-Algebraic Heuristic Search
复制标题
成本代数启发式搜索
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Alberto Lluch
中科院分区：
文献类型：
--
作者：
S. Edelkamp;S. Jabbar;Alberto Lluch
启发式搜索被用来有效地解决赋权图中的单节点最短路径问题。然而，在实践中，人们不仅对寻找一条最短的路径感兴趣，而且根据一定的成本概念，也对寻找一条最优路径感兴趣。我们提出了一种代数形式，它捕获了许多成本概念，如典型的服务质量属性。因此，我们推广了流行的启发式搜索算法A*。用于解决最优路径问题。本文回答了人工智能搜索的一个基本问题，即一般的代价概念、启发式搜索算法可以应用于什么。我们证明了算法的正确性，并给出了实验结果，验证了该方法的可行性。
Heuristic search is used to efficiently solve the single-node shortest path problem in weighted graphs. In practice, however, one is not only interested in finding a short path, but an optimal path, according to a certain cost notion. We propose an algebraic formalism that captures many cost notions, like typical Quality of Service attributes. We thus generalize A*, the popular heuristic search algorithm. for solving optimal-path problem. The paper provides an answer to a fundamental question for AI search, namely to which general notion of cost, heuristic search algorithms can be applied. We proof correctness of the algorithms and provide experimental results that validate the feasibility of the approach.