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

Question

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

, например

М = 5, N = 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).