#algorithm #chess #shortest
#алгоритм #шахматы #кратчайший
Вопрос:
Я столкнулся с любопытной проблемой.
У меня есть неограниченная шахматная доска, N начальных местоположений рыцарей и N целевых местоположений.
Задача состоит в том, чтобы найти минимальное количество ходов для всех рыцарей, чтобы достичь всех целевых местоположений.
Я знаю, что проблема кратчайшего пути для одного рыцаря может быть решена с помощью поиска в ширину, но как ее можно решить для нескольких рыцарей?
Извините за мой английский, я использую его редко.
Комментарии:
1. Стемплинг: как спотыкание, но хардкорное .
Ответ №1:
Вы можете вычислить матрицу затрат, как предложил Рики, используя поиск в ширину. итак, стоимость [i] [j] обозначает стоимость выбора рыцаря i для перехода в конечное местоположение j. Затем вы можете использовать венгерский алгоритм для поиска окончательного ответа, который может быть вычислен в сложности O (N ^ 3).
Ответ №2:
Я предполагаю, что вы знаете, как это сделать для одного Knigt.
Вы можете переформулировать свою задачу в виде линейной программы:
Я буду использовать следующие обозначения :
У нас есть N рыцарей и N местоположений en.
xij = 1 если вы выбрали коня i для перехода в местоположение j и 0 в противном случае
cij минимальная длина перемещения коня i в местоположение j
Тогда у вас есть следующая линейная программа :
переменные:
xij для i j в [0, N]
Функция стоимости :
C = SUM(cij.xij для (i, j) в [0,N] x [0, N])
ограничения:
СУММА (xij для j в [1, N]) = 1 // ровно одна книга переходит от i к j
СУММА (xij для i в [1, N] ) = 1
(Матрица (xij) является случайной матрицей)
если X является матрицей (xij), у вас есть n! возможная матрица. Эта проблема может быть NP-сложной (для этой системы нет простого решения, решение системы очень похоже на тестирование всех возможных решений).
Редактировать:
Эта проблема называется проблемой присваивания, и существует несколько алгоритмов для ее решения за полиномиальное время . (проверьте ответ @purav для примера)
Как упоминалось @Purav, хотя такого рода проблемы могут быть NP-сложными, в этом случае их можно решить за O (n ^ 3)
О проблеме, поднятой @j_random_hacker :
Проблема
Если рыцарь находится в конечной точке, следующие рыцари не должны проходить через эту конечную точку. Таким образом, Cij может потребоваться обновить после перемещения каждого коня.
Примечания :
1. несколько оптимальных путей :
Поскольку на стороне шахматной доски нет ограничений (ограниченная шахматная доска), порядок, в котором вы делаете свой ход для достижения кратчайшего пути, не имеет значения, поэтому всегда есть много разных кратчайших путей (я не буду здесь заниматься комбинаторикой).
Пример с 2 рыцарями
Допустим, у вас есть 2 K и 2 конечные точки (‘x’), оптимальный путь нарисован.
-x | | x | K-- --K
вы перемещаете нужное K в первую точку (1 ход), вторая не может использовать оптимальный путь.
-x | | K | K-- --:
Но я могу легко создать новый оптимальный путь, вместо того, чтобы перемещать 2 вправо на 1 вверх, затем 2 вверх на 1 вправо.
1 может переместить 2 вверх на 1 вправо, 1 вверх на 2 вправо (просто наоборот)
--K | - | K | | : --:
и любая комбинация путей работает :
1 U 2 R, затем 2 U 1 R и т. Д. … До тех пор, пока я сохраняю одинаковое количество ходов ВВЕРХ, ВЛЕВО, ВПРАВО и ВПРАВО, и что они действительны.
2. порядок, в котором перемещаются кони :
Во-вторых, я могу выбрать порядок своего хода.
пример:
в предыдущем примере, если я решил начать с левого коня и перейти к верхней конечной точке, больше не нужно ограничивать конечную точку.
-K | | x | :-- --K -K | | K | :-- --:
С помощью этих 2 замечаний можно было бы доказать, что нет ситуации, в которой вычисленная нижняя граница не является оптимальной .
Комментарии:
1. @j_random_hacker по поводу вашего первого возражения я написал «в целом», что, я думаю, верно. Но в данном случае это может быть не так, я не говорил, что это невозможно решить за полиномиальное время. Я должен был выкопать это больше. спасибо за ваши комментарии, я собираюсь отредактировать свой пост.
2. Это улучшение 🙂 Но есть еще несколько проблем. Алгоритмы для задачи о назначении не являются линейным временем, как вы утверждаете — согласно Википедии, наиболее известным является O (n ^ 3) (как вы сами говорите). Чтобы понять, почему ошибочно говорить, что каждая проблема IP является NP-трудной, подумайте, что вы можете сформулировать даже очень простые задачи (например, выбор максимального числа n) как проблему IP — очевидно, что ее можно решить за линейное время! Также недостаточно сказать, что «маловероятно», что одному рыцарю придется обойти другого — вам нужно доказать, что этого не может быть…
3. … поскольку в противном случае весь ваш подход дает вам нижнюю границу стоимости кратчайшего пути (т. Е. Он может сообщать о стоимости, которая ниже любого фактического кратчайшего пути). В этом случае я уверен, что это можно доказать. Вот схема: учитывая решение, «перематывайте» ходы с конца, пока не увидите ход коня, который не соответствует некоторому кратчайшему пути между его начальной и конечной точками. Предположим, что этот конь — x, а ход — от a до b, и что последнее пристанище x — p . Тогда причина, по которой x ушел «со своего пути», должна быть в том, что все остальные квадраты на кратчайших путях…
4. … между a и p заняты другими рыцарями. Выберите одного из этих других рыцарей произвольно (назовите его y). Теперь мы можем построить другое решение, в котором y переходит в p вместо x, потому что мы знаем, что y «в чистом виде», и нам все равно, какой конь на самом деле заканчивается на p, если какой-то конь делает. Итак, в этом новом решении y движется к p, оставляя свободным квадрат, на который теперь может переместиться x, поскольку он направляется к исходному месту отдыха y (т. Е. Позиции рыцарей x и y будут поменяны местами в окончательном решении). Вы можете продолжать перематывать и повторять это по мере необходимости до тех пор, пока…
5. … вы получаете решение, в котором каждый конь движется по кратчайшему пути к некоторому конечному квадрату. На самом деле в этом эскизе доказательства есть некоторые пробелы (например, действительно ли y «в чистоте»), но я думаю, что их можно было бы решить (или, может быть, кто-то может придумать гораздо более простую стратегию доказательства!) Боюсь, моя последняя жалоба заключается в том, что я вообще не могу разобрать ваше последнее предложение. Хорошо, извините за стену текста!
Ответ №3:
BFS все еще может работать здесь. Вам нужно немного настроить свои состояния, но это все равно будет работать:
пусть S — множество возможных состояний: S={((x1,y1),(x2,y2),...,(xn,yn))|knight i is in (xi,yi)}
Для каждого s в S определите:
Successors(s)={all possible states, moving 1 knight on the board}
Ваши целевые состояния — это, конечно, все перестановки ваших целевых точек [на самом деле вам не нужно разрабатывать эти перестановки, просто проверьте, достигли ли вы состояния, в котором все квадраты «заполнены», что легко проверить]
start=(start_1,start_2,...,start_n) где start_i — начальное местоположение коня i.
Запуск BFS из start [начальной позиции каждого коня] гарантированно найдет решение, если оно существует [потому что BFS завершена]. Это также гарантированно будет кратчайшим возможным решением.
(*) Обратите внимание, что случай с одним рыцарем является частным экземпляром этого решения с n = 1.
Хотя BFS будет работать, это займет много времени! коэффициент ветвления здесь равен 4n, поэтому алгоритму потребуется разработать O((4n)^d) вершины, где n — количество рыцарей, а d — количество шагов, необходимых для решения.
Возможные оптимизации:
- Пробел: обратите внимание, что, поскольку BFS использует много памяти [
O((4n)^d)], вы можете захотеть использовать итеративное углубление DFS, которое ведет себя как BFS, но потребляет гораздо меньше памяти [O(nd)], но требует больше времени для запуска. - Время: Для ускорения поиска решения вы можете использовать звезду с допустимой эвристической функцией. Также гарантируется поиск решения, если оно существует, а также гарантирует, что найденное решение является оптимальным, и, вероятно, [с хорошей эвристикой] потребуется развивать меньше вершин, чем BFS.
Ответ №4:
Итак, я нашел решение.
BFS не будет хорошо работать на неограниченной шахматной доске. Нет смысла использовать какой-либо алгоритм кратчайшего пути — количество ходов коня от местоположения a до местоположения b может быть вычислено за O (1) время — M. Деза, Словарь расстояний, стр. 251
http://www.scribd.com/doc/53001767/Dictionary-of-Distances-M-Deza-E-Deza-Elsevier-2006-WW
Проблема назначения может быть решена с использованием алгоритма mincost-maxflow (например. Эдмондс-Карп):