Введение в прикладную комбинаторику, Кофман А. (984071), страница 36
Текст из файла (страница 36)
П р и м е р. Шаг 1. Приписываем вершине Х, значение О, а остальным вершинам — значение .с (рис, 242). Имеем 1(ХО, Х1) = 7, Л! = сс, Л1 = О + 7 = 7 < сс, 1(Хъ Хз) = 8, Л, = сс, Л', = О + 8 = 8 < сс, 1(Хм Хз) = 3, Лз = сс, Лз = 8+ 3 = 11 < сс, 1 (Хь Хо) = 4, Ло = сс, Л( = 7 + 4 = 11 < сс, 1(Х, Хо) = 8, Ло = сс, Ло = 11 + 8 = 19 < сс 1(Х», Хз)=6, Лз= со, Лз=8+6= 14 < сс, 1(Хо, Хз) = 8, Лз = сс, Л( = 14+ 8 = 22 < сс, 1(Хо, Хв)=3, Лз=со~ Лв=19+3=22<со. Затем приписываем Х, значения Ло что иллюстрирует рис. 243, Шаг 2. Теперь 1(Хо, Х~) =7, Л1 = 7, Л1 =О + 7 =7, и рассматривая другие вершины ХзонГ Х„видим, что Л, нельзя уменьшить; 282 1(Хо, Хз)=8, Лз=8, Лз=О+ 8=8, и рассматривая другие вершины Х; ~ Г Хз, видим, что Лз нельзя уменьшить; 1(Хз, Хз) =3 Лз= 11, Лз= 8+ 3=11, и так как 1(Хо, Хз) =9 Лз=11, Лз=О+9=9<11, то Лз можно уменьшить до 9 (вершины Х, и Х дают большее значение).
Рис. 243. Так как то полагаем Л, = 11. Так как 1(Хм Хз)=6, Лз=14, Лз=8+6=14; 1(Хз Хз) = 5, Лз= 14, Лз= 9+ 5= 14; (52.9) 1(Хм Хз)=4, Лз=14, Лз=!9+4=23, то полагаем Лз=!4. Так как 1(Хз, Хо)=16, Ло=19, Ло=9+ 16=25 > 19; 1(Х4, Хо)= 8, Ло=19, Ло=!1+ 8=19; 1(Хз, Хо)= 4, Ло=19, Ло=14+ 4=18 < 19; 1(Хь Ло) = 2, Ло= 19, Ло =22+ 2=24 > 19, те полагаем Л, 18, 263 1(Хо, Х4) = 15, Л4 = 11 1(Хо Х4) = 4, Л4 = 11, 1 (Хз, Х4) = 6, Лз = 11, Л(=О+ 15=!5 > 11; Л(=7+ 4= 11; Л( = 9+ 6 = 15 > 11, Так как 1(Хь Хз)=15, Л7=22, Ц= 7+15=22; 1(Хз, Хт)= 8, Лз=22, Л1=!4+8=22; 1(Х„Х)= 2, Л,=22, Лз=18+2=20<22, то полагаем Л, = 20. Так как 1(Хо Хз) = 14, Лз = 22, Лз = 11 + 14 = 25 ) 22; 1 (Хз~ Хз) = 10, Лз = 22, Лв = 14 + 10 = 24 ) 22; 1(Хм Хв) = 3 Лв= 22, Лв= 18+ 3=21 < 22; 1(Хт, Хв)= 1 Ли=22 Лз=20+ 1=21 < 22, то полагаем Л,=21.
Результаты представлены на рис. 244. Рис. 244. Шаг 3. Действуя аналогично, видим, что ЧХ,(Л;=Л,+1(Хо Х,))Л!), т. е. значения путей уменьшить больше нельзя. приходим к минимальным путям от Х, до Хв: (Хв Хм Хв, Хв, Хв), (Хм Хм Хм Хв, (Хо Хз Хв, Хв, Хз), (Хв Хз, Хз, Хв, (52.10) Таким ооразом, (52.11) Х7~ ~з) со значением 21. На рис. 244 представлены также значения минимальных пугей от Хв до любой другой вершины. Отыскание максимального пути графа без контуров. Алгоритм Форда может быть использован для отыскания максимального пути таких графов.
Достаточно положить Лз = О, ! = О, 1, 2, ..., и, а затем заменять Л; на Ц =Л!+1(Хо Х~), если Л) ) Л;, до тех пор, пока возможно увеличивать Ль Алгоритм Беллмана — Калаба [2]. Этот алгоритм использует принцип оптимальности; «любой подпуть минимального пути 284 является минимальным путем между соответствующими вершинами». Рассмотрим граф 6 = (Е, Щ с ) Е( = и+ 1 и пронумеруем вершины от 0 до п.
Пусть сп ) 0 — значение, приписанное дуге (Хь Х,). Положим сп = со, если (Хь Х;) ф 1), и сп = О, если г = 1. Найдем такой путь (Х,, Х,„Х;,, ..., Х;,, Х„), что см, +сг,; + ... +сг»8 (52.13) минимально. Задача сводится к решению системы о;=ппп(о!+ сгг), 4=0, 1, 2, ..., и — 1, (52,14) !Фг о„=О, (52.15) где через оь г = О, 1, 2, ..., и — 1, обозначены значения оптимальных путей от Хг до Х„. Положим о!8> = с „, г = О, 1, 2, ..., сг — 1, гл' (52.16) (52.17) о|8' = О. о'8'=0 8 до тех пор, пока не будет выполнено равенство о',8' = о<48 ", г = О, 1, 2, ..., п, (52.21) оптимального пути нахождения доста- (стоимостей) выпи- ог8~= с =оо, огчг= с =со, г 18 ' 2 28 о'8г = с = 14 о18~ = с = 10, (52.22) 4 48 8 88 озг8)= с = оо 8 28 ог»г= с = оо, З 88 о =с,=З, кч 8 о 1= с =1, ог8~= с =О.
28 ' 8 88 Вычисляем последовательно оггг=ш(п(ог»г+с ), 4=0 1, 2, ..., п — 1, ганг г гг о',"=ш!п(о",-и+сг), 8=0, 1,2, ..., и — 1, г/)' и тогда о8»г будет минимальным значением от Х, до Х„. Легко показать, что для его точно и — 1 итераций. При мер (см. рис.
242). Матрица !! с !~ сана ниже (рис. 245). Имеем / = О, 1, 2, ..., и; (52.18) / = О, 1, 2, ..., п; (52.19) (52.20) Вычисляем последовательно (52.23) Хю Х~ Хз Хз Х4 Хв Хв «г Хв Хю Х, Х, Х Х Х Хв Рис. 245. Результаты сведены в нижеследугогцую таблицу; о!и= гп!п(о'"!+ с )= гмю =пни[о',"+ сюо ог,"+ со, ою'+ с,[= 29, о',н = гп!п (о!юг + с, .) = гФ! = гпгп [ою! + с„, оР' + с „, ..., оз~" + с1в) = 16, он!= гп!и [ого+ с 1 2 г з!) = пни[о!юю!+ сан оюза+ с н ..., о!вю'+ сзв) = 16, огп= гпгп(оси+ с 1= з [ г з!) = гнпп[о!юю! 1 сзю' о(ю! 1 см о!ю~ 1 сзв[= 15,- Так как о® = о',", 4 = О, 1, 2, ..., 8, то й = 4 и о'44 = 21 — мини.- мальное значение. По о~4"-ч, о)» ", ..., о4и легко выписать оптимальные пути (они даны в (52.11)).
3 а м е ч а н и е. Объем вычислений можно сократить, действуя следуюшим образом. а) Если о~м — наименьший элемент вектора ои~ (без учета п~„'4) и 4 Ф О, то фиксируем Х, и строим вектор оп'. б) Вектор ом~, 14 > О, определяем, исходя нз Х, и соотношения о(м = ппп (ом ", с, + ом "). П 4 в) В векторе опи выбираем наименьшее значение о4444, причем индекс 4 принадлежит верши~ам множества Š— 1Х4 М-Н 4 М-Н Яг] ЯЦ Рис 246.
(52. 24) 287 где Х44 ' — элемент с наименьшим значением при (й — 1)-й итерации (Е'=Š— (Х„]). Если 4=0, то (Хо, ..., Х„) — минимальный путь, В противном случае обращаемся к 6). Этим способом нельзя найти максимальный путь. Отыскание максимального пути в графе без контуров. С помощью метода Беллмана — Калаба можно указанным выше способом находить максимальные пути в графе без контуров. Для этого достаточно в уравнениях (52.16) †(52.21) заменить ппп на шах и си положить равным — оо, если (Хь Х,)ф П.
4. -4 УМС Например, на рнс. 245 числа в квадратиках обозначают значения максимальных путей от Х4 к Х„. Путь с минимальным произведением. Рассмотрим задачу об определении пути, для которого произведение значений, приписанных его дугам, минимально. Пусть с47 1 — значение дуги (Х;, Х7); с„=со, если (Хо Х )ф1), си =1, если 4 =1. Найдем такой путь (Хз Х4, Х4, ° ° Х44 Хь) что смс;~с,~ ...с~„„ 2 2 З (52.25) (52,29) Вычисляем последовательно о",>=гп!п(о<'>с, ), К=О, 1, 2, „„п — 1, 1=0, 1, 2, ..., и, (52.30) /Фа о„"=1, (52.31) о~и = ш(п(о'"-Нс, ), 1= О, 1, 2, ..., и — 1, 1' = О, 1, 2, ..., и, (52.32) оич и (52.33) до тех пор, пока не получаем о',и = о',~ ", 1 = О, 1, 2, ..., п. (52.34) Например, для графа на рис.
242 путь (Хс Хо Хо Хз) со значением смснсм = 105 (52.35) (52.36) минимален. С очевидными изменениями изложенный метод годится для отыскания путей с максимальным значением (52.25). В качестве чисел си часто рассматриваются вероятности ри попадания из вершины Х; в Хь В этом случае для всех Хь Х; имеем 0:~ри((1, Хрн —— 1. Или, например, в случае, если рн — надежность элемента линии связи, ставится задача о нахождении канала, по которому сообщение может быть получено с наибольшей вероятностью.
Расстояние между двумя вершинами. Путь минимальной длины. Рассмотрим граф 6= (Е, Г). Число с((Хо Х;) дуг в пути минимальной длины от вершины Х; до Х; называют расстоянием от Х; до Х,. Например, для графа на рис. 247 с1(А, В) = = 4, д(В, А) = 7. Нахождение расстояния — частный случай задачи оптимизации суммы значений дуг при с,; = 1, если 288 минимально. В этом случае задача решается с помощью видоизмененного алгоритма Беллмана — Калаба путем рассмотрения системы о; = пп'и [о с, ], (52.26) о„= 1, (52.27) где.через о, обозначено значение оптимального пути от Х; до Х„, Аналогично (52.16) — (52.21) полагаем о~о>=с,, 1=0, 1, 2, ..., и — 1, (52.23) (Хь Х„) ~ 1). Можно использовать алгоритм как Форда, так и Белолмана — Калаба, но мы поступим иначе. Пусть нужно найти расстояние от Хо до Х„, Полагаем г((Хь Х)) = оо, если не существует пути от Х; до Х;. Действуем по следукзпгим правилам: 1) помечаем вершину Х, индексом 0; г Рис.
247 2) помечаем индексом 1 все вершины Хь для которых Х; Ф Хо, Х; ~ ГХо; (52.37) 3) если через Сн, обозначено множество вершин, помеченных индексом пт, то образуем множество С,„е| — — (Хг )Х; ~ ГС, ()Уй ( гп) Хг ф Са); (52.38) 4) если Х„принадлежит некоторому С, то последовательность вершин таких, что Хг~С ь Хг,епГ Хн, Хг, е= С, Хп е= Г Хан (52.39) Хг а= Са, Хг„ен 1' Хг дает искомый путь. Задача нахождения максимального пути с сг, — — 1, если (Хо Х,) ~ 1), ставится лишь для графов без контуров, так как в противном случае она не имеет смысла. УПРАЖЕ! ЕНИЯ 82А. Для графа а) из упражнения 80Г найти. !) пути с минимальным значением от Е до О, от С до О, от Н до 0; 2) пути с максимальным значением от Е до О, от С до О, от Н до 0 Закон композиции — сложение. 82Б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
