Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 158
Текст из файла (страница 158)
Пусть р = (оо о1,..., оь), где оо = в и оь = о. Для 1 = 1,2,..., и выполняются соотношения она = б(в, о,) и о1.4 > гч 1.4 + 1о(о, 1,о;), из чего следует, что 1о(о1 1, о,) < б(в,о,) — б(з,о; 1). В результате суммирования весов вдоль нуги р получаем 716 Часть РТ Алгоритмы длл работы с графами атрибуту в. я присваивается значение„отличное от мпо то граф С содержит цикл с отрицательным весом. 24.5.5 Пусть С = (Ъ'„Е) представляет собой взвешенный ориентированный граф, не содержащий ребер с отрицательным весом, и пусть в б У вЂ” исток. Предположим, что в качестве шя может выступать предшественник вершины о на любом кратчайшем пути к вершине о из истока в, если вершина гг е 'и — 1в) достижима из вершины в; в противном случае гг. к принимает значение мш.
Приведите пример такого графа С и значений, юторые следует присвоить атрибутам гг, чтобы в графе С„образовался цикл. (Согласно лемме 24.16 такое присвоение не может быть получено в результате последовательности шагов ослаблений.) 24.5. 6 Пусть С = ('ьг, Е) представляет собой взвешенный ориентированный граф с весовой функцией ш: Š— > К, не содержащий циклов с отрицательным весом. Пусть в б У вЂ” исток, а граф С инициализируется процедурой 1ьптглшхнЯгьгпьп- Яоггксь(С, в). Докажите, что для каждой вершины о б У в графе С существует путь из вершины в в вершину о и что это свойство поддерживается как инвариант в ходе произвольной последовательности ослаблений.
24.5.7 Пусть С = (К Е) представляет собой взвешенный ориентированный граф, не содержащий циклов с отрицательным весом. Пусть также в б У вЂ” исток, а граф С инициализируется процедурой 1ьггтглшхк-бгмаьн-боггксн(С, в). Докажите, что существует такая последовательность ٠— 1 шагов ослабления, что для всех вершин о б У выполняется равенство гг. Н = б(в, е). Пусть С вЂ” произвольный взвешенный ориентированный граф, который содержит цикл с отрицательным весом, достижимый из истока в. Покажите, что всегда можно построить такую бесконечную последовательность этапов ослабления ребер графа С, что каждое ослабление будет приводить к изменению оценки кратчайшего пути. Задачи 24.1.
Улучшение Иена алгоритма Беллмена-Форда Предположим, что в каждом проходе алгоритма Беллмана-Форда ослабления ребер упорядочены следующим образом. Перед первым проходом вершины входного графа С = (Ъ; Е) выстраиваются в произвольном линейном порядке И, оз,..., о~~ р Затем множество РебеР Е РазбиваетсЯ на множества Е1 0 Еь, где Е1 = ((ггг, гу) Е Е: 1 ( з) и Еь = ((ог, еб) Е Е: г' > г). (Предполагается, что 717 Гаева 74 Кратчайшие нута ив одной вершины граф С не содержит петель, так что каждое ребро принадлежит либо множеству Е7, либо множеству Еь,) Определим графы С7 = (17, Е7) и Сь = (\7, Еь).
а Докажите, что С7 представляет собой ациклический граф с топологической сортировкой (сы из,..., с~то), а Сь — ациклический граф с топологической сортировкой (сурсу~ ы...,с1). Предположим, что каждый проход алгоритма Беллмана-Форда реализован следуюшим образом. Мы посешаем каждую вершину в порядке ш, 77з,..., с~ар ослабляя ребра Е7, покидающие эту вершину. Затем мы посещаем квкдую вершину в поРЯдке с~ь 0 о~~ ~ ы..., оы ослаблЯЯ РебРа Еь, покидающие этУ веРшинУ.
б. Докажите, что если при такой схеме граф С не содержит циклов с отрицательным весом, достижимых из источника в, то после всего лишь ПЪ'~ /21 проходов по ребрам для всех вершин с е Ъ' выполняется равенство о. И = б(в, и). в. Улучшает ли эта схема асимптотическое время работы алгоритма БеллманаФорда? 24.2. Вложенные боксы Говорят, что б-мерный бокс с размерами (хм хз,..., хд) вкладывается (пеата) в другой бокс с размерами (уы уз,..., уд), если существует такая перестановка я индексов (1, 2,..., 4), что выполняются неравенства х 0) < уп х 00 < уз, ..., Хв(д) < Уд. а.
Докажите, что вложение обладает свойством транзитивности. б. Разработайте эффективный метод определения, вкладывается ли один б-мерный бокс в другой. в. Предположим, что задано множество, состояшее из и штук И-мерных боксов (Вы Вз,..., В„). Разработайте эффективный алгоритм, позволяющий найти самую длинную последовательность боксов (В„, В,„..., В;„), такую, что для 7 = 1, 2,..., /с — 1 бокс В,, вкладывается в бокс ВЧ, Выразите время работы этого алгоритма через и и И. 24.3.
Арбитражные операции Арбитражные операции (агЬьпайе) — зто использование различий в текущем курсе валют для преобразования единицы валюты в большее количество единиц этой же валипы. Например, предположим, что за один американский доллар можно купить 49 индийских рупий, за одну индийскую рупию — 2 японские иены, а за одну японскую иену — 0.0107 американского доллара. В этом случае в результате ряда операций обмена торговец может начать с одного американского доллара и купить 49 х 2 х 0.0107 = 1.0486 американского доллара, получив, таким образом, доход в размере 4.86'Уо. Предположим, что даны и валют сы сз,..., с и таблица В размером п х и, содержащая обменные курсы, т.е.
за одну единицу валюты с; можно купить его, у] единиц валюты с . Части Гй Алгоритмы дла работы о графами 718 а. Разработайте эффективный алгоритм, позволяющий определить, существует ли последовательность валют (с„, с„,..., ~„), такая, что гг[гз, 1з] гг[гз, 1з] . гг[гь ы 1ь] гг[гь, 11] > 1 . Проанализируйте время работы этого алгоритма. б. Разработайте эффективный алгоритм поиска такой последовательности, если она существует.
Проанализируйте время работы этого алгоритма. 24.4. Алгоритм Габова маешгнабнровання кратчайших путей нз одной вершины Алгоритм масштабирования (зса11пй) решает задачу, сначала рассматривая только старший бит каждой соответствующей входной величины (такой, как вес ребра). Затем начальное решение улучшается за счет рассмотрения двух старших битов. После этого последовательно рассматривается все большее число (старших) битов, в результате чего каждый раз решение улучшается до тех пор, пока не будут рассмотрены все биты и не будет найдено правильное решение.
В этой задаче исследуется алгоритм вычисления кратчайших путей из одной вершины путем масштабирования весов ребер. Задан ориентированный граф С = (1г, Е), веса ребер в котором выражаются неотрицательными целыми величинами ю. Введем величину И' = шах1 „)ее (ю(и,и)). Наша цель — разработать алгоритм, время работы которого составляет 0(Е 1к И'). Предполагается, что все вершины достижимы из истока. В алгоритме последовательно по одному обрабатываются биты, образующие бинарное представление весов ребер, от самого старшего к самому младшему. В частности, пусть й = [16(Иг + 1)] — количество битов в бинарном представлении величины Иг и пусть ю,(и, и) = [ю(и, и)/2ь '] для ( = 1, 2,..., й.
Другими словами, ю;(и, и) — ммасштабированная" версия ю(и,и), полученная из ( старших битов этой величины. (Таким образом, для всех ребер (и, и) б Е выполняется юь(и, и) = ю(и, и).) Например, если й = 5 и ю(и, и) = 25 (бинарное представление этого значения имеет вид (11001)), то юз(и,и) = (110) = 6. Другой пример с й = 5 — если ю(и, и) = (00100) = 4, то юз(и,и) = (001) = 1. Определим величину б,(и, и) как вес кратчайшего пути из вершины и в вершину и, вычисленный с помощью весовой функции и~о Таким образом, бь(и, и) = б(и, и) для всех вершин и, и е И. Для заданного истока в в алгоритме масштабирования для всех вершин и е (г сначала вычисляются веса кратчайших путей б1(в,и), затем для всех вершин вычисляются величины бз(в, и), и так до тех пор, пока для всех вершин и е И не будут вычислены величины бь(з, и).
Предполагается, что ]Е] ) ]И] — 1. Как вы увидите, вычисление величины б, на основании б, 1 требует времени 0(Е), так что время работы всего алгоритма — 0(кЕ) = 0(Е 1к И'). а. Предположим, что для всех вершин и Е (г выполняется неравенство б(в, и) < ]Е]. Покажите, что величину б(в, и) для всех вершин можно вычислить за время 0(Е). 7!9 Глава 74. Кратчайшие кути ил одной вершины б.
Покажите, что можно вычислить бг(в, о) для всех о Е 17 за время 0(Е). Теперь рассмотрим вопрос вычисления б, из 6, г. а Докажите, что для г = 2,3,..., к мы имеем либо ш!(и,о) = 2ш; з(и, о), либо ш,(и,о) = 2ш; г(и,о) +1. Затем докажите, что 26! г(в, о) < б,(в, о) < 26, !(в, о) + ~Ц вЂ” 1 для всех о Е Ъ'. а Определим для г = 2, 3,..., /с и всех (и, о) Е Е ш!(и,о) = шг(и,о) + 26, 1(в,и) — 26, 1(в,о) Докажите, что для 1 = 2,3,...,)о и всех и,о е Ъ™перевешенное" значе- ние ш,(и,о) ребра (и,о) представляет собой неотрицательное целое число. д. Теперь определим 6,(в, о) как вес кратчайшего пути из в в о с использованием весовой функции ш,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
