Главная Промышленная автоматика.

*5.18. Покажите, что алгоритм нахождения кратчайшего пути из разд. 5.8 работает, когда некоторые ребра имеют отрицательную стоимость, но никакой цикл не имеет отрицательной стоимости. Что случится, если у какого-нибудь цикла будет отрицательная стоимость?

**5.19. Покажите, что положительные и отрицательные вещественные числа с +00 и -оо не образуют замкнутого полукольца. Как в этом свете объяснить упр. 5.18? Указание: Какие свойства замкнутого полукольца фактически используются в алгоритме 5.5?

5.20. Примените алгоритм 5.6 для нахождения кратчайшего расстояния от узла и, в каждый узел v графа G на рис. 5.37.

*5.21. Покажите, что задачу о нахождении кратчайшего пути из одного источника в случае неотрицательных стоимостей ребер для графа с е ребрами и п узлами можно решить за время О (е log п). Указание: Используйте подходящую структуру данных, чтобы строки 5 и 8 алгоритма 5.6 можно было эффективно вьшолнить при

**5.22. Покажите, что задачу о нахождении кратчайшего пути из одного источника в случае неотрицательных стоимостей ребер для графа с е ребрами и п узлами можно решить за время 0{ke+ -fftn + для любой фиксированной постоянной k.

begin

for veV-{v,} do D[v]l{v„, v); while 8ФУ do begin

выбрать такой узел wV-S, что D[w] принимает наименьшее значение; SSuH;

for vV, для которого D[v]>D[w]+l{w, v) do begin

D[v]D[w] + l(w, v); end

Рис. 5.38. Алгоритм нахождения кратчайшего пути из одного источника.



Рис. 5.39. Стоимости ребер для графа с 5 узлами.

*5.23. Докажите, что алгоритм нахождения кратчайшего пути, приведенный на рис. 5.38, строит кратчайший путь из Уо в каждый узел V произвольного графа, у которого могут быть ребра с отрицательными стоимостями, но циклов с отрицательными стоимостями нет.

*5.24. Каков порядок времени работы алгоритма, приведенного на рис. 5.38? Указание: Рассмотрите работу алгоритма на графе с 5 узлами, стоимости ребер которого указаны на рис. 5.39.

5.25. Постройте алгоритм, который распознавал бы, есть ли в данном ориентированном графе, ребрам которого приписаны положительные и отрицательные стоимости, цикл отрицательной стоимости.

5.26. Измените правило выбора узла w в алгоритме на рис. 5.38 так, чтобы гарантировать оценку времени 0(/г) в случае, когда ребрам приписаны произвольные стоимости.

5.27. Напишите алгоритм, который по данной (пХп)-матрице М положительных целых чисел строил бы последовательность смежных элементов, начинакщуюся с Л1[/г, 11 и оканчивающуюся М[1, п], так, чтобы минимизировать сумму абсолютных значений разностей между соседними элементами. Два элемента M.U, /] и M{k, I] считаются смежными, если (а) i-k±l и /=/ или (б) ik и /=/±1. Например, для рис. 5.40 решением будет последовательность 7, 5, 8, 7, 9, 6, 12.

5.28. Алгоритм на рис. 5.24 для каждого о € V вычисляет наименьшую стоимость пути среди всех путей из Уо в у. Модифицируйте этот алгоритм так, чтобы он строил некоторый путь наименьшей стоимости для каждого узла у из V.

19 6 12

8 7 3 5

5 9 11 4

L7 3 2 6J

Рис. 5.40. Матрица положительных целых чисел.



**5.29. Напишите программу, реализующую доминаторный алгоритм из разд. 5.11.

Проблемы для исследования

5.30. Для многих проблем, связанных с графами, поиск в глубину мог бы принести пользу. Одна из них касается k-связности. Неориентированный граф называется k-связным, если для каждой пары узлов V к W существуют такие k путей между ними, что ни один узел (кроме у и tw) не входит более чем в один путь Таким образом, двусвязность означает 2-связность. Хопкрофт, Тарьян [197361 построили алгоритм, отыскивающий 3-связные компоненты за линейное время. Естественно выдвинуть гипотезу, что для каждого k есть алгоритм, отыскивающий /г-связные компоненты за линейное (по числу узлов и ребер) время. Не сможете ли вы найти такой алгоритм?

5.31. Другой интересной проблемой, для решения которой, быть может, нужен поиск в глубину (а, быть может, и нет), является построение алгоритма, отыскивающего за линейное (по числу ребер) время остовное дерево наименьшей стоимости.

5.32. Заслуживает рассмотрения и задача нахождения кратчайшего пути из одного источника, когда е<. Существует ли алгоритм, отыскивающий за время О (е) хотя бы кратчайшее расстояние между двумя конкретными точками? Читателю было бы полезно ознакомиться с упр. 5.21 и 5.22, основанными на диссертации Джонсона [1973], а также с работой Спиры, Пана [1973], в которой показано, что в общем случае для таких алгоритмов требуется rtV4 сравнений, если алгоритмы используют только сравнения между суммами стоимостей ребер. Вагнер [1974] применил технику сортировки вычерпыванием, чтобы получить алгоритм сложности 0(e) в случае, когда в качестве стоимостей ребер фигурируют малые целые числа.

5.33. Было показано (Керр [1972]), что если допускаются только операции MIN и -Ь, то проблема нахождения кратчайших путей между всеми парами узлов требует kn шагов, где k - некоторая положительная постоянная. Рабин усилил этот результат до rtV6. Тем не менее может оказаться, что если допустить другие операции, то можно будет получить алгоритм, работающий менее О (п) времени. Например, как мы увидим в следующей главе, можно построить транзитивное замыкание (или, что эквивалентно, перемножить две булевы матрицы) быстрее, чем за 0(п) шагов, если допустить операции, отличные от булевых.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 [80] 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0039