Алгоритм Литтла - Пример 1

Необходимо найти оптимальный маршрут коммивояжера в графе представленом на рисунке:

Пронумеруем вершины исходного графа, и составим матрицу длин кратчайших дуг между каждой парой вершин D⁰, в случае, если дуги между вершиной i и j не существует, элементу d_i,j матрицы присваивается значение . Исходный граф с пронумероваными вершинами представлен на рисунке ниже.

Матрица D⁰:

D⁰=

В матрице D⁰ присутствуют элементы имеющие значение , что не допустимо. Заменим бесконечные дуги на длины кратчайших путей между соответствующими вершинами (за исключением диагональных элементов которым присвоим значения бесконечности). В результате получим следующую матрицу стоимости:

Так как ее элементы являются уже не дугами а расстояниями между вершинами, то мы освобождаемся от необходимости проверки неравенства треугольника (оно в этом случае выполняется автоматически).

Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г_1,2=0, Г_1,4=14, Г_2,1=9, Г_2,3=0, Г_3,2=0, Г_3,5=8, Г_4,3=9, Г_5,6=2, Г_6,7=14, Г_7,6=14,
В результате сравнения мы получили 3 одинаковых максимальных Г=14. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно.Рассмотрим вариант Г_1,4=14
Удалим из матрицы стоимости строку 1 и столбец 4. Внесем в текущий ориентированный граф дугу (1,4)

В строке 4 и столбце 1 отсутствует элемент равный . Присвоим элементу (4,1) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=87
Нижняя граница равна сумме всех вычтенных элементов в строках и столбцах. Итоговое значение нижней границы должно совпасть с длиной результирующего контура.
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г_2,1=10, Г_2,3=0, Г_3,2=10, Г_3,5=8, Г_4,3=10, Г_5,6=2, Г_6,7=14, Г_7,6=14,
В результате сравнения мы получили 2 одинаковых максимальных Г=14. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно.Рассмотрим вариант Г_6,7=14
Удалим из матрицы стоимости строку 6 и столбец 7. Внесем в текущий ориентированный граф дугу (6,7)

В строке 7 и столбце 6 отсутствует элемент равный . Присвоим элементу (7,6) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=87
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г_2,1=10, Г_2,3=0, Г_3,2=10, Г_3,5=0, Г_4,3=10, Г_5,6=10, Г_7,5=10,
В результате сравнения мы получили 5 одинаковых максимальных Г=10. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно.Рассмотрим вариант Г_2,1=10
Удалим из матрицы стоимости строку 2 и столбец 1. Внесем в текущий ориентированный граф дугу (2,1)

В строке 4 и столбце 2 отсутствует элемент равный . Присвоим элементу (4,2) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=101
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г_3,2=12, Г_3,5=0, Г_4,3=12, Г_5,6=10, Г_7,5=10,
В результате сравнения мы получили 2 одинаковых максимальных Г=12. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно.Рассмотрим вариант Г_3,2=12
Удалим из матрицы стоимости строку 3 и столбец 2. Внесем в текущий ориентированный граф дугу (3,2)

В строке 4 и столбце 3 отсутствует элемент равный . Присвоим элементу (4,3) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=101
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г_4,5=8, Г_5,3=8, Г_5,6=8, Г_7,5=8,
В результате сравнения мы получили 4 одинаковых максимальных Г=8. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно.Рассмотрим вариант Г_4,5=8
Удалим из матрицы стоимости строку 4 и столбец 5. Внесем в текущий ориентированный граф дугу (4,5)

В строке 5 и столбце 3 отсутствует элемент равный . Присвоим элементу (5,3) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=113
После того, как ранг матрицы становится равным двум мы получае нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=121
Маршрут коммивояжера включает в себя дуги:, (1, 4), (6, 7), (2, 1), (3, 2), (4, 5), (5, 6), (7, 3)
-------------------------------------------------------------------------
Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г_7,5. Удалим из матрицы стоимости строку 5 и столбец 7. Внесем в текущий ориентированный граф дугу (7,5)

В строке 5 и столбце 6 отсутствует элемент равный . Присвоим элементу (5,6) значение бесконечности чтобы избежать преждевременногог замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=121
Маршрут коммивояжера включает в себя дуги:, (1, 4), (6, 7), (2, 1), (3, 2), (7, 5), (4, 6), (5, 3)
-------------------------------------------------------------------------
Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г_5,6. Удалим из матрицы стоимости строку 6 и столбец 5. Внесем в текущий ориентированный граф дугу (5,6)

В строке 7 и столбце 5 отсутствует элемент равный . Присвоим элементу (7,5) значение бесконечности чтобы избежать преждевременногог замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=121
Маршрут коммивояжера включает в себя дуги:, (1, 4), (6, 7), (2, 1), (3, 2), (5, 6), (4, 5), (7, 3)
-------------------------------------------------------------------------
Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г_5,3. Удалим из матрицы стоимости строку 3 и столбец 5. Внесем в текущий ориентированный граф дугу (5,3)

В строке 4 и столбце 5 отсутствует элемент равный . Присвоим элементу (4,5) значение бесконечности чтобы избежать преждевременногог замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=121
Маршрут коммивояжера включает в себя дуги:, (1, 4), (6, 7), (2, 1), (3, 2), (5, 3), (4, 6), (7, 5)
----------------------------------------------------------------------

Приводить рассматрение остальных ветвлений алгоритма мы не будем. Скажем сразу, что оптимальное решение нами уже получено (все три контура полученые нами имеют одинаковое значение нижней границы равное 121, следовательно каждый из них задает наилучший маршрут коммивояжера). Рассмотрим первый полученый нами вариант: (1, 4), (6, 7), (2, 1), (3, 2), (7, 5), (4, 6), (5, 3).

Вспомним, что в процессе решения мы заменили некоторые элементы матрицы стоимости (которые по умолчанию являются дугами графа) путями между соответствующими вершинами. Теперь, если такие дуги имеются в составе полученого оптимального контура, необходимо заменить их на эти пути (для этого используется таблица кратчайших путей, полученная предварительно с помощью алгоритма Флойда или Данцига). Дуге (1, 4) соответствует путь (1, 4); дуге (6, 7) - путь(6, 7); дуге (2, 1) соответствует путь (2, 1); дуге (3, 2) - путь (3,2); дуге (5, 3) соответствует путь (5, 3); дуге (7, 5) - путь 7-6-5; дуге (4, 6) - путь 4-3-5-6. То есть оптимальный контур для нашего графа: 1-4-3-5-6-7-6-5-3-2-1 длиной 121 единицу.