问寻路:如何有效地检查路径是否可行？

EN

无约束，单机版

在一个没有约束的图上，程序以前从未见过(甚至是以前的一部分)，也不会再看到。你唯一能做的就是广度优先搜索或者深度优先搜索。

如果内存有问题，您可以考虑使用增量深度优先搜索。

您可以考虑在图形上启动多个线程，以沿着不同的分支进行查找。您需要进行协调，以便它们不会重复工作，因为它们有一个并发的共享数据结构，它们都可以安全地检查和写入。使用并发，您可以让一些线程从头到尾进行搜索，而另一些线程则从头到尾进行搜索。

在具有循环的图上，您可能希望将节点标记为已访问，这样就不会执行无限循环。

约束，单机版

想想你的图表和你的目标。

图是密集的还是稀疏的？

是否存在负边权重？负和循环？

它遵循梯形法则吗？

有没有一个最大的距离，超过这个距离你并不关心是否有一条路径？

图是否是非循环的？

这个图是“简单的”吗？

通过一些工作，您也许能够找到一种比dfs更适合您的图形的方法。其他时候，您可以用一种不同的方式构建图形，从而使dfs更快。有时，优势可能来自于在搜索过程中不必存储大量数据。

约束，多用途

如果这是值得的，您可以运行Floyd-Warshall来求解每对节点之间的最短路径。该算法可能需要一些时间，但当您只需在关键部分中查找最短路径时，它可能会更有优势。

您可以通过在图上执行初始dfs来预先求解连接的组件，而不是预先求解最短路径。

如果图表可以更改，但不会有很大的变化，您可以简单地修改预先计算的结果，而不是每次都从头开始。

Last Thoughts

图的大小和复杂性是重要的考虑因素。对于小的、密集连接的图，最好的算法将与大型稀疏图或树的算法不同。

您是否在同一个图上运行多个路径查找？如果是这样的话，您将需要从图中维护一组不相交的连续空间。这可以通过以下方式实时完成：

如果开始节点和目标节点在相同的已知连续空间中、在两个不同的连续空间中、或者在每个路径determination.之前未知，则

1. 维护来自每个不成功的路径确定的连续空间，作为从开始节点开始的完整闭集；
2. 构造一个数据结构，该数据结构能够在计算出的连续空间中有效地搜索连续空间

(2)的确切最佳机制与您的图的性质密切相关，因此我将其留给另一个问题。