Путь коня или какова польза ограничений?

Question

[mayton2019]

Добрый день всем.

Я решал задачу "путь коня" ( https://en.wikipedia.org/wiki/Knight%27s_tour ) на Java и с мультипоточкой много лет назад.

Сегодня я думаю над следующим. Для больших полей (1000х1000) можно ограничить движения коня коридорами шириной в 4 или 5 клеток и таким образом заставить его двигаться не так хаотично как в базовом варианте с DFS где конь просто идёт от первого хода (x+1,y+2) например до тех пор пока не упирается в стенку.

Что вы думаете на этот счет?

Answer 1

[Wataru]

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

Comments

[mayton2019]

Да. Я помню эту оптимизацию.

[Wataru]

mayton2019, Она, мне кажется, перекрывает предложенную вами оптимизацию. У вас придется коридор слишком широким делать, чтобы все крайние случаи покрыть. И тогда оптимизация станосивтся слабо эффективной.

[mayton2019]

Давайте обобщим и метод притягивания коня к стенкам и метод "коридоров".

У них обоих - одна и та же цель. Ограничить поиск в глубину (DFS) на примере ходов коня. Собственно, чего мы добиваемся, притягивая коня к краям доски? Чтобы конь - как можно быстрее выходил из глубоких узлов дерева. Из тех узлов из которых нет хода дальше. Как это достигается?

Я думаю что это достигается путём повышения веса клеток которые имеют соседей. Тоесть если мы вместо коридоров и правил Варнсдорфа введем некую гравитацию для каждой клетки (в том числе и свободной), тогда конь будет выбирать следующий ход не бездумно а притягиваясь к области клеток которые он уже обошел. Варнсдорф - это просто такой себе частный случай. +1 ход и клетка имеет бесконечный вес.

[Akina]

Есть простая оптимизация - из всех возможных ходов из текущей клетки перебирать сначала те, которые ведут в клетку с наименьшим количеством возможных следующих ходов (это надо проверить и все ходы через один ход и посмотреть, а обойдены ли те клетки уже)

Стопроцентно существует соответствующий этому алгоритму путь, который на доске 8*8 загоняет коня в тупик.
Если я правильно помню, то тупикового решения для случая, когда просматриваются вторые кандидаты, не найдено.

[Wataru]

Akina, Разумеется, это лишь оптимизация для полного рекурсивного перебора. Как и то, что предлагает автор.

Answer 2

[Adamos]

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

Comments

[mayton2019]

Мне почему-то это напомнило игру Сапёр.