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

Имеется схема расположения N абонентов локальной вычислительной сети. Физическая топология – кольцо.
Необходимо выбрать маршрут организации абонентов в сеть с учетом критерия выбора – минимум затрачиваемого кабеля (цифры даны в метрах).
Число абонентов N=10. Матрица расстояний между абонентами представлена ниже.

60.8 58.3 47.2 62.6 40.3 79.1 29.2 40.3 40.3
60.8 108.2 105.9 40.3 47.2 91.9 57.0 74.3 74.3
58.3 108.2 26.9 87.3 98.6 60.4 51.5 36.4 36.4
47.2 105.9 26.9 95.1 84.9 82.0 55.0 47.4 47.4
62.6 40.3 87.3 95.1 73.8 54.1 40.3 51.0 51.0
40.3 47.2 98.6 84.9 73.8 110.1 60.2 76.5 76.5
79.1 91.9 60.4 82.0 54.1 110.1 51.0 40.3 40.3
29.2 57.0 51.5 55.0 40.3 60.2 51.0 18.0 18.0
40.3 74.3 36.4 47.4 51.0 76.5 40.3 18.0
40.3 74.3 36.4 47.4 51.0 76.5 40.3 18.0

Перейдем от матрицы расстояний к матрице стоимости, присвоив диагональному элементу значения бесконечности. Так-как задача геометрическая, неравенство треугольника для нее выполняется, и мы можем искать решение в виде гамильтонова контура.

60.8 58.3 47.2 62.6 40.3 79.1 29.2 40.3 40.3
60.8 108.2 105.9 40.3 47.2 91.9 57.0 74.3 74.3
58.3 108.2 26.9 87.3 98.6 60.4 51.5 36.4 36.4
47.2 105.9 26.9 95.1 84.9 82.0 55.0 47.4 47.4
62.6 40.3 87.3 95.1 73.8 54.1 40.3 51.0 51.0
40.3 47.2 98.6 84.9 73.8 110.1 60.2 76.5 76.5
79.1 91.9 60.4 82.0 54.1 110.1 51.0 40.3 40.3
29.2 57.0 51.5 55.0 40.3 60.2 51.0 18.0 18.0
40.3 74.3 36.4 47.4 51.0 76.5 40.3 18.0
40.3 74.3 36.4 47.4 51.0 76.5 40.3 18.0

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

1 2 3 4 5 6 7 8 9 10
1 31.6 29.1 18 33.4 11.1 49.9 11.1 11.1
2 20.5 67.9 65.6 6.9 51.6 16.7 34 34
3 31.4 81.3 60.4 71.7 33.5 24.6 9.5 9.5
4 20.3 79 68.2 58 55.1 28.1 20.5 20.5
5 22.3 47 54.8 33.5 13.8 10.7 10.7
6 6.9 58.3 44.6 33.5 69.8 19.9 36.2 36.2
7 38.8 51.6 20.1 41.7 13.8 69.8 10.7
8 11.2 39 33.5 37 22.3 42.2 33
9 40.3 74.3 36.4 47.4 51 76.5 40.3 18
10 40.3 74.3 36.4 47.4 51 76.5 40.3 18

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

1 2 3 4 5 6 7 8 9 10
1 31.6 29.1 18 33.4 4.2 36.1 11.1 11.1
2 20.5 67.9 65.6 37.8 16.7 34 34
3 31.4 81.3 60.4 64.8 19.7 24.6 9.5 9.5
4 20.3 79 68.2 51.1 41.3 28.1 20.5 20.5
5 22.3 47 54.8 26.6 10.7 10.7
6 6.9 58.3 44.6 33.5 56 19.9 36.2 36.2
7 38.8 51.6 20.1 41.7 13.8 62.9 10.7
8 11.2 39 33.5 37 22.3 35.3 19.2
9 40.3 74.3 36.4 47.4 51 69.6 26.5 18
10 40.3 74.3 36.4 47.4 51 69.6 26.5 18

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г1,8=4.2, Г2,5=13.8, Г2,6=4.2, Г3,4=27.5, Г4,3=40.4, Г5,2=6.9, Г5,7=19.2, Г5,8=0, Г6,1=18.1, Г7,9=0, Г7,10=0, Г8,9=0, Г8,10=0, Г9,10=18, Г10,9=18,
Максимальное значение имеет Г4,3=40.4
Удалим из матрицы стоимости строку 4 и столбец 3, и присвоим элементу (3,4) значение бесконечности. Внесем в текущий ориентированный граф дугу (4,3)

