可以在未加权的图中简化 A* 搜索吗？

Question

这里介绍一个几乎是A*搜索的算法。本质上它是具有使用 A* 优先级的优先级队列的 BFS。

frontier <- empty priority queue
frontier.insert(start) with priority g(start)+h(start)
while frontier isn't empty
    vertex <- dequeue frontier
    for each undiscovered neighbor of vertex
        neighbor.discovered = true
        neighbor.parent = vertex
        frontier.insert(neighbor) with priority g(neighbor)+h(neighbor)
        if neighbor == goal, stop

此算法缺少处理此事实的 A* 部分：找到的到顶点的第一条路径不一定是到该顶点的最短路径。

很容易举出缺失部分至关重要的例子……对于加权图。对于未加权的图表，我一直无法想出任何图表。

这个更简单的 A* 版本是否可能适用于未加权的图？

Answer 1

不，对于任意 h 函数来说是不正确的。这是一个例子。假设我们有一个包含 7 个顶点和以下未加权边的图：{(1, 2), (2, 3), (3, 4), (4, 6), (2, 5), (5, 6), (6, 7)}。我们可以这样定义h：{0, 0, 0, 0, 2, 1, 0}。起始顶点是1，目标是7. 很容易验证这个启发式函数是可采纳的。但是，如果我们运行这个算法，我们会看到它首先找到的 6 顶点的路径是 (1, 2, 3, 4, 6) 因为 f(4) = 3 + 0 < 2 + 2 = f(5)，而到它的实际最短路径是(1, 2, 5, 6)。

可以在未加权的图中简化 A* 搜索吗？

Can A* search be simplified in an unweighted graph?

algorithm

search

graph

a-star