android - Androidの画面ロックパターンの最長パス

Question

9点あるとします。お一人様1回のみご来店いただけます。左上隅から右下隅などのパスも許可されます。画面ロック パターンの最長パスを計算するアルゴリズムを提供できる人はいますか?

Answer 1

最初に距離メトリックを提供する必要があります。
次のように仮定しましょう: -
水平または垂直の移動は、1 歩で 1 または 2 歩で 2 と長い場合があります。
-対角線上では、1 ステップの長さが 1.41 (2 の平方根、ピタゴラスの定理) または 2 ステップ (8 の平方根) で 2.83 になります。
-チェスの騎士のように、長さは 2.24 (5 の平方根) になります。

したがって、この可能なステップの最大合計を見つける必要があります。上記のように「Best first search」で行くと、最長パスが常に最初の最適なオプションを選択するとは限らないため、面倒です。
次のグラフの場合:
123
456
789
1 つのオプションは 519467382 で、長さは約 17.7です。
したがって、前述のようにすべてのオプションを計算してみる方が安全かもしれませんが、対称性のために長さを計算する必要があることに注意してください。ノード1、2、および5を開始するためだけに。他のノードでも同じ結果が得られるため、計算は必要ありません....

Answer 2

手動で計算したところ、最長のものは 561943728 で、長さは 17.76 でした (最も近い 2 つのドット間の距離を 1 単位にします)。誰かがこれを打ち負かすことができたら、あなたのパターンを見せてください!

Answer 3

これは巡回セールスマン問題 (TSP) に似ていますが、最短経路の代わりに最長経路を探し、経路は閉じていません。

9 点の場合、可能性のあるすべてのパスを試すことを恐れません9! = 362880。また、3 x 3 の規則的なグリッドは非常に対称的であるため、この数を減らすことができる可能性があります。

別のアプローチ (パスが閉じられていないため) は、これまでで最も長いパスを持つノードを「最良」としてノードから最良優先検索を実行することです。各ノードからこれを行い、それらすべての最長パスを記憶します。しかし、これは簡単な考えに過ぎず、これが実際に機能するという証拠はありません。

Answer 4

最長パスは 567 348 192 で、約 18.428 です。

このようなパターンは少なくとも 8 つあり、もう 1 つのパターンは 567 381 932 (トラバース長 18.428) です。それらのパターンの周りに鏡像を置くと、そのようなパターンの 1 つから 4 つのパターンが得られます。