Этап 5. А) Есть прямой путь из U ={1,2,…,5} в 6. fА = 1.
Б) SU = {6,7,8}; S6 = {5,7,8}; SU Ç S6 = {7,8}; fБ = 2.
В) W5 ={1,2,3,4,5}; fВ = 0. F5 = 3.
Этап 6. А) Есть 2 прямых пути из U ={1,…,6} в 7. fА = 2.
Б) SU = {7,8}; S7 = {5,6,8}; SU Ç S6 = {8}; fБ = 1.
В) W6 ={1,2,3,4,5,6 | 8}; fВ = 0. F6 = 3.
Этап 7. А) Есть 3 прямых пути из U ={1,…,7} в 8. fА = 3.
Б) SU = {8}; S8 = {4,6,7}; SU Ç S7 = {}; fБ = 0.
В) W7 ={1,2,3,4,5,6,7}; fВ = 0. F7 = 3.
Минимальный разрез (Fmin = 2) определяется на шаге 4 = argmin Fi множеством включенных вершин W=W4 ={{1,2,3,4}}. Трудоемкость алгоритма: можно упорядочить списки соседей и найти их пересечение за линейное время; число итераций шага B за все этапы ≤ n, т.к. никакая вершина не может быть предпоследней в жирных цепочках более одного раза. На этом же этапе нельзя из-за ПСР=1, а уже на следующем этапе вершина попадет на слой 1 (т.к. соседняя с ней последняя вершина жирной цепочки включается в U). Но на шаге В номер предпоследнего слоя ³ 2!!! Шаги А и Б оцениваются легко. Пусть R(W) - минимальный разрез графа, 1ÎW и k=min`W ≥2 Þ R(W) будет найден на шаге k.
№25. Задача о потоке минимальной стоимости (ПМС).
Потоковая матрица X = { x ij }должна удовлетворять ограничениям:
1) 0 £ x ij £ a ij , 2) x js = x tj = 0 " i ¹ s,t, 3)- баланс потока.
Мы хотим минимизировать стоимость потока при ограничении . Это неравенство можно превратить в равенство, так как мы экономим деньги и лишнего не купим, то естьF(x) = F0.
Т.о. имеем частный случай задачи ЛП, разрешимой за полиномиальное время методом Хачияна или Левина. Но мы эту задачу будем решать иначе.
Если все числа целые, то на каждом шаге поток увеличивается на 1, и в худшем случае будет шаговF0. Но за полиномиальное время решается задача: есть решение задачи ПМС? Предположим, что сеть может пропустить поток R.
???Алгоритм №1. «Цикл». Найдем максимальный поток и начнем его уменьшать доF0: т.е. ищем цикл с отрицательной суммарной стоимостью (аугментальный цикл) и на цикле уменьшаем стоимость. Для этого находим максимальное Dmax как и в Ф-Ф, при этом стоимость падает на DS=DS cij<0, если S cij<0, после чего ищем очередной аугментальный цикл.
Алгоритм №2. Считаем поток по каждой дуге ориентированным. В цикле находим самую дорогую в сети цепочку из s в t и по ней сократим поток.
Алгоритм №3. ДОСТРОЙКА. На каждом этапе находим самую дешевую не цепочку, а сеть из s в t (аналогично алгоритму Дейкстра) и посылаем по ней (ДК-алгоритмом) поток максимальной величины. Если у вершины окажутся 2 отца с оптимальной стоимостью, то обоих оставляем. Полученную сеть вытянем по слоям в соответствии с ценами. Часть ребер насытится, после чего они блокируются и задача решается заново.
Пример работы алгоритма ДОСТРОЙКА: F0=16 Этап 1:
Шаги 1,2. minПСВ=1, k=2. minПСВ=1, k=4.
Все пути из S в t в этой сети имеют стоимость 13. f = ∑ ПСВ =2. S=2*13=26, F=2.
Этап 2: После этапа 1 ребра (1,2) и (4,3) насыщены. Этап 3.
s=6*14=84, S=26+84=110 s=6*15=90 S=110+90=200
Этап 4. По обратной дуге ранее включенная вершина 1 меняет пометку с 8 на 5!!
Можно было бы пропустить поток F = 17, но нам не нужно. Ответ – S=232.
P.S.
Стоимость обратных дуг отрицательна. Это может привести к уменьшению пометок
ранее включенных вершин, если добавление обратных дуг
не порождает ориентированных циклов.
3.6. ПРИБЛИЖЕННОЕ РЕШЕНИЕ NP-ПОЛНЫХ
ЗАДАЧ.
№26. Задача о максимальном независимом множестве.
Граф: вершины=работы соединены ребром, если они используют один и тот же ресурс.
Вопрос: Какое максимальное количество работ можно выполнять одновременно?
Решение: Алгоритм типа ДОСТРОЙКА («включение членов»).
S = Æ. Находим вершины с минимальной степенью 2:
4,5,6,8. Выбираем 4:
S = {4}. Удаляем вместе с ребрами работы 3 и 5, которые не могут
выполняться, если выбрана 4. Выбираем 6 степени 1: S={4,6},
удаляем 7. 2,8 степени 1, выбираем 2: S={4,6,2} удаляем 1.
Осталась 8 ст. 0, S={4,6,2,8}.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.