Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 145
Текст из файла (страница 145)
Кратчайшие пути из одной вершины 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. Кратчайшие пути из одной вершины 707 (Роп1) [93]. Беллман описывает, какое отношение имеют кратчайшие пути к разностным ограничениям. Лоулер (?.ач!ег) [196] описывает алгоритм с линейным временем работы для поиска кратчайших путей в ориентированном ациклическом графе, который он рассматривает как часть "народного творчества".
Если вес каждого из ребер выражается сравнительно малыми неотрицательными целыми числами, задача о кратчайших путях из одной вершины решается с помощью более эффективных алгоритмов. Последовательность значений, возвращаемых в результате вызовов процедуры Ехтклст М1и в алгоритме Дейкстры, монотонно возрастает со временем. Как говорилось в заключительных замечаниях к главе 6, в этом случае существует несколько структур данных, позволяющих эффективнее реализовать различные операции над очередями с приоритетами, чем бинарная пирамида или пирамида Фибоначчи. Ахуя (АЬп]а), Мельхорн (МеЬ)Ьотп), Орлин (Ог1ш) и Таржан (Тат]ап) [8] предложили для графов с неотрицательными весами ребер алгоритм со временем работы 0 (Е+ Ъ'~(ТдУ), где И' — максимальный вес ребра графа. Наилучшие границы достигнуты Торупом (ТЬогир) [299], который предложил алгоритм со временем работы 0(Е1818Ъ'), и Раманом (йшпап) [256], чей алгоритм имеет время работы 0(Е + Ъ' ш1п((18 Ъ')1/з+', (18 И')1~4+')).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
