我试图找到网格中两个节点之间的所有路径，并且该路径必须从头到尾穿过所有节点。 示例(开始 = S，结束 = E)
0 0 0
0 S 0
0 0 E
上述答案是 2 条路径:(忽略“.”)
0-0-0
|.......|
0 S-0
|
0-0-E
0-0-0
|......|
0 S 0
|...|...|
0-0 E
我想过使用递归，但由于每次调用的开销很高而放弃了......并决定采用使用堆栈的迭代方法。 (有点像递归，但不是......固定的内存开销)。 该解决方案对于大小 (4x7) 的网格非常有效，但在 8x8 网格上尝试过......并且它没有在 4 小时内完成......这有点有意义，因为可能性的总数约为 3** 62(大约)，因为每个不在边缘的节点都有 3 种可能的遍历方式......因此该解决方案失败。
我想过将 8x8 网格分成 2 个，使用垂直和水平分割......但这会导致找到不太理想的路径。
我是不是漏掉了什么？？？ 能做点什么让它跑得更快吗？ 我将在明天发布我的解决方案(用 C 语言完成)。
最佳答案
看看最短路径问题，它应该可以帮助您开始解决这个问题。 Bellmann-Ford 或 Dijkstra 算法值得尝试。如果您的网格具有一些可以利用的属性，您也许能够提高这些效率。
关于c - 查找网格中 2 个节点之间的所有路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4012868/