通过具有特殊顶点的图进行寻路

Question

嘿嘿！

所以我得到了这个有向 and/or 无向图，其中包含一堆顶点和边。在这个图中有一个起始顶点和一个结束顶点。还有一个红色的顶点子集（这个子集可以包括开始和结束顶点）。此外，任何一对顶点之间的边不能超过一条。

我要做的就是找到：

A) 不经过红色顶点的最短路径

B)如果有路径至少经过一个红色顶点

C) 红色顶点数量最多的路径

D) 红色顶点数量最少的路径

对于 A，我使用忽略红色分支的广度优先搜索。对于 B，我只是通过对图进行深度优先搜索来暴力破解它。对于 C 和 D，我使用动态规划，记住我在所有路径中找到的红色顶点的数量，使用与 B 中相同的 DFS。

我对所有解决方案都比较满意，如果有任何建议，我将不胜感激！谢谢！！

Answer 1

For A I use a breadth first search ignoring red branches

A) 是典型的寻路问题，发生在不包含红色边的子图中。所以你的解决方案很好（如果你能想出一个，可以用启发式方法改进，然后使用 A*）

For B I simply brute force it with a depth first search of the graph

事情是这样的。每条最优路径 A->C 都可以在任意中间点 B 处拆分。最佳路径的一个不错属性是每个子路径都是最佳的。所以 A->B 和 B->C 是最优的。

这意味着如果你知道你必须从一些start到一些end 通过中间人红色顶点，您可以执行以下操作：

从起始顶点执行 BFS
从端顶点向后执行 BFS（如果你的边是定向的——正如我所想的——你必须在此处将它们倒过来）

交替扩展两个 BFS，使它们的 'edge'（或所谓的开放列表）到各自起点的距离相同。

停止时间：

一个 BFS 命中另一个遇到的红色顶点（或在 'closed' 列表中）。在这种情况下，每个 BFS 都可以构造到该公共顶点的最佳路径。缝合两条半路径，您的最佳路径至少有一个红色顶点。
一个 BFS 卡住（'open' 列表为空）。这种情况，无解。

C) The path with the greatest amount of red vertices

这是一道组合题。我要做的第一件事是制作 [开始节点 + 红色节点 + 结束节点] 的可达性矩阵，其中：

reachability[i, j] = 1 iff there is a path from node i to node j

要计算此矩阵，只需从起始节点和每个红色节点开始执行一次 BFS 搜索。如果BFS到达红色节点，则在对应的line/column.

中放一个1

这将抽象出图的潜在复杂性，并使组合搜索的速度提高一个数量级。

现在的问题是 longest path problem 通过连接矩阵。动态规划确实是可行的方法。

D) The path with the fewest amount of red vertices

简单地执行 Dijkstra 搜索，但在对 'open' 列表中的节点进行排序时使用以下指标：

dist(start, a) < dist(start, b) if:
    numRedNodesInPath(start -> a) < numRedNodesInPath(start -> b)
    OR (
      numRedNodesInPath(start -> a) == numRedNodesInPath(start -> b)
      AND
      numNodesInPath(start -> a) < numNodesInPath(start -> a)
    )

为此，当发现新顶点时，您必须将通向它们的路径（好吧，只是路径中的节点的 nb，以及红色节点的 nb，分别）存储在要获取的专用地图。我提到这个是因为通常路径的长度被隐式存储为顶点在数组中的位置。你必须在你的情况下明确地执行它。

关于长度优化的注意事项：

即使你说你不关心问题 A) 之外的长度最优性，我提供的算法将产生最短长度的解决方案。我相信在很多情况下（比如在 D 中）它可以帮助 Dijkstra 更好地收敛。

通过具有特殊顶点的图进行寻路

Pathfinding through graph with special vertices

path-finding