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

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

граф

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

граф с перенумерованными вершинами

Матрица D:

D= 12 28
12 10 43
10 10
28 43 17
31 10 8
14 6
6

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

12 22 28 32 40 46
12 10 40 20 28 34
22 10 50 10 18 24
28 27 17 27 35 41
32 20 10 60 8 14
46 34 24 74 14 6
52 40 30 80 20 6

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

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

1 2 3 4 5 6 7
1 10 16 20 28 34
2 2 30 10 18 24
3 12 40 8 14
4 11 10 10 18 24
5 24 12 2 52 6
6 40 28 18 68 8
7 46 34 24 74 14

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

1 2 3 4 5 6 7
1 10 20 28 34
2 14 10 18 24
3 10 24 8 14
4 9 10 10 18 24
5 22 12 2 36 6
6 38 28 18 52 8
7 44 34 24 58 14

Для каждого нулевого элемента рассчитаем значение Г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)

1 2 3 5 6 7
2 10 18 24
3 10 8 14
4 9 10 10 18 24
5 22 12 2 6
6 38 28 18 8
7 44 34 24 14

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

Читайте также  Абсолютная медиана графа
1 2 3 5 6 7
2 10 18 24
3 10 8 14
4 10 10 18 24
5 22 12 2 6
6 38 28 18 8
7 44 34 24 14

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

1 2 3 5 6 7
2 10 18 24
3 10 8 14
4 10 10 18 24
5 22 12 2 6
6 38 28 18 8
7 44 34 24 14

Для каждого нулевого элемента рассчитаем значение Г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)

1 2 3 5 6
2 10 18
3 10 8
4 10 10 18
5 22 12 2
7 44 34 24 14

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

1 2 3 5 6
2 10 18
3 10 8
4 10 10 18
5 22 12 2
7 30 20 10

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

1 2 3 5 6
2 10 18
3 10 8
4 10 10 18
5 22 12 2
7 30 20 10

Для каждого нулевого элемента рассчитаем значение Г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)

2 3 5 6
3 8
4 10 10 18
5 12 2
7 20 10

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

Читайте также  Табличный симплекс-метод
2 3 5 6
3 8
4 10 18
5 12 2
7 20 10

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

2 3 5 6
3 8
4 10 18
5 12 2
7 20 10

Для каждого нулевого элемента рассчитаем значение Г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)

3 5 6
4 10 18
5 2
7 10

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

3 5 6
4 8
5 2
7 10

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

3 5 6
4 8
5
7 8

Для каждого нулевого элемента рассчитаем значение Г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)

3 6
5
7 8

В строке 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)

3 6
4 8
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)

Читайте также  Алгоритм Литтла - Пример 2
3 5
4
7 8

В строке 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)

5 6
4 8
7

В строке 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 единицу.

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...