Запрашивая алгоритм, чтобы найти N Knights глобальный кратчайший путь

Question

Я столкнулся с любопытной проблемой.

У меня есть неограниченная шахматная доска, N начальных локаций рыцарей и N целевых локаций.

Задача состоит в том, чтобы найти минимальное количество ходов для всех рыцарей, чтобы достичь всех целевых локаций.

Я знаю, что проблема кратчайшего пути для одного рыцаря может быть решена с помощью поиска в ширину, но как ее можно решить для нескольких рыцарей?

Извините за мой английский, я им редко пользуюсь.

Answer 1

Вы можете вычислить матрицу затрат в соответствии с предложением Рики, используя поиск в ширину.поэтому теперь стоимость [i] [j] обозначает стоимость выбора рыцаря i до конечного пункта j.Затем вы можете использовать Венгерский алгоритм , чтобы найти окончательный ответ, который можно вычислить в сложности O (N ^ 3).

Answer 2

Полагаю, вы знаете, как это сделать за один Knigt.

Вы можете переформулировать свою проблему как линейную программу:

Я буду использовать следующие обозначения:

У нас есть N коней и N локаций.

xij = 1, если вы выбрали рыцаря i, чтобы перейти к локации j и 0, в противном случае

cij - минимальная длина перемещения рыцаря i до места j

Тогда у вас есть следующая линейная программа:

переменные

xij для i j в [0, N]

Функция стоимости:

C = СУММА (cij.xij для (i, j) в [0, N] x [0, N])

Ограничения:

SUM (xij для j в [1, N]) = 1 // ровно один рывок идет от i к j

СУММА (xij для i в [1, N]) = 1

(Матрица (xij) является стохастической матрицей)

если X является матрицей (xij), у вас есть n! возможная матрица Эта проблема может быть NP-Hard (не существует простого решения для этой системы, решение системы очень похоже на тестирование всех возможных решений).

---

EDIT:

Эта проблема называется задачей присваивания , и существует множество алгоритмов для ее решения за полиномиальное время. (посмотрите пример ответа @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
   |
:-- --:

Этими двумя замечаниями можно было бы доказать, что не существует ситуации, в которой рассчитанная нижняя граница не является оптимальной.

Answer 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 complete ]. Также гарантировано самое короткое решение.

(*) Обратите внимание, что случай для single knight является частным экземпляром этого решения , с n = 1.

Хотя BFS будет работать, это займет много времени! коэффициент ветвления здесь равен 4n, поэтому алгоритму потребуется разработать O((4n)^d) вершин, где n - количество рыцарей, а d - количество шагов, необходимых для решения.

Возможные оптимизации:

1. Пробел: Обратите внимание: поскольку BFS использует много памяти [O((4n)^d)], вы можете хотите использовать Итеративное углубление DFS , которое ведет себя как BFS, но потребляет гораздо меньше памяти [O(nd)], но требует больше времени для запуска.
2. Время: Чтобы ускорить поиск решения, вы можете использовать Звезда с допустимая эвристическая функция . Также гарантированно найти решение, если оно существует, а также гарантирует, что найденное решение оптимальный, и, вероятно, [с хорошей эвристикой] нужно развивать меньше вершин, чем BFS.

Answer 4

Итак, я нашел решение.

BFS не будет хорошо работать на неограниченной шахматной доске.Нет никакого смысла в использовании любого алгоритма кратчайшего пути - число ходов коня от места a до места b можно вычислить за время O (1) - М. Деза, Словарь расстояний, с.251

http://www.scribd.com/doc/53001767/Dictionary-of-Distances-M-Deza-E-Deza-Elsevier-2006-WW

Проблема назначения может быть решена с использованием алгоритма mincost-maxflow (например, Edmonds-Karp):

http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm