我有一个非常简单的寻路任务 - 在8x8网格上玩的棋盘游戏，每个方块都可以通过 . 我正在寻找的是一种算法，它将为我提供从一些方形A到方形B的最佳n路径（假设有任何方法） .
我一直在看A *，但就我所知，没有明确的方法来扩展它以找到多条路径 .
所以，重要的是它提供的路径实际上是最短的n条路径，它不会错过任何路径 . 效率也很重要 . 任何人都可以建议一个合适的算法，或指出我正确的方向？
对于像这样的大多数情况，Dijkstra是一个很好的算法，但是由于你是8x8网格，我将假设每个单元格之间的所有距离都是相等和静态的 . 在这种情况下，BFS（广度优先搜索）应该很适合你 .
鉴于电路板尺寸较小，广度优先的详尽搜索是您应该考虑的事情 . 8 x 8表示仅64个方格，x8移动（如果不允许对角线，则为4个），总搜索量非常小 .
Dijkstra很适合找到最短的路径 . 要找到第二个，第三个......第n个最短路径，您需要使用Dijksta算法的扩展 . 一旦找到来自N1，N2，N3 ... Nx的最短路径，克隆该路径上的所有中间节点以创建节点N2'到Nx-1' . 克隆最短路径上的所有进入边缘，除了（N1，N2'）和去除边缘（Nx-1，Nx） . 将所有边缘放宽到克隆路径上的节点，这些节点现在代表了从上一次迭代到达最短路径上的节点的第二快方式 .
查看k-shortest paths，这是一个包含一些参考资料的开源实现 .
4 回答
对于像这样的大多数情况，Dijkstra是一个很好的算法，但是由于你是8x8网格，我将假设每个单元格之间的所有距离都是相等和静态的 . 在这种情况下，BFS（广度优先搜索）应该很适合你 .
鉴于电路板尺寸较小，广度优先的详尽搜索是您应该考虑的事情 . 8 x 8表示仅64个方格，x8移动（如果不允许对角线，则为4个），总搜索量非常小 .
Dijkstra很适合找到最短的路径 . 要找到第二个，第三个......第n个最短路径，您需要使用Dijksta算法的扩展 . 一旦找到来自N1，N2，N3 ... Nx的最短路径，克隆该路径上的所有中间节点以创建节点N2'到Nx-1' . 克隆最短路径上的所有进入边缘，除了（N1，N2'）和去除边缘（Nx-1，Nx） . 将所有边缘放宽到克隆路径上的节点，这些节点现在代表了从上一次迭代到达最短路径上的节点的第二快方式 .
查看k-shortest paths，这是一个包含一些参考资料的开源实现 .