Как реализовать алгоритм кратчайшего пути в этом сценарии?

Question

В моем назначении у меня есть сетка MxN

например

М = 5, Н = 8

KKKK....
.###...X
.XX#...X
...#....
........

K - начальная точка, X - конечная точка, # - препятствие

Мне нужно найти наименьшее количество ходов для переноса посылок от начальных точек до конечных. Мы можем нести только 1 пакет за раз, и мы не можем двигаться по диагонали.

Ответ для этого примера 20.

Мое предложение состояло бы в том, чтобы реализовать алгоритм A* и запускать его для каждой возможности (рассчитать наименьшее число ходов от каждой из начальных точек к каждой из конечных точек) и выбрать наименьший из них, учитывая тот факт, что 1 пакет покрывает 1 конечная точка

Есть ли лучший способ реализовать это?

Answer 1

Хотя мое практическое понимание этого ограничено, я попытаюсь сформулировать проблему как проблему с минимальными затратами. Рассматривайте каждую начальную точку как источник, а каждую конечную точку - как сток. Стоимость отправки потока, fпо определенному краю f * a, где a это стоимость края. Обычным способом обработки нескольких источников и приемников является подключение каждой группы к другому отдельному экземпляру.

Предварительная формулировка:

Вызов n количество начальных или конечных точек.

1. соединить все начальные точки с одним источником с потоком nгде каждое ребро имеет емкость и поток 1 и стоимость 0.

2. соедините все конечные точки с раковиной, каждый край которой имеет емкость 1 и стоимость 0.

3. все остальные ребра имеют бесконечную емкость (по крайней мере n кажется, чтобы покрыть это) и стоимость 1.

4. найти минимальную стоимость для достижения потока n через сеть.

Диаграмма:

imaginary source
 with edge to each
  S with capacity 1
 / /|\
S1S-S1S2.2.2.2.
2       | | | 2   imaginary sink
. # # # .-.-.-T -- with edge to
2       | | | 1     each T with
.2T1T # .-.-.-T --  capacity 1
                      |   |
. . . # . . . .

. . . . . . . .

(Числа на диаграмме являются оптимальным потоком через каждое ребро, они в сумме составляют 20.)