Пример решения

Рассмотрим работу алгоритма Литтла на примере сети, изображенной на рис. 11. Числа c_ij, приписанные дугам, соответствуют их длине или обобщенной стоимости. Матрица обобщенной стоимости этой сети имеет вид:

C =

Работа алгоритма начинается с редуцирования ацикличных и однонаправленныхучастков сети. Результат приведен на рис. 12. Из матрицы C при этом вычеркиваются строки и столбцы с одинаковыми номерами, в которых не на главной диагонали имеется не более одного конечного элемента, то есть в нашем случае №№ 5, 6. Матрица редуцированного циклического подграфа G ₁ имеет вид:

C ₁ =

Для вычисления верхней границы используем цепь [1, 2, 3, 4, 1]:

H _max = H [1, 2, 3, 4, 1] = 17 + 7 + 11 + 3 = 38.

Процедура итераций:

Итерация № 1.

Исходная матрица

min в стр.

Редуцированная по строкам

Редуцированная по столбцам

S=22

S=0

Нижняя граница стоимости всех маршрутов, которая получается на этой итерации, есть сумма всех величин, на которые редуцировалась матрица (они выписаны справа от исходной и снизу от редуцированной по строкам матриц): H ₁ = 22 + 0 = 22.

В последней таблице справа и снизу выписаны наименьшие (кроме нуля) элементы в строках и столбцах, соответственно. Сумма тех из них, которые расположены в тех же столбце и строке, что и какой-нибудь ноль, есть штраф за невыбор этого нуля. Для каждого нуля вычисляем штрафы:

i, j	1,4	2,3	3,2	4,1
Фij

Так как максимален Ф ₁₄, то все маршруты делятся на две группы: содержащие дугу [1, 4], и ее не содержащие (в дереве маршрутов метка [ 1, 4 ], рис. 13). Нижняя граница стоимости всех маршрутов, не содержащих дугу [1, 4], вычисляется как сумма H ₁ и Ф ₁₄: Н ₁₄ = 22 + 10 = 32. Элемент с ₄₁ полагается равным . Поверок на возврат и подциклы на итерации №1 не производится, нижняя граница второй вершины рис. 13 вычисляется на следующей итерации №2, в которой рассматривается матрица без первой строки и четвертого столбца.

Итерация № 2.

Исходная матрица

min в стр.

Редуцированная по строкам

Редуцированная по столбцам

S=5

S=3

Нижняя граница узла [1, 4], которая получается на этой итерации, есть сумма всех величин, на которые редуцировалась матрица, и предыдущей нижней границы H ₁: H ₁₄ = 22 + 5 + 3 = 30.

Для каждого нуля вычисляем штрафы:

i, j	2,3	3,1	3,2	4,2
Фij

Так как максимален Ф ₂₃, то маршруты, содержащие дугу [1, 4], делятся на две группы: содержащие дугу [2, 3] и ее не содержащие (в дереве маршрутов метка [ 2, 3 ], рис. 14). Причем нижняя граница стоимости всех маршрутов, не содержащих дугу [2, 3], вычисляется как сумма H ₁₄ и Ф ₂₃: Н ₂₃ = 30 + 10 = 40. Элемент с ₃₂ полагается равным . Проверка на возврат и подциклы на итерации № 2 результата не дает, так как H ₁₄ < min { H _max, H ₁₄} и из дуг [1, 4] и [2, 3] нельзя образовать подцикл добавлением любой третьей, нижняя граница второй вершины (рис. 14) вычисляется на следующей итерации № 3, в которой рассматривается матрица без второй строки и третьего столбца.

Итерация № 3.

Исходная матрица

min в стр.

Редуцированная по строкам

Редуцированная по столбцам

S=0

S=0

Нижняя граница узла [2, 3]: H ₂₃ = H ₁₄+ 0 + 0 = 30.

Для каждого нуля вычисляем штрафы:

i, j	3,1	4,2
Фij

Бесконечные штрафы означают, что мы обязаны выбрать обе дуги, которым соответствуют конечные элементы матрицы, прием при выборе их получается полный маршрут. В такой ситуации нижние границы H ₃₁ и Н ₄₂ равны между собой и равны H ₂₃ (нижней границе данной итерации). Так как H ₂₃ < min { H _max, H ₁₄, H ₂₃}, то возврата нет; так как замкнут полный маршрут, то подцикл не образован. Вообще говоря, наличие на какой-либо итерации матрицы 2 х 2, аналогичной полученной здесь, свидетельствует о правильности произведенных вычислений и об окончании итераций и без вычисления штрафов. Результирующее дерево маршрутов приведено на рис. 16.

В результате итеративного процесса получен минимальный остовный контур [1, 4, 2, 3, 1] графа G ₁ (рис. 12) с обобщенной стоимостью 30. Для получения минимального остовного контура исходной сети G (рис. 11) необходимо в него добавить контуры от редуцированных на первом этапе алгоритма участков: [1, 4, 6, 4, 2, 3, 1, 5, 1 ], а к стоимости добавить с ₁₅ + с ₅₁ + с ₄₆ + с ₆₄, что даст окончательную величину обобщенной стоимости найденного минимального остовного контура:

С _{[1, 4, 6, 4, 2, 3, 1, 5, 1]} = 30 + 2 + 4 + 5 + 5 = 46.

Решение задачи получено. Необходимо, однако, отметить, что в данном случае не встретилась ситуация возврата и ситуация устранения возможного подцикла, и сели последняя встретится ниже в примере выполнения домашнего задания, то ситуацию возврата иллюстрирует дерево маршрутов (рис. 17) для задачи с нижеприведенной матрицей обобщенной стоимости, причем из-за наличия только нулевых штрафов на первой итерации (ситуация большого количества близких по стоимости маршрутов) при выборе на первой итерации дуги [1, 5] уже на третьей возникает возврат, так как на этой итерации H ₃₄ оказывается больше H ₁₅ (см. рис. 17).

C = .

Более того, при проведении процедуры возврата к первой итерации (при этом c ₁₅ = ) на итерации 2’ снова возникает возврат (см. рис. 17) за счет отмеченной выше особенности матрицы примера.