Задача о соединении городов 39

Вид материала

Задача

Содержание Глава 2. графы и сети Abcda, ac dba, adbca, acbda, abdca, adcba. Abcda, acdba, adbca. AC DBA или ABDCA. Глава 2. графы и сети Sq — либо неудача при поступлении в бизнес-школу университета города Йорка, либо невозможность завершения обучения, Sr Глава 2. графы и сети Алгоритм (план реализации) Глава 2. графы и сети А ж В, может быть не­сколько (рис. 22), и каждое из них обладает своей пропускной спо­собностью. Из того, что поток из пункта А Глава 2. графы и сети Глава 2. графы и сети Обратный ход алгоритма

Подобный материал:

• Тема форума, 187.38kb.
• 1 Вопросы методологии исследования, 416.32kb.
• Проект Сводного доклада Форума "Стратегии крупных городов. Инвестиционные строительные, 508.25kb.
• Проблемы развития городов в последние годы уверенно занимает ключевую позицию в приоритетах, 81.82kb.
• Городов Всемирного Наследия, Международной Ассоциации Породненных Городов, Европейской, 145.2kb.
• Программа курса лекций «Математические методы и модели исследования операций», 27.98kb.
• Т. М. Боровська кандидат технічних наук, доцент І. С. Колесник, 118.17kb.
• Малые города России: в будущее – через инновации, 56.32kb.
• При физическом соединении двух или более компьютеров образуется компьютер¬ная сеть, 1009.79kb.
• Деловую программу откроет конференция, на которой будут обсуждаться вопросы формирования, 201.02kb.

о—»—с

Рис. 13

Рис. Ц

^ ГЛАВА 2. ГРАФЫ И СЕТИ

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

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

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

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

Пример 3. Торговец, живущий в городе А, намерен посетить го­рода В, С ж D, расстояния между которыми ему известны:

АВ = 11, АС = 13, AD = 17, ВС = 6, BD = 9, CD = 10

(рис. 16). Требуется указать кратчайший циклический маршрут из города А, проходящий через три других города.



Возможных циклических маршрутов шесть: ^ ABCDA, AC DBA, ADBCA, ACBDA, ABDCA, ADCBA.

34

2.2. СЕТИ

Однако для решения задачи достаточно сравнить длины только пер­вых трех:

^ ABCDA, ACDBA, ADBCA.

Эти длины равны соответственно

11 + 6 + 10 + 17 = 44, 13 + 10 + 9 + 11=43, 17 + 9 + 6 + 13 = 45.

Тем самым, кратчайшим является любой из маршрутов длиной 43 — ^ AC DBA или ABDCA.

Важный класс графов составляют так называемые деревья. Де­ревом называется связный граф, который не имеет циклов (рис. 17).



Рис. 17

Число В вершин дерева и число Р его ребер различаются на еди­ницу:

В = Р + 1.

2.2. Сети

В приложениях граф обычно интерпретируется как сеть, а его вер­шины называют узлами.

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

2.2.1. Дерево решений

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

35

^ ГЛАВА 2. ГРАФЫ И СЕТИ

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

Пример 4- По настоянию родителей выпускник американской школы должен продолжить учебу. Свободный в своем выборе, он хочет оценить возможности получения диплома в области инжини­ринга или в области бизнеса в одном из двух университетов — в университете родного города Йорка и в университете штата, пони­мая, что вероятность успеха зависит от выбора как университета, так и будущей специальности.

1. Если он останавливает свой выбор на университете штата и биз­
несе, то вероятность успеха (получение диплома) считается равной
0,60.

2. Если он останавливает свой выбор на университете штата и
   инжиниринге, то вероятность успеха считается равной 0,70.
   
3. Если он останавливает свой выбор на университете г. Йорка и
   бизнесе, то вероятность успеха считается равной 0,90.
   
4. Если он останавливает свой выбор на университете г. Йорка и
   инжиниринге, то вероятность успеха считается равной 0,95.
   
5. Средний доход за год в течение первых пяти лет у окончивше­
   го бизнес-школу университета штата при условии полной занятости
   равен 35 тыс. долл.
   
6. Средний доход за год в течение первых пяти лет у окончив­
   шего школу инжиниринга университета штата при условии полной
   занятости равен 30 тыс. долл.
   
7. Средний доход за год в течение первых пяти лет у окончившего
   бизнес-школу университета г. Йорка при условии полной занятости
   равен 24 тыс. долл.
   
8. Средний доход за год в течение первых пяти лет у окончивше­
   го школу инжиниринга университета г. Йорка при условии полной
   занятости равен 25 тыс. долл.
   
9. Если по каким-либо причинам выпускник не поступает ни в
   один из этих университетов, то его средний доход в течение этих
   пяти лет при условии полной занятости будет равен 18 тыс. долл.
   

Предположим, что единственным критерием при принятии вы­пускником окончательного решения является величина ожидаемого

36

2.2. СЕТИ

среднего дохода в первые пять лет его трудовой деятельности. Сде­лав это предположение, попробуем решить проблему выпускника, используя дерево решений (рис. 18).

^ ГЛАВА 2. ГРАФЫ И СЕТИ

2.2. СЕТИ

Значение N\ в узле 1 определяется так:

вследствие того что N₂ > N₃, полагаем N± = N₂ и считаем, что выбор d\ предпочтительнее выбора d₂. Тем самым, N± = 28 200 долл.

Наносим результаты расчетов на рис. 18 и принимаем оконча­тельное решение (рис. 19).

2.2.2. Задача о соединении городов

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

Имеется п городов — А±, А₂, . . . , А_п, которые нужно связать ме­жду собой сетью дорог. Стоимость сооружения дороги, соединяющей города Ai и Ak, известна и равна c(Ai,Ak).

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

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

^ Алгоритм (план реализации)

На 1-м шаге связываем два города с наиболее дешевым соединя­ющим звеном е\.

На каждом следующем шаге добавляем самое дешевое из звеньев е_г- (если имеется несколько звеньев с одинаковой стоимостью, выби­раем любое из них), в результате присоединения которого к уже по­строенным звеньям найденная сеть удлиняется еще на одно звено, но никакого цикла не образуется. При поиске добавляемого звена надо перебирать все ребра, имеющие общую вершину с уже построенной сетью.

Последний шаг алгоритма имеет номер п — 1.

Стоимость строительства полученной сети минимальна и равна

c(ei) + с(е₂) Н hc(e_n_i).

39

^ ГЛАВА 2. ГРАФЫ И СЕТИ

Пример 5. Пусть, например, нужно соединить города А, В, С ж D. Стоимость строительства дорог, соединяющих любые два города, известна и в условных единицах представлена в таблице:

	А	В	С	D
А	—	11	13	12
В	11	—	6	9
С	13	6	—	10
D	12	9	10	—

Сеть дорог минимальной стоимости состоит из 3 (4—1 = 3) звеньев и строится так: сначала выбирается самый дешевый участок доро­ги — ВС (его цена равна 6), затем он удлиняется на самый дешевый из оставшихся — BD (его цена равна 9). И на последнем, третьем шаге вновь выбирается самый дешевый (но так, чтобы не образова­лось никакого цикла) — АВ (его цена равна 11) (рис. 20). Таким образом, стоимость строительства равна 26 (6 + 9 + 11).



2.2.3. Максимальный поток

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

Чтобы пояснить основную идею метода решения этой задачи, предположим, что исходный и конечный пункты, пункт А и пункт В, находятся на разных берегах разделяющей их реки (рис. 21). Мно­жество мостов через реку образуют так называемое разделяющее се­чение (если все мосты по каким-либо причинам выйдут из строя,

40

2.2. СЕТИ

попасть из пункта А в пункт В будет просто невозможно). Ясно, что пропускная способность разделяющего сечения складывается из пропускных способностей всех мостов.

^ ГЛАВА 2. ГРАФЫ И СЕТИ

Сравнивая пропускные способности сечений, получаем, что мак­симальный поток от вершины 1 к вершине 7 равен 2.

2.2.4. Кратчайший маршрут

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

Алгоритм решения этой задачи состоит из двух частей.

Покажем, как он работает, на следующем примере.

Пример 7. Рассмотрим сеть, заданную на рис. 24, с выделенным узлом 1.



Рис. 24

Прямой ход алгоритма

1-й шаг. Все узлы, которые соединены с выделенным узлом 1 одним ребром, метятся так, как это показано на рис. 25 — первое число в метке равно расстоянию от помеченного узла до узла 1.

Ребро, связывающее узлы 1 и 3, является кратчайшим маршру­том от узла 1 к узлу 3 (любой другой маршрут от узла 1 к узлу 3 длиннее), и поэтому узлу 3 приписывается постоянная метка (15,1).

Таким образом, по окончании 1-го шага узлы 1 и 3 имеют посто­янные метки, узлы 2 и 4 — временные метки, а узлы 5, 6 и 7 никаких меток не имеют (рис. 26).

Замечание. При получении постоянной метки узел 3 выделяется так же, как и узел 1.

2-й шаг. Отбираются все узлы, которые соединены с узлом 3 од­ним ребром и не имеют постоянных меток. Это узлы 2, 4 и 6.

42

2.2. СЕТИ







(20,1)

40
(20,1)

^ ГЛАВА 2. ГРАФЫ И СЕТИ



(60,2)


(45,3)

.(20,1)

(20,1)


40

(60,2)


(49,5)




.(20,1)

40
(20,1)


Рис. 29

Рис. 30

2.2. СЕТИ

Замечание. На каждом шаге временная метка одного из узлов ме­няется на постоянную по следующему правилу: рассматриваются все узлы с временными метками и выбирается тот из них, длина маршрута до которого от узла 1 является наименьшей.

^ Обратный ход алгоритма

Используя вторую компоненту метки, определяем последователь­ность вершин в каждом кратчайшем маршруте. Например: метка (49,5) узла 7 указывает на предшествующий узел 5, метка (40,2) узла 5 указывает на предшествующий узел 2, метка (20,1) узла 2 указывает на предшествующий узел 1.

В результате обратная последовательность узлов кратчайшего маршрута от узла 1 к узлу 7 имеет вид

1.

Ответ:

Узел	Маршрут	Длина
2	1 -2	20
3	1 -3	15
4	1-3-4	23
5	1-2-5	40
6	1-3-4-6	43
7	1-2-5-7	49