1 2 4 5 6 7 8 9 10
1 31.6 18 33.4 4.2 36.1 11.1 11.1
2 20.5 65.6 37.8 16.7 34 34
3 31.4 81.3 60.4 64.8 19.7 24.6 9.5 9.5
5 22.3 54.8 26.6 10.7 10.7
6 6.9 44.6 33.5 56 19.9 36.2 36.2
7 38.8 51.6 41.7 13.8 62.9 10.7
8 11.2 39 37 22.3 35.3 19.2
9 40.3 74.3 47.4 51 69.6 26.5 18
10 40.3 74.3 47.4 51 69.6 26.5 18

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

1 2 4 5 6 7 8 9 10
1 31.6 18 33.4 4.2 36.1 11.1 11.1
2 20.5 65.6 37.8 16.7 34 34
3 21.9 71.8 50.9 55.3 10.2 15.1
5 22.3 54.8 26.6 10.7 10.7
6 6.9 44.6 33.5 56 19.9 36.2 36.2
7 38.8 51.6 41.7 13.8 62.9 10.7
8 11.2 39 37 22.3 35.3 19.2
9 40.3 74.3 47.4 51 69.6 26.5 18
10 40.3 74.3 47.4 51 69.6 26.5 18
Читайте также  Алгоритмы поиска кратчайших путей

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

1 2 4 5 6 7 8 9 10
1 31.6 33.4 4.2 36.1 11.1 11.1
2 20.5 47.6 37.8 16.7 34 34
3 21.9 71.8 50.9 55.3 10.2 15.1
5 22.3 36.8 26.6 10.7 10.7
6 6.9 26.6 33.5 56 19.9 36.2 36.2
7 38.8 51.6 23.7 13.8 62.9 10.7
8 11.2 39 19 22.3 35.3 19.2
9 40.3 74.3 29.4 51 69.6 26.5 18
10 40.3 74.3 29.4 51 69.6 26.5 18

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г1,4=19, Г1,8=0, Г2,5=13.8, Г2,6=4.2, Г3,9=0, Г3,10=0, Г5,2=6.9, Г5,7=10.2, Г5,8=0, Г6,1=18.1, Г7,9=0, Г7,10=0, Г8,9=0, Г8,10=0, Г9,10=18, Г10,9=18,
Максимальное значение имеет Г1,4=19
Удалим из матрицы стоимости строку 1 и столбец 4. Внесем в текущий ориентированный граф дугу (1,4)

1 2 5 6 7 8 9 10
2 20.5 37.8 16.7 34 34
3 21.9 71.8 50.9 55.3 10.2 15.1
5 22.3 26.6 10.7 10.7
6 6.9 33.5 56 19.9 36.2 36.2
7 38.8 51.6 13.8 62.9 10.7
8 11.2 39 22.3 35.3 19.2
9 40.3 74.3 51 69.6 26.5 18
10 40.3 74.3 51 69.6 26.5 18

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

1 2 5 6 7 8 9 10
2 20.5 37.8 16.7 34 34
3 71.8 50.9 55.3 10.2 15.1
5 22.3 26.6 10.7 10.7
6 6.9 33.5 56 19.9 36.2 36.2
7 38.8 51.6 13.8 62.9 10.7
8 11.2 39 22.3 35.3 19.2
9 40.3 74.3 51 69.6 26.5 18
10 40.3 74.3 51 69.6 26.5 18

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

1 2 5 6 7 8 9 10
2 20.5 37.8 16.7 34 34
3 71.8 50.9 55.3 10.2 15.1
5 22.3 26.6 10.7 10.7
6 6.9 33.5 56 19.9 36.2 36.2
7 38.8 51.6 13.8 62.9 10.7
8 11.2 39 22.3 35.3 19.2
9 40.3 74.3 51 69.6 26.5 18
10 40.3 74.3 51 69.6 26.5 18

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г2,5=13.8, Г2,6=26.6, Г3,9=0, Г3,10=0, Г5,2=6.9, Г5,7=10.2, Г5,8=10.7, Г6,1=18.1, Г7,9=0, Г7,10=0, Г8,9=0, Г8,10=0, Г9,10=18, Г10,9=18,
Максимальное значение имеет Г2,6=26.6
Удалим из матрицы стоимости строку 2 и столбец 6. Внесем в текущий ориентированный граф дугу (2,6)

1 2 5 7 8 9 10
3 71.8 50.9 10.2 15.1
5 22.3 10.7 10.7
6 6.9 33.5 56 19.9 36.2 36.2
7 38.8 51.6 13.8 10.7
8 11.2 39 22.3 19.2
9 40.3 74.3 51 26.5 18
10 40.3 74.3 51 26.5 18

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

