9

所以我有以下问题:

给定一个 x x y 维度的网格,计算从一个角开始(比如左上角)到另一个角(右下角)结束并通过每个顶点的路径数。

所以我目前的方法只是通过尝试所有可能的路径并计算到达终点并遍历每个节点的路径来强制它。虽然它有效,但它是 O(n^2) 并且非常快地变得令人难以置信的慢。由于路径需要遍历每个顶点,我不确定如何组合地执行此操作。

我查找了更复杂的算法,并且 Hierholzer 计算欧拉路径的算法似乎有些相关但并不完美,因为为此不能多次遍历节点。

事实上,我的程序可以工作,但效果很差,我想让它更有效率。我可以使用更好的算法吗?

编辑感谢到目前为止的答案。澄清一下,二维网格中的所有节点都通过 n/e/s/w 连接

此外,网格不必是正方形

4

3 回答 3

2

你无能为力,因为它是哈密顿路径问题,它是 NP 完全的。

但是,您实际上可能会搜索其他内容并为您尝试解决的问题添加一些限制......

编辑:

正如@JanDvorak 所指出的,您的具体限制是您使用的是方形网格。到目前为止我的发现:

如果x是偶数,则无法遍历从左上角开始到右下角结束的所有顶点。证明:

让我们计算沿轴的定向-1运动,例如向上是,向下是1,向左是-1,向右-1。因此,有 x x x 网格,您的总移动量将是2*x. 在每个顶点(除了最后一个!)您只选择一个方向。因此,如果您需要通过偶数个顶点,那么您的总运动将是偶数,反之亦然。如果x是偶数,则顶点数为奇数,但总运动仍然是偶数=>您找不到任何方法。

于 2013-01-09T23:33:01.170 回答
0

这个学期我在一个主题上处理过这样的问题。我想你可以看看我们这样的元启发式算法:

不过,除非您真的需要改进,否则您可能希望继续使用蛮力;因为它们相当复杂。

于 2013-01-09T23:51:16.367 回答
0

首先,如果 x 是偶数,则有一个简单的奇偶校验参数表明答案始终为零;检查网格并注意左上角和右下角的正方形颜色相同,并且不能同时访问第一个和第 n 2个颜色,因为 n 2是偶数而 1 是奇数。

如果 x 是奇数,我不知道如何计算路径,但请注意总数至少呈指数快速增长:n*n 网格的任何遍历都可以提升为 (n+2) 的两个不同遍历*(n+2) 个网格。沿着第一行向右,沿着第二行向左,沿着第一列向下,沿着第二列向上,然后在剩余的方格上进行 n*n 网格遍历,您可以得到一个;您可以通过以相反的顺序覆盖前两行和列来获得另一个。

这应该告诉您,蛮力解决方案不太可能很好地工作。

于 2013-01-10T00:10:01.710 回答