Категории задач
Uchimatchast
About this Course HTML and CSS Are the Tools You Need to Build a Website Coding for beginners might seem hard. However, starting with the basics is a great way.
  • turitor@admin.com
  • +01145928421
Теория Работа проверена: LiraDrakon11 Время решения: 10 мин Сложность: 3.7

На странице представлен фрагмент

Попробовать AI 🤖

Реши любую задачу с помощью нейросети.

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

0 60.8 58.3 47.2 62.6 40.3 79.1 29.2 40.3 40.3
60.8 0 108.2 105.9 40.3 47.2 91.9 57.0 74.3 74.3
58.3 108.2 0 26.9 87.3 98.6 60.4 51.5 36.4 36.4
47.2 105.9 26.9 0 95.1 84.9 82.0 55.0 47.4 47.4
62.6 40.3 87.3 95.1 0 73.8 54.1 40.3 51.0 51.0
40.3 47.2 98.6 84.9 73.8 0 110.1 60.2 76.5 76.5
79.1 91.9 60.4 82.0 54.1 110.1 0 51.0 40.3 40.3
29.2 57.0 51.5 55.0 40.3 60.2 51.0 0 18.0 18.0
40.3 74.3 36.4 47.4 51.0 76.5 40.3 18.0 0 0
40.3 74.3 36.4 47.4 51.0 76.5 40.3 18.0 0 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 ∞ 0
40.3 74.3 36.4 47.4 51.0 76.5 40.3 18.0 0 ∞

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

1 2 3 4 5 6 7 8 9 10
1 ∞ 31.6 29.1 18 33.4 11.1 49.9 0 11.1 11.1
2 20.5 ∞ 67.9 65.6 0 6.9 51.6 16.7 34 34
3 31.4 81.3 ∞ 0 60.4 71.7 33.5 24.6 9.5 9.5
4 20.3 79 0 ∞ 68.2 58 55.1 28.1 20.5 20.5
5 22.3 0 47 54.8 ∞ 33.5 13.8 0 10.7 10.7
6 0 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 0 0
8 11.2 39 33.5 37 22.3 42.2 33 ∞ 0 0
9 40.3 74.3 36.4 47.4 51 76.5 40.3 18 ∞ 0
10 40.3 74.3 36.4 47.4 51 76.5 40.3 18 0 ∞

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

1 2 3 4 5 6 7 8 9 10
1 ∞ 31.6 29.1 18 33.4 4.2 36.1 0 11.1 11.1
2 20.5 ∞ 67.9 65.6 0 0 37.8 16.7 34 34
3 31.4 81.3 ∞ 0 60.4 64.8 19.7 24.6 9.5 9.5
4 20.3 79 0 ∞ 68.2 51.1 41.3 28.1 20.5 20.5
5 22.3 0 47 54.8 ∞ 26.6 0 0 10.7 10.7
6 0 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 0 0
8 11.2 39 33.5 37 22.3 35.3 19.2 ∞ 0 0
9 40.3 74.3 36.4 47.4 51 69.6 26.5 18 ∞ 0
10 40.3 74.3 36.4 47.4 51 69.6 26.5 18 0 ∞

Для каждого нулевого элемента рассчитаем значение Г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 0 11.1 11.1
2 20.5 ∞ 65.6 0 0 37.8 16.7 34 34
3 31.4 81.3 0 60.4 64.8 19.7 24.6 9.5 9.5
5 22.3 0 54.8 ∞ 26.6 0 0 10.7 10.7
6 0 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 0 0
8 11.2 39 37 22.3 35.3 19.2 ∞ 0 0
9 40.3 74.3 47.4 51 69.6 26.5 18 ∞ 0
10 40.3 74.3 47.4 51 69.6 26.5 18 0 ∞

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

1 2 4 5 6 7 8 9 10
1 ∞ 31.6 18 33.4 4.2 36.1 0 11.1 11.1
2 20.5 ∞ 65.6 0 0 37.8 16.7 34 34
3 21.9 71.8 ∞ 50.9 55.3 10.2 15.1 0 0
5 22.3 0 54.8 ∞ 26.6 0 0 10.7 10.7
6 0 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 0 0
8 11.2 39 37 22.3 35.3 19.2 ∞ 0 0
9 40.3 74.3 47.4 51 69.6 26.5 18 ∞ 0
10 40.3 74.3 47.4 51 69.6 26.5 18 0 ∞

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

