Минимаксная модификация задачи о кратчайших путях
В некоторых практически и теоретически интересных случаях длиной пути естественно считать значение некоторой функции, выражающей – тем или иным образом – длину пути через длины всех входящих в него дуг или рёбер. Рассмотренная выше длина пути, равная сумме длин всех входящих в него рёбер, далеко не исчерпывает всех таких зависимостей. Не рассмат-ривая – в силу скромных целей настоящего пособия – общую задача нахождения кратчайших путей с обобщёнными функциями длин, сосредоточим внимание лишь на одном варианте такой функции. Именно, определим длину L(P) пути P формулой
L(P) = maxl(p, q), (3)
где максимум берётся по всем рёбрам пути P (в ориентированном случае – по всем дугам). Та-кая постановка называется минимаксной (иногда, имея в виду некоторые экономические интер-претации, её называют задачей на узкие места).
На первый взгляд, минимаксная задача заметно отличается от рассмотренной в предыду-щих разделах 2 и 3 традиционной задачи на крачайшие пути. Тем более удивительно, что реша-ется она теми же самыми алгоритмами– АД и АФУ. Остановимся на этом подробнее.
4.1.Модифицированный алгоритм Дейкстры (МАД) для нахождения минимаксных пу-тей из заданной начальной вершины во все остальные. Структура алгоритма остаётся той же са-мой. Единственное изменение касается пункта А1) алгоритма. Формула Z = P(c) + l(c, x) заменяется формулой Z = max{P(c), l(c, x)}. Больше ничего в АД не меняется.
Пример 5.Рассмотрим применение МАД для графа из примера 1 (этот граф для удобства чтения приводится здесь ещё раз). Составим таблицу 6, аналогичную таблице 1 (как уже гово-рилось, изменения коснутся только вычисления величины Z). В остальном правила заполнения таблицы не меняются.
Таблица 6. Пример прменения МАД
| Итера- ция | Последняя помеченная | Вершина 0 | Вершина 1 | Вершина 2 | Вершина 3 | Вершина 4 | Вершина 5 | |||||||||||||
| № | с | P | Z | T | R | Z | T | R | Z | T | R | Z | T | R | Z | T | R | Z | T | R |
| ∞ | ∞ | ∞ | ∞ | ∞ | ||||||||||||||||
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |||||||||||||||
| ∞ | ∞ | |||||||||||||||||||
| ∞ | ∞ | ∞ | ||||||||||||||||||
Дадим пояснения к заполнению данной таблицы. На 0-ой итерации (инициализации) в соответствии с МАД начальной вершине 0 присваиваем постоянную метку 0 (оба числа зано-сятся в 0-ую строку в столбце «Последняя помеченная»). Остальные вершины получают вре-менную метку ∞, которая и заносится в 0-ую строку под буквами T. В остальные позиции 0-ой строки в соответствии с МАД ничего не заносится.
На 1-ой итерации обрабатываются только столбцы, соответствующие вершинам, имею-щим временные метки. Таковыми в этот момент являются все вершины, кроме вершины 0. Вы-числяем числа Zдля всех этих вершин. Так как на 0-ой итерации с = 0, P(c) = 0, то имеем (см. граф) max{P(0), l(0,1)}=1, max{P(0), l(0,2)}=5, max{P(0), l(0,х)}=∞ для х=3,4,5. Поэтому в 1-ую строку под знаком Zзаписываются числа 1, 5 и знаки ∞, ∞, ∞. Далее, сравнивая эти значения со значениями Tиз предыдущей строки, записываем под знаком Tв данную строку минимумы, а под знаком Rв тех столбцах, где произошли изменения в T – последнюю помеченную вершину изстолбца с (в данном случае 0). Выбирая минимальное значение из записанных значений T, получаем 1 в столбце для вершины 1. Поэтому записываем 1 (номер вершины) под с и 1 (длина кратчайшего пути) под P.
На 2-ой итерации обрабатываются только столбцы, соответствующие вершинам 2, 3, 4 и 5. Так как на 1-ой итерации с=1, P(c)=1, то имеем (см. граф) max{P(1), l(1,2)}=8, max{P(1), l(1,3)} =10, max{P(1), l(1,4)}=6, max{P(1), l(1,5)}=∞. Поэтому во 2-ую строку под знаком Zзаписыва-ются числа 8,10,6 и знак ∞. В клетках справа и сверху от этих чисел записаны (под знаком T) предыдущие временные метки: 5,∞,∞,∞. В клетки во 2-ой строке под знаком T записываем но-вые временные метки - наименьшие значения из этих двух чисел; получаем 5,10,6 и ∞. Под зна-ком R в 3-ей и 4-ой группах столбцов во 2-ой строке пишется текущий номер c=1. Выбирая минимальное значение из записанных значений T, получаем 5 в столбце для вершины 2. Поэтому записываем 2 (номер вершины) под с и 5 (длина кратчайшего пути) под P.
На 3-ьей итерации обрабатываются только столбцы, соответствующие вершинам 3,4 и 5. Так как на 2-ой итерации с=2, P(c)=5, то имеем (см. граф) max{P(2), l(2,3)}=∞, max{P(2), l(2, 4)}=7, max{P(2), l(2,5) = ∞. Поэтому в 3-ью строку под знаком Zзаписываются ∞,7,∞. В клетке справа и сверху от этих чисел записаны (под знаком T) предыдущие временные метки: 10,6,∞. В клетку в 3-ьей строке под знаком T записываем новые временные метки - наименьшие значения из этих пар чисел; получаем 10,6 и ∞. Под знаком R во всех трёх столбцах ничего не меняется, так как временные метки в них не изменились. Выбирая минимальное значение из записанных значений T, получаем 6 в столбце для вершины 4. Поэтому записываем 4 (номер вершины) под с и 6 (длина крат-чайшего пути) под P.
На 4-ой итерации рассматриваются только две вершины: 3 и 5. Новые временные метки для них совпадают. В этом случае можно выбрать любую. Выбираем вершину 3 и в соответст-вии с этим заполняем 4-ую строку и далее – последнюю, 5-ую строку.
Найдём теперь, в соответствии с шагом F МАД, сами кратчайшие пути. Просматриваем вершины в том порядке, в каком они идут во 2-ом столбце (в этом порядке они получают посто-янные метки).
Для вершины 1 последнее заполненное значение под знакомRравно 0. Это означает, что предпоследней вершиной на кратчайшем пути из 0 в 1 является начальная вершина 0. Поэтому имеем путь 0→1 длины 1.
Для вершины 2 последнее заполненное значение под знакомRравно 0. Это означает, что предпоследней вершиной на кратчайшем пути из 0 в 2 является начальная вершина 0. Поэтому имеем путь 0→2 длины 5.
Для вершины 4 последнее заполненное значение под знакомRравно 1. Это означает, что предпоследней вершиной на кратчайшем пути из 0 в 4 является вершина 1. Поскольку для вер-шины 1 кратчайший путь таков: 0→1, то имеем путь 0→1→4 длины 6.
Для вершины 3 последнее заполненное значение под знакомRравно 4. Это означает, что предпоследней вершиной на кратчайшем пути из 0 в 3 является вершина 4. Поскольку для вер-шины 4 кратчайший путь таков: 0→1→4, то имеем путь 0→1→4→3 длины 6.
Для вершины 5 последнее заполненное значение под знакомRравно 4. Это означает, что предпоследней вершиной на кратчайшем пути из 0 в 5 является вершина 4. Поскольку для вер-шины 4 кратчайший путь таков: 0→1→4, то имеем путь 0→1→4→5 длины 6.
Напомним, что в данном случае длиной пути является не сумма длин рёбер, а длина мак-симального (в данном пути) ребра. Поэтому кратчайшие пути в одном и том же графе могут от-личаться. Запишем их для сравнения рядом:
| i | Кратчайший путь из вершины 0 в вершину i (сумма длин рёбер) | Длина пути | Кратчайший путь из вершины 0 в вер-шину i (длина максимального ребра) | Длина пути |
| 0→1 | 0→1 | |||
| 0→2 | 0→2 | |||
| 0→1→3 | 0→1→4→3 | |||
| 0→1→4 | 0→1→4 | |||
| 0→1→4→5 | 0→1→4→5 |
Таким образом, даже в этом простейшем случае решения при различных определениях длины не совпадают ■
Задание 3. Используя МАД, найти минимаксные пути между вершиной 0 и остальными вершинами в графах из задания 1 ■
4.2.Модифицированный алгоритм Флойда-Уоршолла(МАФУ) для нахождения мини-максных путей между всеми парами вершин. Структура алгоритма остаётся той же самой. Единственное изменение касается пункта 1.1 общего шага k алгоритма. Формула (2) заменяется формулой (4):
z = max{dik, dkj} (4)
Больше ничего в АФУне меняется.
Пример 6.Рассмотрим применение МАФУ для графа из примера 3 (этот граф для удобст-
ва чтения приводится здесь ещё раз). Результат инициализации совпадает с результатом иници-
ализации, представленным в таблице 4. Приведём здесь эту таблицу ещё один раз:
Таблица 7. Результат инициализации
| № | |||||||||||||||||||||
| ∞ | −4 | ||||||||||||||||||||
| ∞ | ∞ | ||||||||||||||||||||
| ∞ | ∞ | ∞ | |||||||||||||||||||
| ∞ | −5 | ∞ | |||||||||||||||||||
| ∞ | ∞ | ∞ | |||||||||||||||||||
Сами правила заполнения таблиц, подробно описанные в примере 3, не меняются, кроме одного пункта: операция суммирования заменяется на операцию взятия максимума из тех пар чисел. Ниже приводятся результаты всех 5-и последовательных итераций.
Таблица 7.1. Результат итерации 1
| № | |||||||||||||||||||||
| ∞ | −4 | ||||||||||||||||||||
| ∞ | ∞ | ||||||||||||||||||||
| ∞ | ∞ | ∞ | |||||||||||||||||||
| −5 | |||||||||||||||||||||
| ∞ | ∞ | ∞ | |||||||||||||||||||
Таблица 7.2. Результат итерации 2
| № | |||||||||||||||||||||
| −4 | |||||||||||||||||||||
| ∞ | ∞ | ||||||||||||||||||||
| ∞ | |||||||||||||||||||||
| −5 | |||||||||||||||||||||
| ∞ | ∞ | ∞ | |||||||||||||||||||
Таблица 7.3. Результат итерации 3
| № | |||||||||||||||||||||
| −4 | |||||||||||||||||||||
| ∞ | ∞ | ||||||||||||||||||||
| ∞ | |||||||||||||||||||||
| −5 | |||||||||||||||||||||
| ∞ | ∞ | ∞ | |||||||||||||||||||
Таблица 7.4. Результат итерации 4
| № | |||||||||||||||||||||
| −4 | |||||||||||||||||||||
| −5 | |||||||||||||||||||||
Таблица 7.5. Результат итерации 5
| № | |||||||||||||||||||||
| −4 | |||||||||||||||||||||
| −5 | |||||||||||||||||||||
Шаг F. Найдём сами кратчайшие пути, используя правые клетки в ячейках. Напомним, что число в правой клетке в ячейке (i, j) – это номер вершины, предшествующей на кратчайшем пути из iв j вершине j, т.е. номер предпоследней вершины на этом пути.
Для пути из 1 в 2 такой вершиной является вершина 1 (см. таблицу 7.5); далее, для пути из 1 в 3 такой вершиной является вершина 4; для пути из 1 в 4 такой вершиной является вершина 2; наконец, для пути из 1 в 5 такой вершиной является вершина 1. Таким образом, кратчайшие пути из вершины 1 в другие вершины таковы: 1→2; 1→2→4→3; 1→2→4;1→5.
Кратчайшие пути из вершины 2 таковы: 2→4→1; 2→4→3; 2→4; 2→4→1→5.
Кратчайшие пути из вершины 3 таковы: 3→2→4→1; 3→2; 3→2→4; 3→2→4→1→5.
Кратчайшие пути из вершины 4 таковы: 4→1; 4→1→2; 4→3; 4→1→2→5.
Кратчайшие пути из вершины 5 таковы: 5→4→1; 5→4→1→2; 5→4→3; 5→4.
Напомним, что за длину пути в данном случае принимается длина его самой длинной дуги. Сравнивая найденные в данном примере пути с обычными кратчайшими путями из примера 3, убеждаемся, что во многих случаях пути получаются совершенно различными. Например, кратчайший путь из вершины 1 в вершину 2 в рассматриваемом минимаксном случае таков: 1→2, в то время как в традиционной постановке соединяющий те же две вершины путь с минимальной суммарной длиной таков: 1→5→4→3→2 (см. рисунок) ■
Задание 4. Используя МАФУ, найти минимаксные пути между всеми парами вершин в графах из задания 1. Для образца см. примеры 3 и 6. В рассматриваемом неориентированном случае, как уже говорилось, можно использовать тот же самый алгоритм ■
Предметный указатель
Вершинапромежуточная
Дейкстры алгоритм (АД)
модифицированный (МАД)
Метка временная
постоянная
Пути, длина
Путь, кратчайший
минимаксный
минимальный
Флойда-Уоршолла алгоритм (АФУ)
модифицированный (МАФУ)
Глава 9. Паросочетания
1. Максимальные паросочетания
2. Задача назначения
3. Предметный указатель
В некоторых случаях вершины графа распадаются на две части, так что все имеющиеся рёбра соединяют только вершины из разных частей. Напомним, что соответствующий граф на-зывается двудольным, а любое множество рёбер двудольного графа, которые не имеют общих вершин, называется паросочетанием (см. раздел 6-6). Многие практически важные задачи сводятся к поиску паросочетаний, обладающих теми или иными свойствами. Две оптимизаци-онных задачи поиска паросочетаний рассматриваются в данной главе; ещё одна – но уже не оп-тимизационная – задача поиска паросочетаний, удовлетворяющих некоторым специальным условиям, рассмотрена в разделе13-1 пособия.