algorithm - 可以在未加权的图中简化 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) .