78191

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

Лекция

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

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

Русский

2015-02-07

194.5 KB

20 чел.

екция: Алгоритмы поиска кратчайших расстояний в графе      Страница 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.  Сформулировать задачу линейного программирования при максимизации потока. Область применения.


 

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

70887. Перспективы создания конкурентной среды в Республике Казахстан 474.5 KB
  1 Проблема развития конкуренции и антимонопольная политика в РК 59 3. Ключевым понятием выражающим сущность рыночных отношений является понятие конкуренции competition . Благодаря экономической свободе сопутствующей ей конкуренции рыночная экономика превосходит командноадминистративную в которой конкуренции нет места. Положительные стороны конкуренции: конкуренция заставляет постоянно искать и использовать в производстве новые возможности; конкуренция требует совершенствовать технику и технологии; конкуренция стимулирует...
70888. Граждане как субъекты гражданского права. Гражданские правоотношения 275 KB
  В современном мире общепризнанным является взгляд на права человека как универсальную категорию отражающую наднациональные общечеловеческие требования и стандарты в области свободы личности. В этом плане права человека являются не государственно-правовой конкретно-юридической категорией...
70889. ЦЕНОВАЯ ПОЛИТИКА ОРГАНИЗАЦИИ И МЕРОПРИЯТИЯ ПО ЕЕ СОВЕРШЕНСТВОВАНИЮ 1005.5 KB
  Целью дипломной работы является на примере предприятия ЧУП «Гроднотурист» провести анализ ценовой политики гостиничного бизнеса и разработать мероприятия по ее совершенствованию. Для реализации цели выделены следующие задачи: определить сущность и специфику гостиничного бизнеса...
70890. Анализ использования трудовых ресурсов в ЗАО «Дельта» 1.28 MB
  Для изучения данной темы последовательно рассмотрим использование трудовых ресурсов на основе: анализа численности и движения рабочей силы; анализа использования рабочего времени; анализ эффективности использования трудовых ресурсов. Достижение цели возможно при постановке...
70891. Правила оформления документации при передаче дел в архив 176 KB
  Формирование исполненных документов в дела в организации осуществляется в течение всего делопроизводственного года в соответствии с утвержденной на данный год номенклатурой дел. С начала делопроизводственного года должны быть оформлены обложки дела по правилам оговоренных...
70893. СОВЕРШЕНСТВОВАНИЕ ДЕЯТЕЛЬНОСТИ ОРГАНОВ МЕСТНОГО САМОУПРАВЛЕНИЯ ПО ПРОФИЛАКТИКЕ И БОРЬБЕ С СОЦИАЛЬНО ЗНАЧИМЫМИ ЗАБОЛЕВАНИЯМИ (на примере Республики Марий Эл) 1.32 MB
  Главной целью социальной политики Российской Федерации является последовательное повышение уровня и качества жизни обеспечение всеобщей доступности основных социальных услуг прежде всего качественной медицинской помощи и социального обслуживания обеспечение занятости населения.
70894. ФИНАНСОВО-ПРАВОВЫЕ ОСНОВЫ МЕСТНОГО САМОУПРАВЛЕНИЯ 407.5 KB
  Цель настоящей выпускной квалификационной работы состоит в формировании целостного представления об особенностях правовой природы финансовых основ местного самоуправления, особенностей, касающихся устава муниципального образования, муниципальной собственности и бюджета...
70895. Повышение эффективности стимулирования труда на предприятии ООО «Юниор» 244.61 KB
  При изучении теоретических основ стимулирования труда на предприятии автор данной работы опирается на разработки известных специалистов. Опираясь на теорию и анализ действующей системы стимулирования труда автор проявил свою зрелость и обеспечил успешное решение задач...