图如何搜索 return 路径？

Question

我最近在学习图搜索和树搜索，我看到很多例子提到“xxx图搜索的路径return是......”但是，图搜索是一种遍历方法，怎么可能return一条路呢？

我们知道在树搜索中，每个节点对应一条特定的路径，通过访问一个节点，我们知道对应的路径。我对树搜索很熟悉，但是，在图形搜索中，目的是访问目的地，而不是找到到达目的地的路径。那么，我们如何定义一条由图搜索return搜索的路径？

例如下图。

Graph
       B
      / \
     /   \
Start     Destination
     \   /
      \ /
       C

当我们开始做BFS时，访问顺序是Start-B-C-Destination或Start-C-B-Destination。那么， returned 路径应该是什么？如果我们使用队列，我们可以说我们在访问 B（或 C）时将 Destination 入队，因此 returned 路径是 Start-B-Destination（或 Start-C-Destination), 那么下图呢？

Graph
       B
      / \
     /   \
Start-----D-----Destination
     \   /
      \ /
       C

很明显，D在访问Start时就入队了，所以只有可能的路径应该是Start-D-Destination?

A*搜索问题较多。如果一个节点不是从最短路径访问的（由于启发式函数较差），那么最终的 returned 路径应该是什么？比如下图中，访问顺序是Start-B-D-C-Destination，那么returned的路径应该是什么呢？ Start-B-D-Destination 还是 Start-C-D-Destination？当B处于边缘时，我们访问了D，但是，当我们计算从Start到D的成本时，我们正在计算Start-C-D并且成本应该是 2 而不是 3。

Graph
        B
       / \
      1   2
     /     \
Start       D--5--Destination
     \     /
      1   1
       \ /
        C

h(B) = 2, h(C) = 4, h(D) = 1

我认为所有这些问题都是因为图搜索的目的不是寻找路径，图搜索会导致在选择最终路径中应包含哪个节点时产生歧义。

感谢您的耐心等待，如果有人能给我答复，我将不胜感激。

Answer 1

我会用你的例子：

        B
       / \
      1   2
     /     \
Start       D--5--Destination
     \     /
      1   1
       \ /
        C

请注意，纯粹的广度优先搜索不会关注边权重（或 成本）。 在这种情况下，将它带到目的地的第一条路径可能是 Start->B->D->Destination.

它给每一个它访问过的节点都打上一个boolean flag，表示该节点已经访问过，这样就不会再追究了Start->B->Start->C->Start->...为了记住成功的路径，我们必须存储一点某处的更多信息。一种简单的方法是标记每个节点，不仅仅是使用 visited 标志，而是使用对 访问它的节点的引用。 所以如果访问顺序是 Start, B, C, D, Destination，图形将如下所示：

        B(Start)
       / \
      1   2
     /     \
Start       D(B)--5--Destination(D)
     \     /
      1   1
       \ /
        C(Start)

那我们可以原路返回。我们是如何到达 Destination 的？来自 D。我们是如何到达 D 的？来自 B。我们是如何到达 B 的？来自 Start.

广度优先搜索遵循队列中的第一条边，并找到最短路径（在边数最少的意义上）。如果我们想要最轻的 (cheapest) 路径，我们修改搜索以跟踪成本到这个节点，并沿着到达新节点的边节点最便宜。（这是 Dijkstra 算法的一个版本。）然后在这种情况下访问顺序将相同，但我们将从 C 而不是 B 访问 D，并获取路径Start->C->D->Destination.

用A*，用h(B) = 2, h(C) = 4, h(D) = 1，访问顺序为Start, B, D, C, D, Destination，路径为Start->C->D->Destination .

Answer 2

对于 BFS，有两个选项：

当你将一个节点加入队列时，标记你来自哪个邻居。然后在最后，最佳路径上的每个节点都会有一个 link 到路径上的“前一个”节点，因此您可以直接从 Destination 回溯到 Start 以找到路径。
当您将一个节点加入队列时，请记下到该节点的最佳路径，即到其邻居的最佳路径加上您采用的边。

选项 1 是通常采用的方法，因为它的性能更高。

对于 Dijkstra 的（加权图的 BFS），也是如此，只是当你将一个节点加入队列并注意你来自哪个邻居时，你不一定找到最好的到该节点的路径。 如果以后遇到来自不同邻居的相同节点，则需要比较两条路径的总距离，并选择较短的路径作为“前一个”节点。

这是在 pseudocode on Wikipedia

的第 18-20 行中完成的

18  if alt < dist[v]:              
19    dist[v] ← alt
20    prev[v] ← u

一旦你扩展节点（将其从优先级队列中删除），你保证找到了最佳路径节点。

对于A*，情况与Dijkstra的如果启发式是consistent. However, if the heuristic is only admissible，那么你不保证有当你第一次展开它时找到了到一个节点的最佳路径。在这种情况下，您可能需要对同一个节点进行多次入队和扩容。

出于这个原因，使用具有非一致性启发式的 A* 实际上并不常见。

图如何搜索 return 路径？

How can graph search return a path?

search

graph

path

a-star

breadth-first-search