78191

Алгоритмы поиска кратчайших расстояний в графе

Лекция

Информатика, кибернетика и программирование

Требуется посетить все вершины графа и вернуться в исходную вершину минимизировав затраты на проезд или минимизировав время. Исходные данные – это граф дугам которого приписаны положительные числа – затраты на проезд или время необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным и каждые две вершины соединяют две дуги – туда и обратно. Пусть требуется найти расстояния от 1й вершины до всех остальных.

Русский

2015-02-07

194.5 KB

14 чел.

екция: Алгоритмы поиска кратчайших расстояний в графе      Страница 2 из 2

Оглавление

[1] Оглавление

[2] Алгоритм поиска кратчайших расстояний в графе

[2.1] Алгори́тм Де́йкстры 

[2.2] Задача о кратчайшем пути

[2.3] Задача о максимальном потоке

[2.4] Задача линейного программирования при максимизации потока

[3] Контрольные вопросы

Лекция №22

Алгоритм поиска кратчайших расстояний в графе

Графы широко используются как в самой математике, так и в ее приложениях. Они применяются при построении различных математических моделей: линий электропередачи, сетей автодорог, линий воздушных сообщений и пр.

Требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд (или минимизировав время).

Исходные данные – это граф, дугам которого приписаны положительные числа – затраты на проезд или время, необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным, и каждые две вершины соединяют две дуги – туда и обратно. Действительно, если пункт А расположен на горе, а пункт Б – в низине, то время на проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А.

Многие постановки экономического содержания сводятся к задаче коммивояжера. Например:

  •  составить наиболее выгодный маршрут обхода наладчика в цехе (контролера, охранника, милиционера), отвечающего за должное функционирование заданного множества объектов (каждый из этих объектов моделируется вершиной графа);
  •  составить наиболее выгодный маршрут доставки деталей рабочим или хлеба с хлебозавода по заданному числу булочных и других торговых точек (парковка у хлебозавода).

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

Алгори́тм Де́йкстры  

Это  алгоритм на графах, изобретенный Э. Дейкстрой. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями — пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из не посещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.

Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 — вершина 3. Если идти в неё через 2, то длина такого пути будет = 7 + 10 = 17. Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22<, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.

Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).

Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

Задача о кратчайшем пути

 Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число – время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис.7).

Рис.7. Исходные данные к задаче о кратчайшем пути.

Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (табл.8).

Табл.8. Исходные данные к задаче о кратчайшем пути.

Начало дуги

Конец дуги

Время в пути

1

2

7

1

3

1

2

4

4

2

6

1

3

2

5

3

5

2

3

6

3

5

2

2

5

4

5

6

5

3

Задача: как кратчайшим путем попасть из вершины 1 в вершину 4?

Решение. Введем обозначение: С(Т) – длина кратчайшего пути из вершины 1 в вершину Т. Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается. Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на рис.7 и в табл.6, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С(3)=1. Кроме того, очевидно, что С(1)=0. В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение С(4)=min{С(2)+4; С(5)+5}. 

Таким образом, проведена реструктуризация задачи – нахождение С(4) сведено к нахождению С(2) и С(5).  В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение С(5)=min{С(3)+2; С(6)+3}. Мы знаем, что С(3)=1. Поэтому С(5)=min{3; С(6)+3}. Поскольку очевидно, что С(6) – положительное число, то из последнего соотношения вытекает, что С(5 =3. В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение С(2)=min{С(1)+7; С(3)+5; С(5)+2}. Нам известно, что С(1)= 0, С(3 =1, С(5)=3. Поэтому С(2) =min{0+7; 1+5 ; 3+2}=5.

Теперь мы можем найти С(4): С(4)=min{С(2)+4 ; С(5)+5}=min{5+4; 3+5}=8.

Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1.

Итак, кратчайший путь таков: 1 → 3 → 5 → 4 .

Задача о кратчайшем пути для конкретных исходных данных (рис.7 и табл.6) полностью решена.

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

Задача о максимальном потоке 

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

Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной  системе, должно быть сопоставлено число - пропускная способность этой дуги. Рассмотрим пример (рис.8).

Рис.8. Исходные данные к задаче о максимальном потоке

Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис.8, можно также задать таблицей (табл.9).

Табл.9. Исходные данные к задаче о максимальном потоке

Пункт отправления

Пункт назначения

Пропускная способность

0

1

2

0

2

3

0

3

1

1

2

4

1

3

1

1

4

3

2

3

1

2

4

2

3

4

2

Решение задачи о максимальном потоке может быть получено из следующих соображений.

Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов  можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.

Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2  грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу – в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 3. Их направляем в пункт 4.

Итак, максимальная пропускная способность рассматриваемой транспортной системы – 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 – по ней направлены 2 единицы груза при пропускной способности в 3 единицы.

Решение можно представить в виде таблицы (табл.10)

Табл.10. Решение  задачи о максимальном потоке

Пункт отправления

Пункт назначения

План перевозок

Пропускная способность

0

1

2

2

0

2

3

3

0

3

1

1

1

2

0

4

1

3

0

1

1

4

2

3

2

3

1

1

2

4

2

2

3

4

2

2

Задача линейного программирования при максимизации потока

Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть ХKM – объем перевозок из пункта К в пункт М. Согласно рис.8 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных ХKM , а именно,  Х01 , Х02 , Х03 , Х12 , Х13 , Х14 , Х23 , Х24 , Х34 . Задача линейного программирования, нацеленная на максимизацию потока, имеет вид: F   →  max ,

Х01 +Х0203=F  (0)
- Х
01 + Х12 + Х13 +Х14 = 0 (1)
- Х
02 - Х12 + Х23 + Х24 = 0 (2)
03132334= 0 (3)
142434=-F (4)
Х
01  ≤  2                                    

Х02  ≤  3                                    

Х03  ≤  1                                    

Х12  ≤  4       

Х13  ≤  1                                    

Х14  ≤  3                                    

Х23  ≤  1                                    

Х24  ≤  2                                    

Х34  ≤  2                                    

ХКМ  ≥ 0 , К, М = 0, 1, 2, 3, 4,  F ≥ 0 .

Здесь F – целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1)–(3) задают балансовые соотношения для узлов 1–3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не "рождаются" в ней.  Условие (4) – это условие "выхода" грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом ("вход" равен "выходу"). Следующие девять неравенств задают ограничения на пропускную способность отдельных "веток" транспортной системы. Затем указана неотрицательность объемов перевозок и целевой функции.

Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию – через систему может быть  пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом "не знает").