1 2 5 7 8 9 10
3 71.8 50.9 10.2 15.1
5 22.3 10.7 10.7
6 33.5 56 19.9 36.2 36.2
7 38.8 51.6 13.8 10.7
8 11.2 39 22.3 19.2
9 40.3 74.3 51 26.5 18
10 40.3 74.3 51 26.5 18

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

1 2 5 7 8 9 10
3 71.8 37.1 10.2 15.1
5 22.3 10.7 10.7
6 19.7 56 19.9 36.2 36.2
7 38.8 51.6 10.7
8 11.2 39 8.5 19.2
9 40.3 74.3 37.2 26.5 18
10 40.3 74.3 37.2 26.5 18

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г3,9=0, Г3,10=0, Г5,2=39, Г5,7=10.2, Г5,8=10.7, Г6,1=30.9, Г7,5=8.5, Г7,9=0, Г7,10=0, Г8,9=0, Г8,10=0, Г9,10=18, Г10,9=18,
Максимальное значение имеет Г5,2=39
Удалим из матрицы стоимости строку 5 и столбец 2. Внесем в текущий ориентированный граф дугу (5,2)

Читайте также  Линейная регрессия. Прямые линии среднеквадратической регрессии
1 5 7 8 9 10
3 37.1 10.2 15.1
6 19.7 56 19.9 36.2 36.2
7 38.8 10.7
8 11.2 8.5 19.2
9 40.3 37.2 26.5 18
10 40.3 37.2 26.5 18

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

1 5 7 8 9 10
3 37.1 10.2 15.1
6 56 19.9 36.2 36.2
7 38.8 10.7
8 11.2 8.5 19.2
9 40.3 37.2 26.5 18
10 40.3 37.2 26.5 18

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

1 5 7 8 9 10
3 37.1 4.4
6 45.8 9.2 36.2 36.2
7 38.8
8 11.2 8.5 9
9 40.3 37.2 16.3 7.3
10 40.3 37.2 16.3 7.3

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г3,7=9, Г3,9=0, Г3,10=0, Г6,1=20.4, Г7,5=8.5, Г7,8=4.4, Г7,9=0, Г7,10=0, Г8,9=0, Г8,10=0, Г9,10=7.3, Г10,9=7.3,
Максимальное значение имеет Г6,1=20.4
Удалим из матрицы стоимости строку 6 и столбец 1. Внесем в текущий ориентированный граф дугу (6,1)

5 7 8 9 10
3 37.1 4.4
7
8 8.5 9
9 37.2 16.3 7.3
10 37.2 16.3 7.3

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

5 7 8 9 10
3 4.4
7
8 8.5 9
9 37.2 16.3 7.3
10 37.2 16.3 7.3

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

5 7 8 9 10
3 4.4
7
8 8.5 9
9 37.2 16.3 7.3
10 37.2 16.3 7.3

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г3,7=9, Г3,9=0, Г3,10=0, Г7,5=8.5, Г7,8=4.4, Г7,9=0, Г7,10=0, Г8,9=0, Г8,10=0, Г9,10=7.3, Г10,9=7.3,
Максимальное значение имеет Г3,7=9
Удалим из матрицы стоимости строку 3 и столбец 7. Внесем в текущий ориентированный граф дугу (3,7)

5 8 9 10
7
8 8.5
9 37.2 7.3
10 37.2 7.3

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

5 8 9 10
7
8 8.5
9 37.2 7.3
10 37.2 7.3

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

5 8 9 10
7
8
9 28.7 7.3
10 28.7 7.3

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г7,8=7.3, Г7,9=0, Г7,10=0, Г8,5=28.7, Г8,9=0, Г8,10=0, Г9,10=7.3, Г10,9=7.3,
Максимальное значение имеет Г8,5=28.7
Удалим из матрицы стоимости строку 8 и столбец 5. Внесем в текущий ориентированный граф дугу (8,5)

8 9 10
7
9 7.3
10 7.3

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

8 9 10
7
9 7.3
10 7.3

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

8 9 10
7
9
10

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

9 10
7
10

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

Читайте также  Главный центр
8 10
7
9

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

9 10
7
9

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

8 9
7
10

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

8 9
9
10

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

8 10
9
10

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

Мы рассмотрели все возможные ветви алгоритма, теперь необходимо выбрать из полученых в результате рассмотрения каждой ветви значений нижней границы — минимальное. Это и будет оптимальной длиной пути коммивояжера
Минимальное значение имеет НГр=360.9
Соответствующий оптимальный контур включет дуги:, (4, 3), (1, 4), (2, 6), (5, 2), (6, 1), (3, 7), (8, 5), (9, 8), (7, 10), (10, 9)

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