Алгоритмы - построение и анализ (1021735), страница 144
Текст из файла (страница 144)
Затем множество ребер Е разбивается на множества Еу И Еь, где Еу = ((о;, иу) Е Е: 1 ( )') и Еь = ((о;, оу) б Е: г' ) Я. (Предполагается, что граф С не содержит петель, так что каждое ребро принадлежит либо множеству Еу, либо множеству Еь.) Определим графы Су = (К Еу) и Сь = (К Еь). а) Докажите, что Су — ациклический граф с топологической сортировкой (оы сз,..., оу)), а Сь — ациклический граф с топологической сортировкой (и)) ),о)ч) ы..., о1), Предположим, что каждый проход Беллмана-Форда реализуется следующим образом. Сначала вершины обходятся в порядке сыоз,..., о)ь у и при этом ослабляется каждое ребро графа Еу, исходящее из посещаемой вершины.
Затем вершины обходятся в порядке с)ь ус)ч~ ы..., ип и при этом ослабляется каждое ребро графа Еь, исходящее из этой вершины. б) Докажите, что при такой схеме, если граф С не содержит циклов с отрицательным весом, достижимых из истока в, то после ПЦ/21 проходов по ребрам И [с) = б (в, с) для всех вершин п е У. в) Улучшает ли эта схема асимптотическое поведение времени работы алгоритма Беллмана-Форда? 24-2. Вложенные ящики Говорят, что д-мерный ящик с размерами (хм хз,..., хв) вкладывается (пез1з) в другой ящик с размерами (уы уз,..., Ув), если существует такая перестановка я индексов (1, 2,..., Н), что выполняются неравенства хл(1) < Уы хл(2) < Уз» х~г(н) < Ув. а) Докажите, что вложение обладает свойством транзитивности. б) Разработайте эффективный метод определения, вкладывается ли один Н-мерный ящик в другой.
в) Предположим, что задано множество, состоящее из и д-мерных ящиков (Вы Вз,..., В„). Разработайте эффективный алгоритм, позволяющий найти самую длинную последовательность ящиков (В,„ В;„..., В;,) такую, что для у = 1, 2,..., й — 1 ящик В;з вкладывается в ящик В;з+,. Выразите время работы этого алгоритма через и и Н. Глава 24. Кратчайшие пути из одной вершины 703 24-3. Арбитражные операции Арбитражные операции (агЬ11гаде) — это использование различий в текущем курсе валют для преобразования единицы валюты в большее количество единиц этой же валюты. Например, предположим, что за 1 американский доллар можно купить 46.4 индийских рупий, за одну индийскую рупию можно купить 2.5 японских иен, а за одну японскую иену— 0.0091 американских долларов.
В этом случае в результате ряда операций обмена торговец может начать с одного американского доллара и купить 46.4 х 2.5 х 0.0091 = 1.0556 американских долларов, получив таким образом доход в размере 5.56;4. Предположим, что даны п валют емсз,...,с„и таблица )1 размером и х и, содержащая обменные курсы, т.е.
за одну единицу валюты с; можно купить Л 1ю', Я единиц валюты с . а) Разработайте эффективный алгоритм, позволяющий определить, существует ли последовательность валют (с;„с;2,..., с;„), такая что В(гцкз] В(гз,1з] 'ВЬ-~ 1ь] В[тьт1]) 1. Проанализируйте время работы этого алгоритма. б) Разработайте эффективный алгоритм поиска такой последовательности, если она существует. Проанализируйте время работы этого алгоритма. 24-4. Алгоритм Габова для масштабирования кратчайших путей из одной вершины Алгоритм масштабирования (зса11пя) решает задачу, сначала рассматривая толью старший бит каждой соответствующей входной величины (такие как вес ребра).
Затем начальное решение улучшается за счет рассмотрения двух старших битов. После этого последовательно рассматривается все большее число (старших) битов, в результате чего каждый раз решение улучшается до тех пор, пока не будут рассмотрены все биты, и не будет найдено правильное решение. В этой задаче исследуется алгоритм поиска кратчайших путей из одной вершины путем масштабирования весов ребер.
Нам дан ориентированный граф С = ( г', Е), веса ребер в котором выражаются неотрицательными целыми величинами и. Введем величину И~ = шах(„„)ал (тс (и, о)). Наша цель — разработать алгоритм, время работы которого составляет О (Е 16 И"). Предполагается, что все вершины достижимы из истока. В алгоритме последовательно по одному обрабатываются биты, образующие бинарное представление весов ребер, начиная с самого старшего к самому младшему. В частности, пусть й = ~16(И'+ 1)] — количество битов в бинарном представлении величины И', и пусть ии (и, о) = Часть Ч1 Алгоритмы для работы с графами 704 = '(ю(и, и)/2" '~, где 1 = 1,2,..., й.
Другими словами, ю; (и, и) — "масштабированная" версия ю (и, и), полученная из г старших битов этой величины. (Таким образом, для всех ребер (и, и) Е Е юь (и, и) = ю (и, и).) Например, если 1с = 5 и ю (и, и) = 25 (бинарное представление которого имеет вид (11001)), то юз (и, и) = (110) = 6. Другой пример с lс = 5: если ю(и, и) = (00100) = 4, то юз (и, и) = (001) = 1. Определим величину Б; (и,и) — вес кратчайшего пути из вершины и в вершину и, вычисленный с помощью весовой функции ю;.
Таким образом, для всех вершин и, и е У бь (и, и) = б (и, и). Для заданного истока з в алгоритме масштабирования для всех вершин и е Ъ' сначала вычисляются веса кратчайших путей Б1 (з,и), затем для всех вершин вычисляются величины Бз (з, и) и т.д., пока для всех вершин и е Ъ" не будут вычислены величины бь (з, и). Предполагается, что (Е~ > )Ц вЂ” 1. Как вы увидите, вычисление величины б; на основании Б; 1 требует О (Е) времени, так что время работы всего алгоритма — О (йЕ) = О (Е 1я И'). а) Предположим, что для всех вершин и е У выполняется неравенство б(з,и) < ~Е~.
Покажите, что величину Б(з,и) для всех вершин можно вычислить в течение времени О (Е). б) Покажите, что величину Б1 (з,и) для всех вершин и е У можно вычислить в течение времени О (Е). Теперь сосредоточим внимание на вычислении величины б;, зная вели- чину Б; 1. в) Докажите, что при 4 = 2,3,..., й выполняется либо равенство ю; (и,и) = 2ю; 1(и,и), либо равенство ю;(и,и) = 2ю; 1(и,и)+1. Затем докажите, что для всех вершин иеУ справедливы неравенства 2Б; 1 (з, и) < б;(з, и) < 2б1 т (з, и) + )Ц вЂ” 1.
г) Определим для г = 2, 3,..., й и всех ребер (и, и) й Е величину ю; (и, и) = ю; (и, и) + 2Б; 1 (з,и) — 2б; 1 (з, и) . Докажите, что для г = 2,3,...,й и всех и,и е У значение ю;(и,е) представляет собой неотрицательное целое число. д) Теперь определим величину б; (з, и) как вес кратчайшего пути из истока з в вершину и, полученного с помощью весовой функции ю,.
Докажите, что для 4 = 2, 3,..., Й и всех вершин и е У выполняется равенство б; (з, и) = б; (з, и) + 2б; 1 (з, и) и что Б; (з, и) < (Е). Глава 24. Кратчайшие пути из одной вершины 705 е) Покажите, как вычислить величину б;(з,с) на основе величины б, 1 (з, о) для всех вершин о Е У в течение времени О (Е) и обоснуйте вывод о том, что вычислить б(з, ю) для всех вершин о Е У можно за время 0 (Е 1к 1У). 24-5. Алгоритм Карпа для поиска цикла с минимальным средним весом Пусть 0 = (У, Е) — ориентированный граф с весовой функцией ю: Е-+ В., и пусть и = Щ. Определим средний вес (шеап не(я1н) цикла с = (еы ез,..., еь), состоящего из ребер множества Е, как Пусть р' = ппп, р (с), где с охватывает все ориентированные циклы графа С.
Цикл с, для которого выполняется равенство р (с) = р', называется циклам с минимальным средним весам (ппшшшп шеап-тче(яМ сус1е). В этой задаче исследуется эффективный алгоритм вычисления величины И. Без потери общности предположим, что каждая вершина о Е У достижима из истока з Е У. Пусть б (з, о) — вес кратчайшего пути из истока з в вершину о, а бь (з, ю) — вес кратчайшего пути из истока з в вершину ю, содержащего ровно й ребер. Если такого пути не существует, то бь(з,о) = со.
а) Покажите, что если (з' = О, то граф С не содержит циклов с отрицательным весом, и б (з, ю) = гпшо<а<„з бь (з, о) для всех вершин ю Е У. б) Покажите, что если и' = О, то б„(з, ю) — бь (з, о) о<а< -т п — Й для всех вершин о Е У. (Указание: воспользуйтесь обоими свойствами из части а.) в) Пусть с — цикл с нулевым весом, а и и ю — две произвольные вершины в этом цикле. Предположим, что и" = О, и что вес пути из вершины и в вершину о вдоль цикла равен х.
Докажите, что б (з, о) = б (з, и) + х. (Указание: вес пути из вершины ю в вершину и вдоль цикла равен -х.) Часть Ч1. Алгоритмы для работы с графами 706 г) Покажите, что если д' = О, то в каждом цикле с минимальным средним весом существует вершина с такая, что б„(а, и) — б» (з, о) шах О<»< -1 П вЂ” Й (Указание: покажите, что кратчайший путь в каждую вершину, принадлежащую циклу с минимальным средним весом, можно расширить вдоль цикла к следующей вершине цикла.) д) Покажите, что если и' = О, то б„(е, о) — б» (е, о) ппп шах вет' 0(~»((ь-1 и — к е) Покажите, что если к весу каждого ребра графа С добавить константу т, то величина д' увеличится на т.
Покажите с помощью этого факта справедливость соотношения ояк 0(Мп — 1 и — Й ж) Разработайте алгоритм, позволяющий вычислить величину и* за время О (У Е). 24-6. Битонические кратчайшие пути Последовательность называется битоничеекой (Ьйоп1с), если она монотонно возрастает, а затем монотонно убывает, или если путем циклического сдвига ее можно привести к такому виду. Например, битоническими являются последовательности (1,4,6,8,3, — 2), (9,2, — 4, — 10, — 5) и (1, 2, 3, 4), но не (1, 3, 12, 4, 2, 10). (См. также главу 27 и задачу 15-1.) Предположим, что задан ориентированный граф С = (К Е) с весовой функцией ю: Е -+ В., и нужно найти кратчайшие пути из одной вершины в.
Имеется также дополнительная информация: для каждой вершины и 6 У веса ребер вдоль произвольного кратчайшего пути из истока е в вершину о образуют битоническую последовательность. Разработайте наиболее эффективный алгоритм, позволяющий решить эту задачу, и проанализируйте время его работы. Заключительные замечания Алгоритм Дейкстры (131)Юга) (75) появился в 1959 году, но в нем не содержалось никаких упоминаний по поводу очереди с приоритетами. Алгоритм Белл- мана-Форда основан на отдельных алгоритмах Беллмана (Ве!1тап) (351 и Форда Глава 24.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
