Алгоритм Литтла

Теория Работа проверена: LiraDrakon11 Время решения: 10 мин Сложность: 3.7

Имеется схема расположения 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

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

4.49

LiraDrakon11

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

Нанять автора

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

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

LiraDrakon11