Контрольные вопросы

  1.  Дайте определение алгоритму поиска в графах.
  2.  Принцип работы алгоритма Дейкстры.
  3.  Сформулировать задачу о кратчайшем пути. Область применения.
  4.  Сформулировать задачу о максимальном потоке. Область применения.
  5.  Сформулировать задачу линейного программирования при максимизации потока. Область применения.


 

А также другие работы, которые могут Вас заинтересовать

17752. Расчёт ступени центробежного насос. Построение лопастей колеса в меридианном сечении и в плане 369.5 KB
  Лекция 8. Расчёт ступени центробежного насоса продолжение Построение лопастей колеса в меридианном сечении и в плане. Особенностью принятого способа изображения лопастей в меридианном сечении является то что лопасти не рассекаются плоскостью а в этой плоскости сов...
17753. Конструкция и работа центробежных насосов 1.33 MB
  Лекция 9. Конструкция и работа центробежных насосов Усилия в центробежных насосах. При работе центробежных насосов на роторе возникают осевое и радиальное усилия. Причина возникновения осевого усилия объясняется на основании рис. 9.1. В соответствии с рисунком осевое у...
17754. Объёмные насосы 709 KB
  Лекция №10. Объёмные насосы Специфической особенностью всех объёмных насосов является то что их производительность в основном определяется величинами периодически замыкаемых в них объёмов и скоростью переноса этих объёмов со стороны всасывания на сторону нагнетани
17755. Действительная подача шестерённого насоса 1.66 MB
  Лекция 11. Объёмные насосы продолжение 10.3. Действительная подача шестерённого насоса. Действительная подача шестерённого насоса меньше теоретической на величину объёмных потерь . Объёмные потери определяются внутренними утечками в насосе и потерями связанны
17756. Регулирование производительности насосов 331 KB
  Лекция №12. Регулирование производительности насосов. При регулировании производительности насосов используют разные способы соединения насосов между собой и разные способы изменения параметров характеристик как насосов так и систем на которые они работают. Все эти ...
17757. Поршневые пусковые компрессоры 4.37 MB
  Лекция №13. Поршневые пусковые компрессоры. 13.1. Устройство и работа поршневых пусковых компрессоров. На рис. 13.1 представлена принципиальная схема одноступенчатого поршневого компрессора. Поршень движется в цилиндре возвратнопоступательно от верхней мёртвой точки ВМ...
17758. Расчёт многоступенчатого поршневого компрессора 730 KB
  Лекция №14. Расчёт многоступенчатого поршневого компрессора. 14.1 Коэффициент подачи компрессора. Все коэффициенты снижения производительности названные в предыдущей лекции могут быть вычислены на основании зависимостей установленных достаточно простым способом...
17759. Проектирование многоступенчатого поршневого компрессора 375.5 KB
  Лекция №16. Проектирование многоступенчатого поршневого компрессора. 16.1 Выбор числа ступеней. При выборе числа ступеней можно находить минимально возможное число ступеней zmin и оптимальное число ступеней zopt. Минимальное число ступеней устанавливается из условия вз...
17760. Дослідження забруднення повітряного середовища робочої зони 260.5 KB
  Лабораторна робота №9 Дослідження забруднення повітряного середовища робочої зони Вступ Лабораторна робота з дослідження забруднення повітряного середовища робочої зони комплексна. До її складу включені: 1. Лабораторна робота з дослідження запиленості по