algorithm - 可以在未加权的图中简化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*是否可能适用于未加权的图？

最佳答案

不，对于任意的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)。