Android屏幕锁定模式的最长路径

Question

假设我们有9点。每个人只能被访问一次。路径，例如从左上角到右下角，也是允许的。任何人都可以提供算法来计算屏幕锁定模式的最长路径？

Answer 1

您需要首先提供距离度量。
让我们假设如下：
- 水平或垂直移动可以长1个一步或2个两步。
- 在对角线方向上，一个步长（2的平方根，毕达哥拉斯定理）或2.83两步（8的平方根）的长度为1.41。
样在国际象棋骑士，你将有长度2.24（5平方根）

所以，现在你需要找到刚才的这种可能的步骤的最大总和。 如果您使用上面提到的“最佳首次搜索”，这将会很麻烦，因为最长的路径不会选择首选最佳选项。
对于下图：
一种选择是519467382，这将有长约17.7
所以也许它是安全的尝试如前所述计算所有的选择，但你也可以保持在请注意，由于对称性，您需要计算仅用于开始节点1,2和5的长度。其他节点会给出相同的结果，因此不需要进行计算。...

Answer 2

它类似于旅行商问题（TSP），但不是您寻找最长路径的最短路径，而且路径未关闭。

对于9分的情况，我不会害怕尝试所有可能的路径，因为它们只有9! = 362880。而这个数字可能会减少，因为3×3的规则网格高度对称。

另一种方法（因为路径没有关闭）可能会从一个节点做到best-first search，“最好”是迄今为止路径最长的节点。你会从每个节点上记下它们最长的路径。但这只是一个快速的想法，我没有证据证明这实际上可行。

Answer 3

最长的路径是567 348 192 这是大约18.428

至少有8个这样的模式，另外一个是567 381 932（遍历长度18.428）。围绕这些模式放置镜像，并从一个这样的模式中获得4个模式。