可以在未加权图中简化 A* 搜索吗? [英] Can A* search be simplified in an unweighted graph?

问题描述

这是一个几乎是 A* 搜索的算法.本质上它是带有使用 A* 优先级的优先级队列的 BFS.

Here's an algorithm that is almost A* search. Essentially it's BFS with a priority queue that uses A* priority.

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* 部分:找到的第一个顶点的路径不一定是到那个顶点的最短路径.

This algorithm is missing the parts of A* that handle this fact: the first path found to a vertex is not necessarily the shortest path to that vertex.

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

It's easy to come up with examples where the missing parts are crucial... for weighted graphs. For unweighted graphs, I haven't been able to come up with any.

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

Is it possible that this simpler version of A* is correct for unweighted graphs?

推荐答案

不，它不适用于任意 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).

No, it is not correct for an arbitrary h function. Here is an example. Let's assume that we have a graph with 7 vertices and the following unweighted edges: {(1, 2), (2, 3), (3, 4), (4, 6), (2, 5), (5, 6), (6, 7)}. We can define h in the following way: {0, 0, 0, 0, 2, 1, 0}. The start vertex is 1, the goal is 7. It is easy to verify that this heuristic function is admissible. However, if we run this algorithm we will see that the path to the 6 vertex that it finds first is (1, 2, 3, 4, 6) because f(4) = 3 + 0 < 2 + 2 = f(5), while the actual shortest path to it is (1, 2, 5, 6).

这篇关于可以在未加权图中简化 A* 搜索吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！