Минимаксная модификация задачи о кратчайших путях

В некоторых практически и теоретически интересных случаях длиной пути естественно считать значение некоторой функции, выражающей – тем или иным образом – длину пути через длины всех входящих в него дуг или рёбер. Рассмотренная выше длина пути, равная сумме длин всех входящих в него рёбер, далеко не исчерпывает всех таких зависимостей. Не рассмат-ривая – в силу скромных целей настоящего пособия – общую задача нахождения кратчайших путей с обобщёнными функциями длин, сосредоточим внимание лишь на одном варианте такой функции. Именно, определим длину L (P) пути P формулой

L (P) = max l (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{ d_ik, d_kj } (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 пособия.