Введение в прикладную комбинаторику, Кофман А. (984071), страница 42
Текст из файла (страница 42)
Очевидно, что при некотором т подмножества ЕП<, Еа<, ... ..., Е< < дают разбиение Е. Аналогично можно определить и-минимально<е подмножества. Называют к-оптимумом (й-максимумом или й-минимумом) множества действительных чисел (о<) такое число о<»<, что (57.6) Е; ~ Епо -~ о; = ом! (число о<ю является й-м по величине среди всех о<), и записывают ор!' о; =о' '. (57.7) <=<ль ..., л Полагают ор! о;= -<- оо, (57.8) <=<,2, ° ° °, У если Е<м = 8 (знак «плюс» относится к ор! = пнп, знак «минус> — к ор! = <пах). Рассмотрим числовую функцию от А< действительных переменных и параметра хо оо,н (хо х< хо ° ° ° ~ хл) = о< (хо~ х<) + оо (х< хо) + ...
+о„(х„„х„)+ ... +оо(хн „хн), (57.9) где хоев Ео и х„ ев Г„(х„ ,), и = 1, 2, ..., А<, (57.10) а Г, — многозначные отображения и Га(х„<) — конечные множества. Тем самым приходим к последовательному графу. Для каждого хо зададимся областью 0(хо). Для получения й-оптимального подмножества в Р(хо) нужно вычислить й-оптимум функции (57.9): )о<ми(хо) = оР!ав оо и (хо, х„..., хн), (57.1!) (х<, хь ", хп) ~ Р (хо) 3<2 и найти (Л1+ 1)-выборки й(хо) = (хо, х!, ..., х„), для которых оо,н совпадает с (57.11).
(Лг + 1)-выборка йо,н, совместимая с (57.10), представляет путь в последовательном графе '), а (6 + 1)-выборка йп, ьл = = (т„, х„ьг, ..., х„ть), совместимая с (57.10), представляет подпуть в последовательном графе. Подпуть й, „ = (х„, х,+ь ..., хн) называют я-оптимальным путем из х„до вершин Лг-го уровня, если он принадлежит й-оптимальному подмножеству множества путей, выходящих из х„, Б е л л м а н и К а л а б а ') дали метод, состоящий в последовательном вычислении )й-!, н(хн-~) = ор( о„(хн „х,), (57.12) кн «гн (хн ~) ~„Р"и = ор1 [о„ь„(х„, х„,) + фг,, (х„ь,!)~, (57.13) жя, „и+ л' а+! 1=1'1, 2, ..., 11 1 = 1, 2, ..., й, и = Лг — 2, Л1 — 3, ..., О.
Этот метод основан на следующей теореме. Теорема о й-оптимальности. Подпуть й„,н= = (х„, х„+и ..., хн), образованный последними Лг — и+ 1 компонентами й-оптимального пути йон = (хо, х!,..., хн), является 1-оптимальным путем из х„до вершин Л1-го уровня для некоторого 1' ( й. Доказательство проведем от противного. Пусть й„,н — 1-оптимальный путь с 1) й. Тогда найдутся й подпутей из х„до вершин Лг-го уровня, все значения которых различны и «лучше», чем у й„,н.
Добавляя каждый из этих подпутей к первым п компонентам пути й,,„(что можно сделать, так как граф последовательный), получаем й путей, все значения которых различны и «лучше», чем у й,, ь. Это противоречит й-оптимальностн йа,н. Чтобы получить й-оптимальные пути от х„до вершин Лг-го уровня, по доказанной теореме достаточно рассмотреть 1-оптимальные подпути (1 = 1, 2, ..., Й) из х„+! до вершин Лг-го уровня. Если при некотором 1 множество гчоптимальных подпутей пусто, то формулы (57.12) и (57.13) остаются справедливыми в силу (57.8). Из рассмотрения формулы (57.13) следует, что для отыскания 1-оптимума достаточно рассмотреть множество А мощности 1 (Гх,), где (Гх„! — мощность Гх,.
Однако заметим, что 1' элементов из А, отвечающих заданному х„ь! (полагая последовательно 1= 1,2, ..., 1 в (57.13)), можно упорядочить. В силу этого достаточно разыскивать 1-оптимум в некотором множестве мощности (Гх„(. ') Этот путь называют также траекторией или стратегией. ') й. В е 1)гп а п, й. К а!а Ь а, Ои й-!Ь Ьеа1 ро!!с)еа, а. 5ос. 1пбпыг. Арр!. Мань 8, йа 4 (1950), 582 — 588. 343 Положим ') (57. 14) Чх (ф,(хи)= -1- оо, 1= 2, 3, ..., й), (57.15) Чх„))Гх„,(/~" (х„, х„,)=1, п=О, 1, 2, ..., А' — !), (57.16) Последовательно вычисляем при п = (й! — !), (М вЂ” 2), ...
2, 1, О, при всех х„и при') 1=1, 2, ..., /г х„, ~ Гх„: )~„' (х„) = ор! [о„,(х„, х„,)+ ~'„а~~, (х,)1, з„„, г „"~ " "+ (57.!7) где а=)~'~(х„, х„,) (57.18) и 1~„'"')(х„, х„,) = !и! + ! ь в противном случае; Итак, для каждого хо ~ Еа и для ! = 1, 2, ..., й получаем: значение 1-оптимального пути от хв до вершин й(-го уровня, равное ф'„(х ); множество 1-оптимальных путей от хв до вершин А'-го уровня (с помощью (57.20) ). Справедливость формул (57.17) — (57.20) следует из сравнения с (57.12) и (57.13); отличие следующее: а) вместо ~'-оптимума ищем !-оптимум, предварительно исключая /-оптимумы (! ( !); б) для отыскания 1-оптимума можно использовать лишь один элемент А для каждого хны (выбрасывая заведомо неоптимальные).
Этот алгоритм легко запрограммировать для ЭВМ. Полезно отметить, что: а) для более простого описания графа иногда бывает удобно добавить фиктивные вершины и приписать всем дугам, не фигурирующим в первоначальном графе, значение ~со; 1) Символы ~ и ~ ~означают либо + и ), либо — и < в зависимости от ор! = пип или ор! = так. ') Если (,ч и — — ." со длв некоторого й то !)с1 = л оо, П< ', (х„) = (л, ш аз-1 )=~',..., )е. 344 (57.19) П~а>.,(х„)=[х„„)чае(х„, х„,)!о„,(х„, х„,)+)~„"~, (х„,)= = )и>, (х„)). (57.20) б) изложенный алгоритм практически столь же эффективен, что и алгоритм Беллмана (см. (53.4)) для отыскания 1-оптимальных путей, так как требует для отыскания йоптимальных путей (1= 1, 2, ..., й) времени примерно в й раз больше (по формулам же (57.12) и (57.!3) примерно в йз раз).
Рис. 3??. Пример. Рассмотрим последовательный граф на рис. 377 (из А исходит 24 пути, а из  — 21 путь). Найдем йминималь. ные пути с 1= 1, 2, 3,4. Имеем ор! = ппп, й = 4, й? = 4. Удобно составить матрицу значений подпутей из х„до вершин У-го уровня (см. столбец (6) в таблице (57.22)). В столбцах (3) и (5) приведены соответственно окончательные и промежуточные результаты вычислений по данному методу. При вычислениях вручную к индикатору 1~," можно не обращаться.
На рис. 378 представлены Рминимальные пути (1 = 1, 2, 3, 4). Для большей наглядности некоторые вершины х„заменены вершинами (х„, 1), (х„, 2), ..., (х„, й). Множество 11~„'(х„) определяет тогда дуги 1-минимального пути из (х„, !). На рис. 379 некоторые 1-минимальные пути выделены. Заметим также, что: 1) если ищут Й-оптимальные пути из хе в фиксированную вершину х' л?-го уровня, то при использовании изложенного метода не учитывают дуги (хл „ х„) с хл Ф хд, Продолжение (5) «„,(лл, ш "и+()4 )л«(.
М (" ° ) (5) (л ) л' л+() (4) (з) (2) (и "л+1 4 7((4)4 (С) 18 12 12 18 (Р, 1) ПВ (С) (Р, 2) (Е,з) !и) (р) 12 13 11 17 15 16 14 оо 0 Н 12 13 17 п)о ())] (С, 1) (Н, 1) (Р, 2) (Р, 1) (и), (Е) 14 15 16 13 12 14 П(2') (Е) 12 (Н, 1) (Н, 2) (С, 2) (а,П (,'(,'4(Л) 16 13 14 16 22 17 18 13 14 С 0 19 (Е, 2) ((Е, 1)1 ~(С,2)~ и(') (А) 14 15 16 17 (С, 1) )о',)4(Е) 16 13 !6 17 18 13 17 15 ~(0,2)~ ~(1),3) ~ п",) (в) 16 17 18 (7), 1) (Е, 1) (57.22) 2) если Л)-й уровень содержит единственную вершину, то переходят к графу, получающемуся из исходного изменением направления всех дуг; 3) при отыскании )2-оптимальныл путей из вершин нулевого до вершин Л)-го уровня можно к исходному графу добавить вершину х ), соединить ее со всеми вершинами нулевого уровня дугами со значением О и найти (з-оптимальные пути от х ) до вершин Л)-го уровня.
Задачу об отыскании (4-оптимальных путей в произвольном графе во многих случаях можно свести к аналогичной задаче для последовательного графа, хотя зто сведение не всегда легка осуществить. 348 УПРАЖНЕНИЯ 37А. Указать 1-минимальные пути (ю'=1, 2, 3] между ха и хв в графе Аз д Ае 3 Аз у А Аа 3СРСУСзлеелеур 1 ,I Юд Дл Хе ХУ ~й 57В. Тот же вопрос для г-макспмальных 11 = 1, 2, 3) путей. 37В. Найти 1-минимальные и 2-минимальные пути между А и гУ в графе 67Г. Тот же вопрос для 1.максимальных н 2-максимальных путей.
37Д. Указать 1-минимальные пути (1 = 1, 2, 3, 4) в графе Ае А Аз Аз д" юд ха $58. Оптимизация на прадереве. Отыскание оптимального дерева, являющегося частичным графом Это два разных вопроса. Но мы рассматриваем их в одном параграфе ввиду родства понятий дерева и прадерева. Оптимизация на прадереве.
Как мы видели в $ 38, прадерево обладает порядковой функцией. Пусть его дугам (или вершинам) приписаны числовые значения. Задача состоит в отыскании оптимального пути между $ 1 1 $ ) К Рис, 380. корнем и висячими вершинами, образующими нулевой уровень. Общий метод оптимизации изложен в $ 51. Здесь мы рассмотрим лишь пример. Пример. Минимальный путь для прадерева на рис. 380 вьщелен. Отыскание оптимального дерева, являющегося частичным графом. Рассмотрим неориентированный связный граф 6 = (Е, Ю), ребрам которого приписаны некоторые числа.
Пусть Й вЂ” множество частичных графов Ни = (Е, 9и) графа 6, являющихся деревьями. Требуется найти дерево с минимальным значением Й = ш1п ~ч'„о (и). н„~н аа7ь (58.1) Для этой задачи можно использовать различные алгоритмы. Мы опишем здесь наиболее простой алгоритм Краскала, который мало эффективен для графов с большим числом вершин. Для таких графов предпочитают пользоваться алгоритмом Солена ([22)), который приспособлен для ЭВМ. 858 Алгоритм Краскала').
Принцип и формулировка этого алгоритма предельно просты. Действуют поэтапно, выбирая каждый раз ребро с возможно меньшим значением, добавление которого к уже выбранным ребрам не приводит к циклу. Обоснуем этот алгоритм. Пусть гг = (Е, е)) с ~ Е ~ = и — связный неориентированный граф, каждому ребру йг ен 1) которого приписано значение о(й;).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
