Предположим, что у нас есть 9 баллов. Каждый из них может посещать только один раз. Также допускается путь, например, от верхнего левого угла до нижнего правого угла. Может ли кто-нибудь предоставить алгоритм вычисления самого длинного пути для шаблона блокировки экрана?Самый длинный путь экрана блокировки экрана Android
Прежде всего вам необходимо указать метрики расстояния.
Предположим следующее:
- Горизонтальное или вертикальное перемещение может быть длинным 1 для одного шага или 2 для двух шагов.
-Диагонально у вас будет длина 1.41 за один шаг (квадратный корень из 2, теорема пифагора) или 2.83 для двух шагов (квадратный корень из 8).
-Как рыцарь в шахматах будет иметь длину 2,24 (квадратный корень из 5)
Так что теперь вам нужно найти только максимальную сумму этих возможных шагов. Если вы поедете с «Лучшим первым поиском», как упомянуто выше, это будет проблематично, потому что самый длинный путь не выбирает в качестве первого наилучшего варианта.
Для следующего графика:
Одним из вариантов является 519467382, которая будет иметь длину около 17,7
Так может быть, это безопаснее, чтобы попытаться расчета всех вариантов, как уже упоминалось, но вы также можете сохранить в помните, что из-за симметрии вам нужно рассчитать длины только для начальных узлов 1, 2 и 5. Остальные узлы будут давать одинаковые результаты, поэтому нет необходимости в вычислениях ....
Это похоже на проблему коммивояжера (TSP), но вместо кратчайшего пути вы найдете самый длинный путь, и путь не закрыт.
Для случая с 9 пунктами я бы не боялся просто пытаться использовать все возможные пути, так как есть только 9! = 362880 из них. И это число потенциально может быть уменьшено, так как 3 на 3 правильная сетка очень симметрична.
Другой подход (поскольку путь не закрыт) мог бы делать best-first search от узла с «лучшим», который имеет самый длинный путь до сих пор. Вы будете делать это с каждого узла, запоминая самый длинный путь для всех. Но это всего лишь быстрая мысль, и у меня нет доказательств того, что это действительно сработает.
Самый длинный путь - 567 348 192 , который составляет около 18,428
Есть по меньшей мере 8 таких узоров, один из которых - 567 381 932 (длина хода 18.428). Поместите зеркальное изображение вокруг этих шаблонов, и вы получите 4 шаблона из одного такого шаблона.
Самый длинный путь = посещение всех 9 баллов? Если это так, это частный случай проблемы гамильтонова пути, который довольно легко решается для 9 узлов. В противном случае, пожалуйста, объясните, что означает «самый длинный». – amit
Конечно. Нам нужно посетить больше очков, чтобы создать максимально возможное расстояние. Таким образом, очевидно, что все 9 пунктов должны быть посещены. –