找出瓦片网格中两点之间长度为n的所有路径

Question

我有一个2D的基于贴图的地图，上面有两个相邻的点。我想找到这两个点之间的所有长度为n的路径(这些点总是相邻的，n的值总是至少为3，所以这些永远不会是最短路径)，有可能排除任何经过一个或多个任意定义点的路径。

我已经研究了许多寻径算法，但我很难想出一种方法来修改它们以返回具有精确长度的所有路径。有人能给我指个正确的方向吗?

Answer 1

查找所有路径是不寻常的，因此寻路算法在这里可能无法帮助您。你真的在寻找一个缓慢的穷举搜索。

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

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

最终你会用尽所有可能到达端点的节点，你可以简单地查看所有到达端点的路径

Answer 2

简单地进行穷举搜索。你可以修剪一些无论如何都不会到达目的地的树枝:

search(from, to, n):
    if from is outside boundaries: return
    if distance(from, to) > n: return
    if n == 0:
        if from == to:
            do something with your path
        return
    search(left of from,  to, n-1)
    search(right of from, to, n-1)
    search(up of from,    to, n-1)
    search(down  of from, to, n-1)

如果您的路径不需要有重复点，只需像通常使用DFS那样跟踪即可，但请记住在退出节点时取消已访问标记(以便您可以在另一条路径中再次访问它)。