mayton2019
@mayton2019
Bigdata Engineer

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

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

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

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

Что вы думаете на этот счет?
  • Вопрос задан
  • 202 просмотра
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Есть простая оптимизация - из всех возможных ходов из текущей клетки перебирать сначала те, которые ведут в клетку с наименьшим количеством возможных следующих ходов (это надо проверить и все ходы через один ход и посмотреть, а обойдены ли те клетки уже). Эта оптимизация как раз заставит коня ходить сначала вокруг стенки и по спирали подходить к центру.
Ответ написан
Adamos
@Adamos
Для больших полей вообще может иметь смысл перестроить алгоритм на определение самой "зажатой" на текущий момент клетки (той, в которую можно попасть из наименьшего количества клеток и при этом хотя бы одна из них уже занята) - и выстраивания кратчайшего пути до нее. Возвращаясь, если такой путь приводит к недостижимым клеткам.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы