Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 37

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 37)

М., Рараднпйпои С Н. Оп Ипеа< спагас(епхаИопэ о1 сопзЫпа(она) орИгп!хз(!оп ргоЫешэ, Ргос. 2!з( Апина! Вушрозшш оп Роипда(юпэ о! Согпри1ег 5с<епсе, 1ЕЕЕ (1980), ! — 9. [ОЬ5! Ого(эсйе! М., Ьочаэз)., Вс!пцче< А ТЬе сИ)рэо)д пзерпод апд Иэ сопзейи. елось !и соп<Ыпа!ог)а! ор(нп(ха!оп, Кери<! 80 — 151 — ОК, Бп(ч о1 Вопп, 1980. В следующей главе мы построим полнномиальный алгоритм для частного случая задачи ЛП, а именно задачи о максимальном потоке нэ гл. 6.

Однако в отличие от алгорн<ма эллнпсоидов число оперзцнй в э<ам,<л<орнтме ограничено полиномом от числа целых «исе.< во входе (а не,< их суммарной длины). Назовем такой алга- ритм <илько налинамиа»ьным, если он к <ому же полниомиален з обычном смысле (з . если шола, учас<ву<ощие в эрнцзмсцн[згских операциях, не экспоненциальны). Важный отнрьпый вопрос, связанный с алгоритмом элляпсоидов: имеется ли сильно полнномнальный злгорнзм для задачи ЛП7 Прим~ром такого алга. рнгмз мог бы служить симплекс-алгоритм с правилом замещения, гарантирующим заверш<нне алгоризма посл~ полнномиат ного (отн<кнтельно т и л) числа замещений Резулшз<ы иэ й 8.6 н рати (де[, (уа)! и [Ва2! не исключают возможности существования <акозо ирнзнла ээл<енизн<я Как недавно отметил Заде, длн следующего нрнвлеказсльног < правила юмешення не известно экспоненциального кон <рпрпмера «( ргдн всех столбцов, для к<порых г (О, выбрать тот, который до этого момент,< и»ныне всего раз входил н базис» Сил~но полиномнального алгоритма не нзнестэо даже для неиосредсз венного обобщенна задачи о максимальном потоке — задачи о по~оке минимальной стоимости иэ гл.

7 (слз. «Комиентарин н ссылки< к гл 7) В гл !6 будут обсуждшься лстданалинамиальные алгоригл<ы — понятие, прямо противоположное сильно полиномиальным алгоритмам <(окаэазельс<во неразрешимости проблем, определенных в задаче 2, можно найти в гл 6 книги [1.Р! 1 ек В Н.

К., Рарадпнйпои С. Н. Е)ешепы о( Гпе Гпеогу о1 согпри(аИоп. Епй)е<чоод С![Па, Х 1: РгепИсе.НаИ РиЫВ!)пй Со., !пс., 1981. То, что процедура ог»ращения ма грины, известная нак метод исключения Гаусса, в применении к целочисленным магрнцим является полиномиальным алгоритмом (см доказательство теоремы 8.2), следует нз того факта, что все промежуточные резульгаты в ней — рациональные числа, числизелн и знаменатели которых равны подонределнтелям исходной матрицы; см.

[Га! Гантмахер Ф, Р. Теория матриц. — 3-< нэд. — Мл Мнр, 1967, гл. 2, Доказательство гого, что имеется н"-' осзовных деревьев с о вершииамн (пример 2), см. в гл 2 книги ') [Еч! Ечеп Б, Огарй а!дог)Инпэ Ро1огпас, Магу!апд: СозпрЫег 5с<епсе Ргезз, 1979. ') См также: Оре О. Теория графов.

11ер, с англ.— 2.е изд.— Мл Наука, 1980, с. 79.— Прим. перез. Эффективные алгоритмы длв задачи о максимальном потоке В предыдущей главе был введен формальный метод описания эффективности алгоритмов, позволяюгций оценивать поведение любого алгоритма с единых математических позиций. Заметим, что, согласно жестким критериям этого подхода, симплекс-алгоритм для линейного программирования не являезся «хорошим», хотя это очень умный и пракхичсски полезный алгоритм.

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

Э»от алгорцгм не ~олько регцае~ задачу о максимальном потоке, но и можег быть адапгирован для эффективного решения некоторых других интересных комбинаторных задач оптимизации. Рассмотрим вначале фундаментальный алгоритм для работы с графами, называемый ПОИСК.

Различные варианты этого алгоритма составляю~ основу многих алгоритмов па графах, описанных в этой и последующих главах, а также элементарного алгоритма пометок из гл. б. 9.1 Поиск по граФу Граф 6=(г', Е) представляется списками смежностей А (и), и Б )г (см. пример 8.5). Как всегда, мы считаем, что 1Е~)(Ц!2, предполагая, например, что в 0 нет изолированных вершин. Рассмотрим алгоритм ПОИСК, приведенный на рис.

9.1. Он основан на следующей идее. Начинаем с вершины и, и «помечаем» ее. Далее, проделываем то же самое для вершин, смежных с оп затем для вершин, смежных с этими вершинами, и т. д. В множестве Д храним список всех вершин, козорые можно помети1ь — т. е. тех вершин, которые смежны с уже помеченными вершинами и сами Угд Поиск по графУ еще не помечены. Процесс останавливается, когда (е становится пустым. Теорема 9.1. Алгоритм ПОИСК, приведенный на рис. 9.1, помечает все вершины графа О, соединимые путем с о„за время 0((Е)). Доказатпельство.

Предположим, что вершина о соединима путем с о,. Индукцией по длине этого пути можно показать, что о будет АЛГОРИТМ ПОИСК Вход. Граф С, представленный списками смежностей; вершина чь Выход. Тот же граф, но в котором вершинин достижимые иэ чт по некоторому пути, >помечены>. Ьед1п , :О:= (ч,);,: пЫ!е С) ж и Во Ьей1п пусть ч — проиэвольпый элемент иэ ь); удалить ч нэ О; пометить ч 1ог эи ч'ЕА(ч) йо Н ч' не помечена гьеп добэвить ч' к сг;,: епо' епв Рис. 9Л. Алгоритм ПОИСК.

помечена. Пусть, с другой стороны, не существует пути из о, в о. Тогда также простой индукцией по числу выполнений цикла вЫ!е в алгоритме ПОИСК можно показать, что о не будет помечено. Для доказательства временной оценки заметим, что сложность алгоритма ПОИСК складывается из трех частей, 1.

Начальный шаг; он использует постоянное время. 2. Работа с множеством 0; добавление и удаление элементов множества 0 производится ие более 2~Ц раз. Каждое добавление или удаление можно выполнить с помощью двух или трех элементарных операций (рис. 9.2 и 9.4); отсюда следует оценка 0(Я). 3. Поиск по спискам смежностей; при этом для любого элемента любого списка смежностей производится постоянная работа. Так как сумма длин списков смежностей равна 2(Е(, то в целом требуется время 0((Е().

Суммарно получаем оценку 0(~Е(). Г 1 Пример 9.1. Алгоритм ПОИСК можно использовать для проверки связности графа: граф 6 связен в том и только в том случае, если после применения к нему алгоритма ПОИСК все вершины будут помечены. Так же непосредственно ПОИСК можно использовать Гл. Р. Задача о максимальном ног»оке 200 для нахождения связных компонент (максимальных связных подграфов) графа 6 (см. задачу 1). Алгоритм ПОИСК, представленный на рис.

9.1, не полностью определен. Необходимо точно определить, как выбирается элемент и лоб»ннтв и и (1 Уда»нтв о из Гр л р»и»»»П»ср»ь» ч! л»сл»М»» .. »»»»зссч!а» ! Г(»,сс»зв»»Г ): п (а) р! =- !еЬ н»р»»нг1 И) реый 2 с»ел»З»ье = 7 Г<»лсржпмос () в пор»л»с пс»с»у»» »си н» (а) Рис. 9.2. Программы, реализующие Гр в виде очереди. Перемепныь! носледний и первый вна. чале присвапваетсн значение нуль; !! — массив с 1У1 элементами.

!) пусса тогда и только тогда, когда первый = последний. пш пг (в скобка») Рис. 9.3. проста: представим себе, что Я вЂ” это реальная линия ожидания (очередь)) и что всегда удаляется вершина, которая ожидала дольше всех, Это правило можно легко реализовать с помощью двух из Я в цикле м»Ы!е. Для этого можно применять несколько правил; например, можно всегда выбирать элеменг множества Я, имеющий наименьший индекс.

Однако одна из возможных стоагегий особенно 20! РП. Поиск ло грос)у Добавить и к (2 Удалить и иа () и: () Гное«мной ) «ос«сан«« '. = ни«саго«« — ! нос«сеной!-" «ос«с го Н ! 0 (нос ммм ) (а) «ос«ганна =4 Содержимое () а порядке ггоь«уплснгся (в) Рнс. 9Л. Програлгмы, реалиауюгцие О в виде очереди, организованной по пршшипу: последним пришел — первым ушел (в виде стека) Вначале последний =- О. н2 — массив с (Ц нле. ментами, () пусто тогда н только тогда, когда последний = О. вне скобок). Заметим, что при поиске этого типа вершины посещаются в порядке возрастания длины кратчайшего пути до них из и, — отсюда и происходит название поиск в ширину (доказательство см. в задаче 3).

р) Другим вариантом поиска является поиск в глубину (ПГ), при котором работа с множеством Я производится по прнннипу последним пришел — первым ушел (рис. 9.4). Этот алгоритм производит проверку вглубь, продолжая некоторый путь как можно дальше и возвращаясь назад для выбора нового варианта только тогда, когда никакой новой вершины нельзя достичь из последней вершины рассматриваемого пути. Пример 9.2 (продолжение). На рис. 9.3 в скобках приведен порядок посещения вершин графа при использовании ПГ. ("4 Алгоритм ПОИСК можно также применять к орграфалс. Орграф ))=()г, А) тоже можно представлять списками смежностей: А(и) будет множеством всех таких вершин и' Е )с, что (о, о') Е А.

Заметим что с этой точки зрения графы — это просто частный случай орграфов, а именно это синлнетричныеорграфы, в которых и Е А (и) тогда и только тогда, когда пЕА (и). Таким образом, алгоритм ПОИСК простых программ (рис. 9.2). Такой вариант алгоритма ПОИСК называется поиск в ширину (ПШ). Пример 9.2. Применим ПШ к графу, представленному на рис.

9.3. Будем считать, что вершины в списке смежностей просматриваются в порядке возрастания индексов (это условие буден предполагаться обычно и в дальнейшем). Порядок, в котором помечаются вершины данного графа при использовании ПШ, приведен на рис. 9.3 (числа Гл. 9. Задача о маиоималвиом аооиже (и его частные случаи ПГ и ПШ) можно без каких либо изменений применять к орграфам. Пример 9.3. На рис.

Характеристики

Список файлов книги