По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
1 2 3 4 5 А В 1 1 1 0 0 0 2 1 0 0 0 1 * 3 0 0 1 1 0 * * 4 0 1 0 1 0 * 5 0 0 0 1 1 186 4. Алгоритмы на графах 4.9. Потоки в сетях, паросочетания 4.9.1. Постановка задачи Одной из задач теории графов является задача определения максимального потока, протекающего от некоторой вершины s графа (источника) к некоторой вершине t (стоку). При этом каждой дуге (граф ориентированный) приписана некоторая пропускная способность определяющая максимальное значение потока, который может протекать по данной дуге. Со- держательных интерпретаций задачи достаточно много, и, бе- зусловно, они усилят и сделают более понятными сложные за- нятия по этой проблематике. Метод решения задачи о максимальном потоке от s к t был предложен Фордом и Фалкерсоном, и их «техника меток» со- ставляет основу других алгоритмов решения многочисленных задач, являющихся обобщениями или расширениями указан- ной задачи. Одним из фундаментальных фактов теории потоков в сетях является классическая теорема о максимальном потоке и ми- нимальном разрезе. Разрезом называют множество дуг, удале- ние которых из сети приводит к «разрыву» всех путей, веду- щих из s в Пропускная способность разреза — это суммарная пропускная способность дуг, его составляющих. Разрез с мини- мальной пропускной способностью называют минимальным разрезом. Теорема (Форд и Фалкерсон). Величина каждого потока из s в t не превосходит пропускной способности минимального разре- за, разделяющего s и t, причем существует поток, достигающий этого значения. Теорема устанавливает экви- валентность задач нахождения максимального потока и минима- льного разреза, однако не опреде- ляет метода их поиска. Пример. Показана сеть, источник — вершина 1, сток — вер- шина 6, в скобках у дуг указаны их пропускные способности. Минимальный разрез — дуги (1, 2) и (3, 4), следовательно, со- гласно теореме максимальный поток равен 4. Разрез определен путем простого перебора. Логика его «лобового» поиска очевид- на. Осуществляем перебор по дугам путем генерации всех воз- можных подмножеств дуг. Для каждого подмножества дуг про- 4. Алгоритмы на графах 187 является ли оно разрезом. Если является, то его пропускную способность и сравниваем ее с минимальным значением. При положительном результате сравнения запоми- наем разрез и изменяем значение минимума. Удачный выбор данных позволяет сделать программный код компактным, но очевидно, что даже при наличии различных отсечений в перебо- ре метод применим только для небольших сетей. Однако, как найти максимальный поток, т. е. его распределение по дугам, по-прежнему открытый вопрос. «Техника меток» Форда и Фалкерсона заключается в после- довательном (итерационном) построении максимального пото- ка путем поиска на каждом шаге увеличивающейся цепи, то есть пути (последовательности дуг), поток по которой можно увеличить. При этом узлы (вершины графа) специальным обра- зом помечаются. Отсюда и возник термин «метка». Пример из работы [9]. Рядом с пропуск- ными способностями дуг указаны потоки, построенные на этих дугах. На рисунке по- ток через сеть равен 10 и увели- чивающаяся цепочка, выделенная «жирны- ми» линиями. Обра- тите внимание на ориентацию дуг, входящих в цепочку. По данной цепочке можно пропустить поток, равный 1, пропуск- ная способность дуги (5, 6). Изменяем суммарный поток, его значение становится равным Поток увеличен, необходимо продолжить поиск увеличивающихся цепочек; если окажется, что построить их нельзя, то результирующий поток максима- лен. Заметим, что для данного примера это значение потока окончательное. Обратите внимание на то, как изменен поток на дугах сети в зависимости от их ориентации. 4.9.2. Метод построения максимального потока в сети Рассмотрим метод на примере. Пусть дана сеть уз- лом-источником является вершина 1, узлом-стоком — вершина 6. Построим максимальный поток между этими вершина- ми. Начальное значение F нулевое. Очевидно, что структурой данных для описания F является матрица того же типа, что и матрица С, в которой определены пропускные способности дуг. 188 4. Алгоритмы на графах Первая итерация. Присвоим вершине 1 метку [1,@]. Пер- вый шаг. Рассмотрим дуги, началом которых является верши- на 1 — дуги (1,2) и (1,3). Вершины 2 и 3 не помечены, поэтому присваиваем им метки, для 2-й — [1,2] и 3-й — [1,6]. Что пред- ставляют из себя мет- ки? Первая цифра — номер вершины, из которой идет поток, вторая цифра — чис- ленное значение пото- ка, который передать по этой дуге. Второй шаг. Выберем помеченную, но не- просмотренную вер- шину. Первой в соот- ветствующей структуре данных записана вершина 2. Рассмотрим дуги, для которых она является началом — дуги (2,4) и (2,5). Вершины 4 и 5 не помечены. Присвоим им мет- ки — [2,2] и [2,2]. Итак, на втором шаге вершина 2 просмотре- на, вершины 3, 4, 5 помечены, но не просмотрены, остальные вершины не помечены. Третий шаг. Выбираем вершину 3. Рас- смотрим дугу (3,4). Вершина 4 помечена. Переходим к следую- щей вершине — четвертой, соответствующая дуга — (4,6). Вер- шина 6 не помечена. Присваиваем ей метку [4,2]. Мы достигли вершины-стока, тем самым найдя путь (последовательность дуг), поток по которым можно увеличить. Информация об этом пути содержит метки вершин. В данном случае путь или увели- чивающаяся цепочка Максимально возможный по- ток, который можно передать по дугам этого пути, определяет- ся второй цифрой метки вершины стока, то есть 2. Поток в сети стал равным 2. 4. Алгоритмы на графах 189 Вторая итерация. Первый шаг. Присвоим вершине 1 метку [1,@]. Рассмотрим дуги, нача- лом которых является помеченная вершина 1. Это дуги (1,2) и (1,3). Вершина 2 не может быть помечена, так как пропускная способность дуги (1,2) исчерпана. Вершине 3 присваиваем метку [1,6]. Вто- рой шаг. Выберем помеченную, но не просмотренную вершину. Это вершина 3. Повторяем действия. В результате вершина 4 получает метку [3,2]. Третий шаг. Выбираем вершину 4, толь- ко она помечена и не просмотрена. Вершине 6 присваиваем метку [4,1]. Почему только одна единица потока? На предыду- щей итерации израсходованы две единицы пропускной способ- ности данной дуги, осталась только одна. Вершина-сток достиг- нута. Найдена увеличивающая поток цепочка, это по которой можно «протащить» единичный поток. Результиру- ющий поток в сети равен 3. Третья итерация. Вершине 1 присваиваем метку [1,@]. Первый шаг. Результат — метка [1,5] у вершины 3. Вто- рой шаг — метка [3,1] у вершины 4. Третий шаг. Пропускная способность дуги (4,6) израсходована полностью. Однако есть обратная дуга (2,4), по которой передается по- ток, не равный нулю (обратите внимание на текст, выделенный курсивом — «изюминка» метода). Попробуем перераспреде- лить поток. Нам необходимо передать из вершины 4 поток, равный единице (зафиксирован в метке вершины). Задержим единицу потока в вершине 2, то есть вернем единицу потока из вершины 4 в вершину 2. Эту особенность зафиксируем в метке вершины 2 — [-4,1]. Тогда единицу потока из вершины 4 мы передадим по сети вместо той, которая задержана в вершине 2, а единицу потока из вершины 2 попытаемся «протолкнуть» по сети, используя другие дуги. Итак, вершина 4 просмотрена, 190 Алгоритмы на графах вершина 2 помечена, вершины 5 и 6 не помечены. Четвертый и пятый шаги очевидны. Передаем единицу потока из вершины 2 в вершину 6 через вершину 5. Вершина-сток достигнута, найде- на цепочка по которой можно передать по- ток, равный единице. При этом по прямым дугам поток увели- чивается на единицу, по обратным — уменьшается. Суммарный поток в сети — 4 единицы. Четвертая итерация. Вершине 1 присваиваем метку [1,@]. Первый шаг. Помечаем вершину 3 — [1,4]. Второй шаг. Рас- сматриваем помеченную, но не просмотренную вер- шину 3. Одна дуга — (3,4). Вершину 4 пометить не можем — пропускная спо- собность дуги исчерпана. Помеченных вершин больше нет, и вершина-сток не достигну- та. Увеличивающую поток цепочку построить не можем. Най- ден максимальный поток в сети. Можно заканчивать работу. Итак, в чем суть «техники меток» Форда и Фалкерсона? Первое. На каждой итерации вершины сети могут находиться в одном из трех состояний: вершине присвоена метка, и она про- смотрена; вершине присвоена метка, и она не просмотрена, то есть не все смежные с ней вершины обработаны; вершина не имеет метки. Второе. На каждой итерации мы выбираем поме- ченную, но не просмотренную вершину v и пытаемся найти вершину и, смежную с которую можно пометить. Помечен- ные вершины, достижимые из вершины-источника, образуют множество вершин сети G. Если среди этих вершин окажется вершина-сток, то это означает успешный результат поиска це- почки, увеличивающей поток, при неизменности этого множе- ства работа заканчивается — поток изменить нельзя. Алгоритм. Входные данные. Описание сети матри- цей пропускных способностей C[1..N,1..N], где N — количество вершин. Вершина-источник s и вершина-сток t. Выходные дан- ные. Поток, описываемый матрицей F[1..N,1..N]. Рабочие пере- менные. Структура данных для хранения меток — P[1..N,1..2]. Элемент P[i,l] — номер вершины, из которой можно передать поток, равный P[i,2J, в вершину с номером i. Логическая пере- менная Lg, значение — есть цепочка, увеличивающая по- ток, False — нет. 4. Алгоритмы на графах 191 Основная логика. Begin <ввод данных и инициализация >; While Lg Do Begin расстановки если вершину t не смогли пометить, то Lg:=False; результат работы - значение Р (метки вершин) >; If Lg Then <процедура - изменение потока по дугам найденной цепочки от вершины-стока t до вершины-источника s; входные данные - массив Р, результат - измененный массив F>; End; <вывод потока F> ; End.(конец Уточним логику расстановки меток (не лучший вариант). Procedure Var M:Set Of 1. 1 -.integer; Begin M: = вершины. *} метку *} While And Lg Do Begin For i:=l To N Do непомеченной вершины. *} If And ((C[l,i]<>0) Or (C[i,l]<>0)) Then If F[l,i] прямая?*) If P[l,2] Else End Else If F[i,l]>0 Then обратная?*) If Then Else End; M:=M- [1] ; { *Вершина с номером 1 1 :=1; { *Находим помеченную и непросмотренную вершину. *} 192 Алгоритмы на графах Repeat Inc(l) Until (1>N) Or ((P[l,l]<>0) And (1 In M) ) ; If 1>N Then End; End; Логика изменения потока F имеет вид: Procedure Stream Begin тип дуги - прямая или обратная, знак минус у номера вершины - признак обратной дуги. *} If Then Else ) ]-P[t,2]; If Then не то переход к предыдущей вершине цепочки. *} End; End; Итак, рассмотрение метода построения максимального пото- ка в сети завершено. 4.9.3. Наибольшее паросочетание в двудольном графе Паросочетанием в неориентированном графе G=(V,E) назы- вается произвольное множество ребер такое, что никакие два ребра из М не инцидентны одной вершине. Вершины в G, не принадлежащие ни одному ребру паросочетания, называют свободными. Граф G называют двудольным, если его множест- во вершин можно разбить на непересекающиеся множества — причем каждое ребро имеет вид где Двудольный граф будем обозначать Задача нахождения наибольшего паросочетания в двудоль- ном графе сводится к построению максимального потока в неко- торой сети. Рассмот- рим схему сведения. На рисунке показан исходный двудольный граф G. Построим сеть S(G) с источником s и стоком t следующим образом: 4. Алгоритмы на графах 193 • источник s соединим дугами с вершинами из множества X; • вершины из множества Y соединим дугами со стоком • направление на ребрах исходного графа будет от вершин из X к вершинам из Y; • пропускная способность всех дуг Найдем максимальный поток из s в t для построенной сети. Он существует [18]. Насыщенные дуги потока (они выделены «жирными» линиями на рисунке) соответствуют ребрам наибо- льшего паросочетания исходного графа. Найденное наибольшее паросочетание не единственное. Проверьте, это ли паросочета- ние получается при помощи алгоритма нахождения максималь- ного потока. Найдите другие паросочетания. Рассмотрим другой метод построения наибольшего паросо- четания в двудольном графе. Введем понятие чередующейся це- пи из X в Y относительно данного паросочетания М. Произво- льное множество дуг вида: ..., где все вершины различны, — сво- бодная вершина в X, — свободная вершина в и каждая вторая дуга принадлежит М, то есть Теорема [18]. Паросочетание М в двудольном графе G наибо- льшее тогда и только тогда, когда в G не существует чередую- щейся цепи относительно М. Теорема подсказывает реальный путь нахождения наиболь- шего паросочетания. Пусть найдено некоторое паросочетание в графе G, на рисунке оно выделено «жирными» линиями. Ищем чередующуюся цепь — ее дуги выделены линиями со стрелка- ми. Она состоит из «тонких» дуг и «жирных», причем начи- нается и заканчивается в сво- бодных вершинах. Длина цепи нечетна. Делаем «тонкие» дуги «жирными» и наоборот. Паро- сочетание увеличено на едини- Общая логика. Begin <ввод и инициализация <найти первое While <есть чередующаяся цепочка> Do <изменить 194 4. Алгоритмы на графах результата>; End. Очередь за определением данных и последовательным уточ- нением логики. Граф описывается матрицей A[N,M], где N — количество вершин в множестве X, а М — в Y. Паросочетание будем хранить в двух одномерных массивах XN и УМ. Для рас- смотренного примера и Уточнение фрагмента «найти первое паросочетание» не требует разъясне- ний. Можно начать и с одного ребра в первом паросочетании, но в этом случае количество итераций в основной логике возраста- ет. For i:=l N Do Begin {*Назначение переменных i, j , очевидно. *} j While (j<=M) And Do Begin If And (YM[j]=0) Then Begin XN[i] :=i; ; End; Inc(j) ; End; End; Как лучше хранить чередующуюся цепочку, учитывая требова- ние изменения паросочетания и продумывая логику её построе- ния? Естественно, массив, пусть это будет Chain:array[l..NMmax] of где — максимальное число вершин в графе, и его значение для рассмотренного примера равно [1, -4, 4, -2, 3, -3], т. е. вершины из множества YM хранятся со знаком минус (вспомните метод построения максимального потока). Итак, поиск чередующейся цепочки. Function Var Begin в частности <нахождение свободной вершины в XN>; If <вершина не найдена> Then Else Begin первой свободной вершины>; Repeat вершина из Chain>; For <для всех вершин, связанных с r> Do 4. Алгоритмы на графах 195 If из XN> Then Begin If <ребро Then ребро в End Else Begin If <ребро "толстое"> Then ребро в End; Until все вершины из Chain> or <текущая вершина принадлежит YM, и она свободна>; вершина принадлежит YM, и она свободна>; End; End; Процесс дальнейшего уточнения логики вынесем в самосто- ятельную часть работы. 4.10. Методы приближенного решения задачи коммивояжера 4.10.1. Метод локальной оптимизации Попытаемся отказаться от перебора вариантов при решении задачи о поиске циклов или, если граф «нагру- женный», о поиске путей коммивояжера. При больших размер- ностях задачи (значение N) переборные схемы не работают — остаются только приближенные методы решения. Суть прибли- женных методов заключается в быстром поиске первого реше- ния (первой оценки), а затем в попытках его улучшения. В мето- де локальной оптимизации в этих попытках просматриваются только соседние вершины графа (города) найденного пути. Шаг 1. Получить приближенное решение (первую оценку). Шаг 2. Пока происходит улучшение решения, выполнять следующий шаг, иначе перейти на шаг 4. Шаг 3. Для всех пар номеров городов i,j, удовлетворяющих неравенству проверить: для смежных городов, т. е. для несмежных городов. Примечание На рисунке даны графические иллюстрации первого и второго не- равенств. «Жирными» линиями обозначены участки старых марш- рутов, — 196 4. Алгоритмы на графах Если одно из неравенств выполняется, то найдено лучшее решение. Следует откорректировать ранее найденное решение и вернуться на шаг 2. Шаг 4. Закончить работу алгоритма. Для реализации логики достаточно матрицы расстояний (А) и массива для хранения пути коммивояжера (Way). Вид общей логики: Begin из файла матрицы расстояний, инициализация глобальных *} первого варианта пути *} оптимизация. *} результата. *} End. Продолжим уточнение логики. Работа процедур Init, One- Way, Out достаточно очевидна. Естественным приемом являет- ся вынесение ее в самостоятельную часть работы школьников на занятии. Нам необходимо уточнить процедуру Local. Работа- ем не с частностями, а на содержательном уровне. Предполо- жим, что мы имеем функции и Best2, их параметры — индексы элементов массива Way, определяющих номера горо- дов в пути коммивояжера, а выход естественный — истина или ложь, в зависимости от того, выполняются неравенства или нет. Рассуждаем дальше. Если неравенство выполняется, то нам необходимо изменить путь (соответствующие элементы массива Way). Пока не будем заниматься деталями. Пусть эту работу выполняет процедура Swap, ее параметры — индексы элементов массива Way). Эта процедура, вероятно, должна со- общать о том, что она «что-то изменила», ибо нам необходимо продолжать работу до тех пор, пока что-то меняется, происхо- дят улучшения. Итак, логика процедуры Local. 4. Алгоритмы на графах 197 Procedure Local; Var Change '.Boolean; функции и Best2, а также процедура Swap>; Begin Repeat For i:=l To Do For To N Do If Then Begin If Then Swap (i,j);End Else If And (j=N) Then Begin If Bestl (i,j) Then End {*Об этой проверке лучше первоначально умолчать, чтобы было о чем спросить, "если совсем будет плохо" - все понимают и нет *} Else If Best2 (i,j) Then Swap(i,j); Until логики неясно - кто изменяет значение переменной Change на True. Определите, учитывая, что функции Best2 и процедура Swap локальные по отношению к процедуре Local.*} End; 4.10.2. Алгоритм Эйлера Этот алгоритм и следующий работоспособны в том случае, если выполняется неравенство треугольника. Его суть в том, что для любой тройки городов i, (между которыми есть связь) выполняется неравенство Рассмотрим идею алгоритма. Шаг 1. Строится каркас минимального веса (алгоритмы Прима или Краскала). Примечание. Это не есть первое прибли- жение, как в предыдущем алгоритме. Шаг 2. Путем дублирования каждого ребра каркас преобра- зуется в эйлеров граф. Шаг 3. Находим в построенном графе эйлеров цикл. Шаг 4. Эйлеров цикл преобразуем в гамильтонов цикл (или маршрут коммивояжера). Метод преобразования: последовате- льность вершин эйлерова цикла сокращается так, чтобы каж- дая вершина графа в получившемся цикле встречалась ровно один раз. 198 4. Алгоритмы на графах Шаг 5. Закончить работу алгоритма. Получено приближен- ное решение задачи коммивояжера. Покажем, что стоимость приближенного решение CostAp не превосходит удвоенной стоимости оптимального решения Cost- Bet. Пусть стоимость каркаса — CostFr. Тогда так как при удалении из оптимального пути коммивояжера ребра получаем каркас с весом не большим, чем CostAp. Из пра- вила построения эйлерова графа получаем, что вес построенного эйлерова цикла Неравенство треугольника обеспечива- ет результат: следующую оценку шага 4 — a значит, . Рассмотрим пример. Для исходных данных (из п. 3.2), приведенных в таблице, на рисунке «жирными» линиями выделен каркас минимально- го веса. В таблице выделены те ребра графа, которые включа- ются в каркас с помощью алгоритма Прима. Последователь- ность включения ребер в каркас: (8,9), (8,1), (9,2), (1,7), (7,5), (5,10), (10,6), (1,3) и (3,4). «Тонкие» линии добавляются на 4. Алгоритмы на графах 199 шаге 2. Получаем эйлеров граф. Затем эйлеров цикл (его стои- мость 244) преобразуется в путь коммивояжера (шаг 4). Соглас- но неравенству треугольника мы получаем: Суммируя левые и правые части не- равенств, получаем: Аналогичные пре- образования осуществляются и для других фрагментов щения эйлерова цикла. Для рассмотренного примера CostAp равна 202. Оцените, насколько стоимость этого маршрута боль- ше стоимости оптимального. Структуры данных. Помимо названных ранее массивов А — матрица расстояний и массива Way — хранение искомого пути, требуется «что-то» для хранения описания каркаса. |