algorithm - 找到所有路径的复杂度是多少

Question

有一张地图，由六边形区域组成。在这张地图上，我们有一个棋子。他不能两次访问任何位置。无需重复即可找到所有可能路径的算法的复杂性是多少？（基本上找到所有可能的路径，不必遍历所有领域，因为棋子可能会自己跑到角落里，只要能移动，他就会走）。

Answer 1

首先，给定n 个字段的映射和给定的起始位置（即专门为配置和起始位置设计的算法）的答案范围：从 O(n)（如果可以存在孤立的十六进制，则为 O(1)）到 O(e ^n)。

我的意思是，如果地图是十六进制线，那么如果起始位置在行尾，则只有 1 条路径，否则只有 2 条路径，无论 n 的值是多少。如果地图是一个六边形圆圈，则始终有 1 条路径。另一方面，如果地图的重要部分是连接的六边形的“正方形”，那么路径的数量会呈指数增长，并且找到所有路径的算法不会比这更快（即使路径在某种程度上很明显，我们仍然必须输出它们）。

如果地图的配置和起始位置也是算法的输入，那么问题就变得更加困难了：理论上，算法可以先尝试“分析”地图，看它是否足够“具体”（例如，地图可以有重复的模式只能分析一次）并且比奥斯瓦尔德的算法更好地在这样的地图上进行。

对于由连接的六边形组成的“平均”地图，路径的数量似乎是指数的（我没有严格的证明），所以算法的时间复杂度也是指数的（不能更好，奥斯瓦尔德的算法达到了这个限制）。平均随机地图路径的确切指数值很难评估，可能不需要。

Answer 2

复杂度为 O(5 ⁿ )。

• 除了第一个字段，每个字段最多可以进行 5 次移动。
• 如果 pawn 被移动到一个字段，它会创建一个唯一的路径（不需要检查路径是否已经被访问过）。
• 跟踪可以从任何给定字段访问哪些字段可以在 O(1) 中完成。

根据地图的形状，可能存在下限。

Answer 3

If I understood the problem correctly, on a random map, the complexity of this algorithm will be O(x) where x is the answer for this map.