Самый длинный путь шаблона блокировки экрана Android

Сначала необходимо предоставить показатели расстояния.
Предположим следующее:
-Горизонтальное или вертикальное перемещение может быть длинным 1 на один шаг или 2 на два шага.
-Диагонально у вас будет длина 1,41 на один шаг (Квадратный корень из 2 , теорема Пифагора) или 2,83 за два шага (квадратный корень из 8).
-Как у коня в шахматах, у вас будет длина 2,24 (квадратный корень из 5)

Итак, теперь вам нужно найти только максимальную сумму этих возможных шагов. Если вы выберете "Лучший первый поиск", как упоминалось выше, это будет проблематично, потому что самый длинный путь не всегда выбирает первый лучший вариант.
Для следующего графика:
123
456< br/> 789
Один из вариантов — 519467382, который будет иметь длину около 17,7
Так что, возможно, безопаснее попытаться вычислить все варианты, как указано, но вы также можете иметь в виду, что из-за необходимой вам симметрии чтобы вычислить длины только для начальных узлов 1, 2 и 5. Другие узлы дадут те же результаты, поэтому нет необходимости в вычислениях....

Это похоже на задачу коммивояжера (TSP), но вместо кратчайшего пути вы ищете самый длинный, а путь не замкнут.

В случае с 9 точками я бы не боялся просто попробовать все возможные пути, поскольку их всего 9! = 362880. И это число потенциально может быть уменьшено, поскольку обычная сетка 3 на 3 очень симметрична.

Другой подход (поскольку путь не закрыт) может заключаться в выполнении поиска по первому наилучшему из узел с «лучшим» является тем, у которого на данный момент самый длинный путь. Вы сделаете это из каждого узла, запомнив самый длинный путь из всех. Но это всего лишь краткая мысль, и у меня нет доказательств, что это действительно сработает.

Я вычислил вручную и получил самое длинное число 561943728, которое имеет длину 17,76 (примите расстояние между двумя ближайшими точками равным 1 единице). Если кто-то может победить это, то покажите свою выкройку!

В основном проблема TSP с небольшой модификацией, которая запрещает переход через точки, которые не были посещены.

3x3 можно легко взломать. Для задач немного большего размера модифицированный алгоритм динамического программирования для TSP также работает за время {O(2^n*n^2)}.

https://repl.it/@farteryhr/AndroidLockscreen#index.js

3x3: 17.779271744364845

591643728
573461928
591827346
537281946
573829164
519283764
537649182
519467382

4x4: 45.679014611640504 (0123456789abcdef)

92d6c3875e1f4b0a
68793c2d5e1f4b0a
92d6c3875b4f1e0a
68793c2d5b4f1e0a
a1e5f0b46d2c7839
5b4a0f1e6d2c7839
a1e5f0b4687c2d39
5b4a0f1e687c2d39
a4b5f0e19783d2c6
5e1a0f4b9783d2c6
a4b5f0e192d387c6
5e1a0f4b92d387c6
9786c3d2a4b0e1f5
6d293c78a4b0e1f5
9786c3d2a1e0b4f5
6d293c78a1e0b4f5

5x5: 91,8712723085273 (0123456789abcdefghijklmno)

ci6o0j5dbea9f8g4k3m1n7l2h
cg8k4f9bdae5j6i0o1m3l7n2h
ci6o0n1h7m2l3g8k4fe5jb9ad
c8g4k3l7h2m1n6i0o5ef9bjad
cg8k4l3h7m2n1i6o0ja9fd5eb
c6i0o1n7h2m3l8g4k9aj5dfeb
c8g4k9fdbeaj5i6o0n2l3h1m7
c6i0o5jbdaef9g8k4l2n1h3m7

Самый длинный путь будет 567 348 192, что составляет около 18,428.

Таких паттернов минимум 8, еще один 567 381 932 (длина хода 18.428). Поместите зеркальное отражение вокруг этих узоров, и вы получите 4 узора из одного такого узора.