查找网格中 2 个节点之间的所有路径
我试图找到网格中两个节点之间的所有路径，并且该路径必须从头到尾穿过所有节点。 示例（开始 = 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 语言完成）。
I'm trying to find all the paths between 2 nodes in a grid, and the path has to go through all the node from start to end.
Example (Start = S, End = E)
0 0 0
0 S 0
0 0 E
The answer for the above is 2 paths: (ignore the '.''s)
0-0-0
|.......|
0 S-0
|
0-0-E
0-0-0
|......|
0 S 0
|...|...|
0-0 E
I thought of using recursing, but gave that up due to the high overhead of each call...and decided to go with an iterative approach using a stack. (kind of like recursing but not...fixed memory overhead).
The solution works great for grids of size (4x7), but tried it on an 8x8 grid...and it didn't finish in 4 hours...which sort of makes sense since the total number of possibilities is around 3**62 (approx), as each node that is not on the edge has 3 possible ways of traversal...and hence that solution fails.
I thought of splitting the 8x8 grid into 2, using a vertical and horizontal split...but this would lead to finding less than ideal paths.
Is there something that I'm missing????
Can something be done to make it go faster?
I will post the solution that I have tomorrow (done in C).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
嗯，有一个线性时间算法，用于查找任意两个给定顶点之间的最长路径矩形网格图，这似乎正是您正在寻找的。
Well, there is a linear-time algorithm for finding a longest path between any two given vertices in a rectangular grid graph, which seems to be exactly what you're looking for.
不，您不会错过任何事情，也没有什么可以做得更快。
这是NP-Hard 的最长路径问题。
Nope, you do not miss anything and nothing can be done faster.
This is the Longest Path Problem which is NP-Hard.
看一下最短路径问题，它应该可以帮助您开始解决这个问题。 Bellmann-Ford 或 Dijkstra 算法值得尝试。如果您的网格具有一些可以利用的属性，您也许能够提高这些效率。
Have a look at the shortest paths problem it should get you started on this. The Bellmann-Ford or Dijkstra's algorithm are worth trying. You might be able to improve on the efficiency of those if your grid has some properties you can exploit.