寻找无重访图遍历路径的优化策略（所有顶点）
Optimization strategies for finding a no re-visit graph traversal path (all vertices)
为了重振我有些生疏的编程技能，我正在尝试解决我 运行 遇到的这个图遍历问题。
我想找到一条访问 10x10 网格上所有坐标（顶点）的路径。有一些移动限制，例如只能沿任一方向移动 3 步（x+/-3 或 y+/-3）或沿对角线移动 2 步（x+/-2 和 y+/-2）。据我了解，这些限制并不重要，因为它仍然只是一个带有顶点和边的图，我可以在我的解决方案中很容易地对其进行建模。
到目前为止，我已经能够使用 "simple" DFS 策略解决 6x6 网格的这个问题（至少我认为那是我产生的:)。但是，由于我的算法的 O(n) 有点废话，所以我 运行 会遇到性能问题。 7x7 在我的电脑上大约需要 45 分钟，所以 10x10 就不用管了。
我发现 5x5 的网格总是可以解决的，所以我想一个可行的策略是将 10x10 分成 4x5x5。但这感觉不是一个合适的解决方案，即使它可以解决边长为 5 的倍数的网格，我仍然无法解决 8x8 和 11x11 等问题。
所以我的问题是可以应用哪些策略来优化这个特定问题？
您的问题是 Hamiltonian path problem，它对于任意图是 NP 完全的。这意味着没有已知的有效算法，因此尝试为任意图解决这个问题将是徒劳的。
相反，使用您在 网格 上求解的事实。您可以简单地逐行进行，在末端转身。
如果您在网格上可以做的动作有限，您还可以查看 knight's tour 文献。
为了重振我有些生疏的编程技能，我正在尝试解决我 运行 遇到的这个图遍历问题。
我想找到一条访问 10x10 网格上所有坐标（顶点）的路径。有一些移动限制，例如只能沿任一方向移动 3 步（x+/-3 或 y+/-3）或沿对角线移动 2 步（x+/-2 和 y+/-2）。据我了解，这些限制并不重要，因为它仍然只是一个带有顶点和边的图，我可以在我的解决方案中很容易地对其进行建模。
到目前为止，我已经能够使用 "simple" DFS 策略解决 6x6 网格的这个问题（至少我认为那是我产生的:)。但是，由于我的算法的 O(n) 有点废话，所以我 运行 会遇到性能问题。 7x7 在我的电脑上大约需要 45 分钟，所以 10x10 就不用管了。
我发现 5x5 的网格总是可以解决的，所以我想一个可行的策略是将 10x10 分成 4x5x5。但这感觉不是一个合适的解决方案，即使它可以解决边长为 5 的倍数的网格，我仍然无法解决 8x8 和 11x11 等问题。
所以我的问题是可以应用哪些策略来优化这个特定问题？
您的问题是 Hamiltonian path problem，它对于任意图是 NP 完全的。这意味着没有已知的有效算法，因此尝试为任意图解决这个问题将是徒劳的。
相反，使用您在 网格 上求解的事实。您可以简单地逐行进行，在末端转身。
如果您在网格上可以做的动作有限，您还可以查看 knight's tour 文献。