Занятие 5. Решение задач ДП: Задача поиска кратчайшего пути (о поиске минимального расстояния)

Авторadmin / Опубликовано

Решение задачи динамического программирования о поиске кратчайшего пути

Назад
К оглавлению
Далее

Постановка задачи

Представим граф, представляющий собой воображаемую карту дорог, вершинами которого являются точки пересечения дорог или перекрестки (A11, A21, A31, A12, A22, A31, A13, A23…), см. рис. 5.1.

Необходимо добраться из дома на работу, сделать это следует за минимальное время или другими словами — с помощью маршрута минимальной длины.

Рис. 5.1. Граф для задачи поиска кратчайшего пути
Рис. 5.1. Граф для задачи поиска кратчайшего пути

Итак, наша цель:

  1. определить путь минимальной длины;
  2. определить минимальное расстояние от дома до работы.

Введем условные дополнения:

  • ехать можно только в одну сторону — слева направо (например, из точки A21 можно двигаться только в точки A31 и A32)
  • расстояние между точками или перекрестками укажем в таблицах:
A11 A12 A13
Дом 1 2 3
A21 A22 A23
A11 2 1 1
A12 1 2 1
A13 2 3 2
A31 A32
A21 3 2
A22 3 3
A23 1 3
Работа
A31 4
A32 3

Как решить задачу без использования методов ДП?

Наивное решение

Наивным решением может быть метод перебора.

Граф имеет структуру — порядок слева направо.

  • взять 1-й путь и найти его длину d1
  • взять 2-й путь и найти его длину d2
  • …
  • взять k-й путь и найти его длину dk

После этого определить минимальный путь посредством процедуры argmin (di), i=1...k

Т.е. решить такую задачу можно перебором.

Минус:
Посчитаем количество путей (из каждой вершины) — получим 18 путей.
Это не так мало, задача ведь простая.

При увеличении графа количество путей будет расти экспоненциально (путем умножения), как функция количества перекрестков.

Такие алгоритмы считаются не эффективными.

Другой вариант:
Можно воспользоваться так называемыми алгоритмами на графах, например, алгоритмом Дейкстра. О них поговорим на другой лекции.

Использование методов динамического программирования

Составление порядка решения

Для начала обратим внимание, что у задачи есть структура — порядок вершин. Т.е. такой линейный порядок можно определить, как количество перекрестков, которые нужно миновать, доехав до работы.

Двигаясь от точки, обозначающей работу, разобьем граф на количество уровней перекрестков (рис. 5.2):

решение задачи поиска кратчайшего пути на графе
Рис. 5.2. Количество уровней перекрестков, которые надо пересечь, доехав до работы

Получилось 4 уровня перекрестков от Дома до Работы.

Этим порядком и воспользуемся для решения задачи поиска кратчайшего пути методом динамического программирования.

Предположим, что мы находимся на последнем уровне перекрестков от Работы.
На последнем уровне перекрестков минимальная длина пути из каждого перекрестка до работы известна (из таблицы) — это 4 и 3.

Зная минимальную длину пути из этого уровня перекрестков до Работы, можно ли найти минимальную дину пути из следующего уровня (A21, A22, A23) до Работы? — да можно. Например, из точки А21 нужно посмотреть всего два варианта: А21 -> A31 и A21 -> A32. Затем выбрать минимальный из них, воспользовавшись процедурой argmin.

Теперь, зная минимальную длину пути из перекрестков второго уровня до Работы, можно найти минимальную длину пути из перекрестков третьего уровня до Работы.

И так и продолжим, пока не найдем минимальную длину пути от Дома до Работы.

Словесный алгоритм мы разработали. Теперь приступим к решению.

1 этап: определению целевой функции и порядка решения:

FAij — минимальная длина пути из перекрестка Aij до работы.
Запишем формулу. Начнем с последнего уровня перекрестков, двигаясь влево.

F3,j (j)=1,2 <- F2,j (j)=1,2,3 <- F1,j(j)=1,2,3 <- FДом

2 этап: Определение начального условия:

F3,1 — минимальная длина пути из перекрестка A31 до Работы = 4
F3,2 — минимальная длина пути из перекрестка A32 до Работы = 3

F3,1 = 4
F3,2 = 3

3-й этап: определение рекурсивной функции перехода от, например, F2,j (j)=1,2,3 до F3,j

F2,2 — это второй уровень, состоящий из перекрестков А21, А22, А23

Рассмотрим перекресток А22, из которого есть два пути:

  1. А22 <- А31, а из него мы отправимся до работы минимальным маршрутом, который уже рассчитан — это F3,1; получаем 3 + 4;
  2. и А22 <- А32, а из него мы отправимся до работы минимальным маршрутом, который ужже рассчитан — это F3,2; получаем 3 + 3;

Затем необходимо выбрать минимальный из них, используя функцию argmin : 6 < 7, т.е. нам подходит А32

Итак, получаем по одной ветви второго уровня перекрестков:
F2,2 = min[A22 -> A31 -> Работа; A22 -> A32 -> Работа] = min[3 + 4; 3 + 3] = 6 (А3,2)

Рассчитываем следующую ветвь второго уровня:

F2,1 = min[A21 -> A31 -> Работа; A21 -> A32 -> Работа] = min(3 + 4; 2 + 3) = 5 (А32)

Рассчитываем последнюю оставшуюся ветвь второго уровня:

F2,3 = min(1 + 4; 3 + 3) = 5 (А31)

Рассматриваем третий уровень перекрестков:

F1,1 (перекресток A11) = min[A11 -> A21 -> F2,1;A11 -> A22 -> F2,2;A11 -> A23 -> F2,3] = min[2 + 5;1 + 6;1 + 5] = 6 (A23) (А31)

F1,2 (перекресток A12) = min[1 + 5;2 + 6;1 + 5] = 6 (A23) (А21), можно взять любой минмимум из двух

F1,3 (перекресток A13)= min[2 + 5;3 + 6;2 + 5] = 7 (A23) (А21), можно взять любой минмимум из двух

F3 F2 F1
1 4 5 (A32) 6 (A23)
2 3 6 (A32) 5 (A21)
— — 5 (A31) 7 (A21)

Осталось найти цель — из Дома:

FДом = min[1 -> A11 -> F11; 2 -> A12 -> F12; 3 -> A13 -> F13] = min[1 + 6;2 + 6;3 + 7] = 7 (A11)

Результат:

Длина минимального пути из Дома до Работы = 7
Восстановим минимальный путь: A11 -> A23 -> A31 - > Работа

Сложность решения: решая задачу с перебором, приходилось умножать (3 * 3 * 2), а в данной задаче нам необходимо складывать. Т.е. мы получаем вместо экспоненциальной функции эффективное полеомиальное решения.

Но решение работает не для всех графов, например, если можно двигаться во всех направлениях, не только слева направо, то функция работать не будет.

Назад
К оглавлению
Далее