Введение в прикладную комбинаторику, Кофман А. (984071), страница 37
Текст из файла (страница 37)
Для графа В) ич упражнения ВОГ найти пути с минимальным н максимальным значениями от В до О, от В до О, от М до 0 и от М до 0 Закон композиции — сложение. 289 $2В. ЬъказатЬ максвмальиые И Миннмальные пути мвжДу А и В для еле. дующего графа (закон композиции — сложение): 52Г. Методом Форда найти минимальные пути от А до каждой из осталь. ных вершин графов а) и б) (закон композиции — сложение): Е а) А В С Н В Р 6 Н ! Х Н б) 62гх То же методом Беллмана — Калаба. 220 52Б.
Методом Форда найти мпннматьный и максимальный пути графа из упражнения 52В (закон композиции — сложение). 52Ж. То же методом Беллмана — Калаба. 523. Для графов упражнения 52Г найти методом Беллмана — Калаба минимальный путь (закон композиции — умножение). 52И.
Определить расстояние от вершины Л до каждой из остальных вершин следующих графов (предполагая, что в пустых нлетках стоят нули): Л В С Р Е Р С Л В С 0 Е Р О и 1 и) б) Л В С В Е Е 6 Н 1 1 Н в) В 53. Последовательные графы Граф сг =(Е, Г) называют последовательным, если для него выполняются следую:цие условия: 1) 6 обладает порядковой функцией 0(Х) со значениями 0,1, ..., п; 29! 2) ГЕзс: Ез.п й=О, 1, 2,, и — 1, (53.!) где Е =)Х)0(Х)=й), (53.2) Следовательно, последовательный граф — зто такой граф без контуров, в котором множество дуг, исходящих из вершин уровня Етл совпадает со множеством дуг, входящих в вершины уровня Епоь если нулевой уровень определяется условием à †'Ео = З. Пример такого графа приведен на рис. 248.
Очевидно, что к последовательным графам применимы способы отыскания оптимальных путей, изложенные выше, как, например, для графа на рис. 249, где максимальный путь выделен (на рис. 250, та же задача решена для того же графа, но с другой порядковой функцией). Для последовательного графа процесс оптимизации упрощается. Пусть о, (х„х,) — значение дуги, соединяющен уровень Е, с уровнем Еп о,(х„хз) — значение дуги, соединяющей уровень Е, с уровнем Е.„ оп(хл и хп) — значение дуги, соединяющей уровень Еп, с уровнем Еп, где х;, 1 = О, 1, ..., и — 1, — переменная, определенная на вершинах уровня Еь Тогда задача сводится к оптимизации функции Р (хо хз хз~ хп ~ хп) о1 (хо х~) + о (х| хз) + + оз (хз, хз) + ...
+ оп-1(хл — и хл-~) + ол (хл и хп). (53.3) Под сложением здесь можно понимать произвольную бинар- ную ассоциативную операцию .. Метод динамического программирования, основанный на принципе оптимальности, позволяет записать ~о,, (х„х,) = о, (х„х,), )о з(хо хз) = ор1 (1о, з (хо х!) л оз (хп хз)), к,ив, 1о,з(хо хз) = ор1 Ь,з(хо хз) * аз(хз хз)1 к ~Е, (53.4) 1о,л-1(хо х -з) = ор1 К, и з (хо, хп,) л ол, (хп,, х„,)), к ев п з л л (о п(хо, хп)= оР1 [1о и з(хо, хп,)*ол(хп „хл)). кл 1~ел 1 292 Рис. 251.
,' эу ! '! l Ер Е! Ег Еэ Е, Ег Еу Ег Ег ! ' Е" о' ЕО' ! ! ! о ! сЛ'~ у!' !О Л'' ! ! ! ! н! ! о ! ! г О! 4! ! у !эу в Iи! ! ! ! ! ! ! Ег Еу Ег Ео Е1 Рис. 252. о 'эо1 1Г1 ! ! ! !ИО' ' ! а' о, ,'и !в!с ! ф ! '!ио' 'И э! !О! ! ! ! у 'О!У О о ! о ! Ег Еу в, ! Е ! э !.Е! о О! '0 о'и ! с э 'а ! ! уФ ! О ! /О! !О ! ! ' и'' ' е'' Ег Ег О ! ! ! ~ с" ! ! ! ! 'ЕО ! В случае, когда Е, или Е„ содержат более одной вершины, (53.5) ор1 ), „(х„х„). «осЕю «« ~ Е« Последовательный граф можно разложить на последовательные подграфы, как показано на рис.
251, и производить оптимизацию по частям. С друтой стороны, вводя новые вершины, любой граф без контуров можно дополнить до последовательного. На рис. 252 показано, как это осуществляется; при этом новым дугам приписывается значение 0 (или нейтральный элемент относительно закона»). Задачи, приводящие к оптимизации на последовательных графах. Некоторые комбинаторные задачи можно свести к задаче оптимизации на последовательном графе. Пусть 1;(х;), 4 = 1, 2, 3, 4, заданы таблицей (53,6) Требуется определить минимум г (хи х, хм х4) ~~ (х,) + 14 (х4) + 14(х«) +14(х4) (53.7) при условии х, + х, + х, + х„= 5.
(53.8) Строится граф, дугам которого приписываются возможные значения функции из таблицы (53.6), как показано на рис. 253 (вершины расположены в том же порядке, что и числа в (53.6)). Порядок, в котором рассматриваются переменные хь хм хм х4, произволен, т. е. существуют 4! = 24 таких последова. тельных графов. Полагая х, +х,= пи сй+х.=н„и +х4=5, (53.9) 295 где (53.10) и,<5, и,<5, функцию (53.7) можно записать так: г (х„им и ) = г", (х ) + 7з (и, — х,) + Ь (из — и ) + 74 (5 — и ), (53.1!) т. е. в форме (53.3). хз хз Рнс 2оз. УПРАЖНЕНИЯ аЗА. Определить путь с минимальным значением из А~ до Г.~ для следующего графа (закон композиции — сложение): 53Б.
Определить путь с минималыпям значением от первого до последнего уровня для следующего графа (закон композиции — сложение): 3 Бг г бг г ~г г Ер и '5~ г $г 3 УУ~ г Ах чг ЗЗВ. То же для графа Вг' в, !гм еж 5ЗГ. То же, что и в упражнениях 53А — 53В, но для мзксимальных путей. ЗЗД. Решить задачу, аналогичную рассмотренной з последнем пункте зтого параграфа, для функций, заданных таблицей ЗЗЕ. То же, что и в упражнении 5ЗД, ио для максимального пути 297 БЗЖ.
Найти минимальное значение пути от первого до последнего уровня пля следующего графа (закон композиции — сложенне; веуказаниые значения I справа от А и Аз периодически повторяют указанные); 15) 2 533. Найти минимальный и максимальный пути от А ао Л для последова. тельного графа (запои композиции — сложение): ~г гз г, Е7 53И. Найти максимальный и минимальный пути от крайнего левого до крайнего правого уровня для следующего графа: У l 1) закон композиции — сложение 9) закон композвцни — умножение.
998 $ 54. Метод прогрессивных разделений и оценок (метод ветвления и ограничения)') Пусть Е = (5ь 5э, ..., 5„) — множество решений некоторой задачи, а ( — функция на нем. Требуется найти подмножество Е, на котором Г достигает минимума (если он существует). Предлагаемый метод можно использовать и для подмножества Ем максимальных решений.
ЯпвпСп...пМ АпвпСп...пМ Рис. 264. Пусть с помощью свойства Уд множество Е можно разбить на подмножество А и его дополнение А. Г[редположим, что мы умеем найти нижнюю границу Ь, значений 1 на Е, а также нижние границы Ьг) Ьс, Ьг) Ьс значений 1 па А, А соответственно. Рассмотрим свойства Ув, Ус, ..., также позволяющие разбить Е на две части.
Тогда свойствам Уа Л Ув Ул Л Ув Уа Л Ув Уа Л Ув соответствуют подмножества А П В, А Г[ В, А Г) В, А П В соответственно. Таким образом, можно образовать прадерево (рис. 254), которое, вообще говоря, нам не нужно строить полностью. Действуем следующим образом. Допустим, что мы уже построили часть прадерева, использовав Й свойств Уг, ..., Уго и нашли нижние границы для вершин этой части. Берем тогда одну из висячих вершин с наименьшей границей и с помощью этих й свойств и, быть может, нового Уасг получаем новые две ') См.
Б е р т ь е и Р о й [12), Л и т т л [Я. Р. С. ь 1111 е) и др., Ап А1яогпнгп 1ог Шс Тгатси1пя Ба)сьпгап Ргоыспг, а. О. К. Я. А. 11 [!963), 972 — 989. Отметим, что основы этого метода даны в 1961 г. Мальгранжем и Фором 299 вершины, для которых стараемся уточнить нижние границы, и т. д, Заметим, что объединение висячих вершин, получающихся на каждом этапе, дает Е. Например, для прадерева на рис. 255 имеем А () (А П В) () (А П В П С) () (А П В П С) = Е В силу этого замечания, если в результате данного процесса мы приходим к висячей вершине, являющейся одноэлементным множеством, то 1 принимает на нем минимальное значение. Очевидно, что аналогичные рассуждения можно использовать для получения максимального решения (если оно существует), рассматривая соответствующие верхние границы и стараясь их уменьшить на каждом шаге.
Этот метод можно назвать «методом оптимизации с помощью решета». Рассматриваются его различные модифика- А и 6 А и 6 ции (например, метод динамического программирования). При реализации этого метода существуют выбор свойств и АпВоп АобгтС уточнение оценок на каждом этапе. За- метим также, что вместо разбиений на Рис 266. две части можно рассматривать разбиения на п частей.
Об этом, в частности, см, работу Лоулера и Вуда' ). Отыскание оптимальных гамильтоновых контуров графа. Алгоритм Литтла'). Эта задача, известная под названием «задача о коммивояжере», долгое время оставалась нерешенной. В 1963 г. Литтл (вместе с другими авторами) дал для этой задачи строгий метод оптимизации; мы рассмотрим его на примере. Название этой задачи происходит из того, что гамильтонов контур можно рассматривать как путь коммивояжера, желающего посетить все города в точности по одному разу и возвратиться обратно. Опишем алгоритм Литтла для нахождения минимального гамильтонова контура для графа с и вершинами. Для иллюстрации рассуждений будем пользоваться полным симметрическим графом на рис.
256, каждой дуге (Хь Х,) которого приписано значение оп = о(Х;, Х;) ) О. Эти значения представлены в виде матрицы стоимостей 1~ оп ~~ (рис. 257). Символ «оо» означает, что между Х, и Х, нет дуги. Этот алгоритм сводится к следующим правилам. А) Находим в каждой строке матрицы ~~ оп ~~ минималвнвгй элемент и вычитаем его из всех элементов этой строки. Если в получающейся матрице окажутся столбцы, не содержащие ') ь а ж 1е г Е.
с, ап6 Цг о о 6 О. Е, Вгапсн-апа-Ьоипв Мсщоба: А зпгчеу, аоогпа) о1 Ше О. й. Бос1е1у о1 Агпепса 14, гй 4, эи)у — Аоноы, 1966, 699 — 719, ') См. сноску иа стр 299. 300 нуля, то в каждом из них находим минимальный элемент и вычитаем его из всех элелгентов этого столбца, Таким образо,и, мы приходим к матрице ,'~ он'2, каждая строка и каждый столбец которой содержат по меньшей лгере один нуль. Б) Суммируем все элемеггтьц которые мы вычитали в А), Очевидно, что эта сумма является нижней границей множества Х~ Ха Хз Х4 Ха Ха Гт Хэ ха х Рнс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