1 2 4 5 6 7 8 9 10
1 ∞ 31.6 0 33.4 4.2 36.1 0 11.1 11.1
2 20.5 ∞ 47.6 0 0 37.8 16.7 34 34
3 21.9 71.8 ∞ 50.9 55.3 10.2 15.1 0 0
5 22.3 0 36.8 ∞ 26.6 0 0 10.7 10.7
6 0 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 0 0
8 11.2 39 19 22.3 35.3 19.2 ∞ 0 0
9 40.3 74.3 29.4 51 69.6 26.5 18 ∞ 0
10 40.3 74.3 29.4 51 69.6 26.5 18 0 ∞

Для каждого нулевого элемента рассчитаем значение Г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 ∞ 0 0 37.8 16.7 34 34
3 21.9 71.8 50.9 55.3 10.2 15.1 0 0
5 22.3 0 ∞ 26.6 0 0 10.7 10.7
6 0 6.9 33.5 ∞ 56 19.9 36.2 36.2
7 38.8 51.6 13.8 62.9 ∞ 10.7 0 0
8 11.2 39 22.3 35.3 19.2 ∞ 0 0
9 40.3 74.3 51 69.6 26.5 18 ∞ 0
10 40.3 74.3 51 69.6 26.5 18 0 ∞

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

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

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

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

Для каждого нулевого элемента рассчитаем значение Г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 0 0
5 22.3 0 ∞ 0 0 10.7 10.7
6 0 6.9 33.5 56 19.9 36.2 36.2
7 38.8 51.6 13.8 ∞ 10.7 0 0
8 11.2 39 22.3 19.2 ∞ 0 0
9 40.3 74.3 51 26.5 18 ∞ 0
10 40.3 74.3 51 26.5 18 0 ∞

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

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

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

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

Для каждого нулевого элемента рассчитаем значение Г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 0 0
6 0 19.7 56 19.9 36.2 36.2
7 38.8 0 ∞ 10.7 0 0
8 11.2 8.5 19.2 ∞ 0 0
9 40.3 37.2 26.5 18 ∞ 0
10 40.3 37.2 26.5 18 0 ∞

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

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

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

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

Для каждого нулевого элемента рассчитаем значение Г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 0 4.4 0 0
7 0 ∞ 0 0 0
8 8.5 9 ∞ 0 0
9 37.2 16.3 7.3 ∞ 0
10 37.2 16.3 7.3 0 ∞

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

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

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

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

Для каждого нулевого элемента рассчитаем значение Г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 0 0 0 0
8 8.5 ∞ 0 0
9 37.2 7.3 ∞ 0
10 37.2 7.3 0 ∞

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

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

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

5 8 9 10
7 ∞ 0 0 0
8 0 ∞ 0 0
9 28.7 7.3 ∞ 0
10 28.7 7.3 0 ∞

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

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

8 9 10
7 ∞ 0 0
9 7.3 ∞ 0
10 7.3 0 ∞

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

8 9 10
7 ∞ 0 0
9 0 ∞ 0
10 0 0 ∞

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

В строке 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 ∞ 0
9 0 0

В строке 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 0 0
9 ∞ 0

В строке 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 ∞ 0
10 0 0

В строке 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 0 ∞
10 0 0

В строке 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 0 0
10 0 ∞

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

   

Купить уже готовую работу

Подробнее
Курсовая комплексный анализ вариант 2
Курсовая работа, Анализ хозяйственной деятельности
Выполнил: reinc
1800

Так же вы можете купить уже выполненные похожие работы. Для удобства покупки работы размещены на независимой бирже. Подробнее об условиях покупки тут.

 

Также искали:

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

d+b-a=3 c+f+g-b=3 d+c-m=0 22*a+220*b+150*f=-300 22*a+50*d-150*c-220*b=0 180*g-150*f=0 150*c+200*m-180*g=0

Табличный симплекс-метод

Пример Алгоритм Флойда

4.49
LiraDrakon11
Владею глубокими знаниями в области экономики, банковского дела, логистики, маркетинга и менеджмента. Практический опыт (15 лет) в написании дипломных, курсовых работ, отчетов по практике, индивидуальных заданий, контрольных, диссертаций!!!
Нанять автора

Рейтинг сайтов по написанию работ