algorithm - 查找瓷砖网格中两点之间长度为 n 的所有路径

Question

我有一个基于图 block 的二维 map ，其中有两个点彼此相邻。我想找到这两点之间长度为 n 的所有路径(这些点总是相邻的，并且 n 的值总是至少为 3，所以这些永远不会是最短路径)，并有可能排除任何经过的路径通过一个或多个任意定义的点。

我研究过许多寻路算法，但无法想出一种方法来修改它们以返回具有精确长度的所有路径。有人能指出我正确的方向吗？

Answer 1

找到所有路径是不寻常的，因此寻路算法在这里可能帮不了您。您确实在寻找缓慢的穷举搜索。

首先，我将使用 Dijkstra 算法在 n 步内找到结束节点与每个节点之间的最短路径。这稍后会有用，因为它会找到每个节点的最短路径。稍后，我们可以用它来修剪无用的路径。

然后我将开始对网格进行迭代搜索。在每一步，跟踪到达那里所用的路径，称为长度 m。请记住，您将有许多路径(可能是循环路径)到达同一节点。你会想保留所有这些。在每次迭代中，查看当前节点的邻居，并将新路径插入搜索中，这些路径会到达每个可以在 n-m 步内到达端点的邻居。

最终您将用完所有可能到达终点的节点，您可以简单地查看到达终点的所有路径。