寻找无重访图遍历路径（所有顶点）的优化策略。

Question

为了让我那有些生疏的编程技能不再受影响，我正在尝试解决我遇到的这个图遍历问题。

我想找到一个路径，它可以访问10x10网格上的所有坐标（顶点）。有一些移动限制，比如只能在任何一个方向上移动3步(x+-3 OR y+-3)或者对角线上移动2步(x+-2 AND y+-2)。根据我的理解，这些限制并不重要，因为它仍然只是一个有顶点和边的图，我可以在我的解决方案中很容易地建模。

我已经到了能够使用 "简单的 "DFS策略解决6x6网格的问题的程度（至少我认为这是我的成果 :)。但如果再大一些，我就会遇到性能问题，因为我的算法的O(n)是个垃圾。7x7在我的电脑上需要45分钟，所以10x10就是算了。

我发现5x5的网格总是可以解决的，所以我想一个可行的策略就是把10x10的网格分成4x5x5。但我觉得这不是一个合适的解决方案，即使它可以解决边长为5的倍数的网格，我仍然无法解决8x8和11x11等问题。

所以我的问题是，对于这个特殊的问题，可以应用什么策略来优化？

Answer 1

你的问题是 汉密尔顿路径问题对于任意图来说，它是NP-完备的。这意味着没有已知的有效算法，所以试图解决任意图的问题将是相当无果的。

相反，你可以利用你要在一个 网格. 你可以简单地逐行走，在两端转圈。

如果你在一个网格上能做的动作有限，你也可以看一看 骑士团 文学。