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個模式。