Привет, Вы узнаете о том , что такое алгоритм литтла, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое алгоритм литтла, задачи коммивояжера , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

алгоритм литтла  применяют для поиска решения  задачи коммивояжера  в виде гамильтонова контура. Данный алгоритм используется для поиска оптимального гамильтонова контура в графе, имеющем N вершин, причем каждая вершина i связана с любой другой вершиной j двунаправленной дугой. Каждой дуге приписан вес Сi,j, причем веса дуг строго положительны (Сi,j≥0). Веса дуг образуют матрицу стоимости. Все элементы по диагонали матрицы приравнивают к бесконечности (Сj,j=∞).

В случае, если пара вершин i и j не связана между собой (граф не полносвязный), то соответствующему элементу матрицы стоимости приписываем вес, равный длине минимального пути между вершинами i и j. Если в итоге дуга (i, j) войдет в результирующий контур, то ее необходимо заменить соответствующим ей путем. Матрицу оптимальных путей между всеми вершинами графа можно получить применив алгоритм Данцига или Флойда.

Алгоритм Литтала является частным случаем применения метода "ветвей и границ" для конкретной задачи. Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.

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

1. В каждой строке матрицы стоимости найдем минимальный элемент и вычтем его из всех элементов строки. Сделаем это и для столбцов, не содержащих нуля. Получим матрицу стоимости, каждая строка и каждый столбец которой содержат хотя бы один нулевой элемент.
2. Для каждого нулевого элемента матрицы cij  рассчитаем коэффициент Гi,j, который равен сумме наименьшего элемента i строки (исключая элемент Сi,j=0) и наименьшего элемента j столбца. Из всех коэффициентов  Гi,j выберем такой, который является максимальным Гk,l=max{Гi,j}. В гамильтонов контур вносится соответствующая дуга (k,l).
3. Удаляем k-тую строку и столбец l, поменяем на бесконечность значение элемента Сl,k (поскольку дуга (k,l) включена в контур, то обратный путь из l в k недопустим).
4. Повторяем алгоритм шага 1, пока порядок матрицы не станет равным двум.
5. Затем в текущий ориентированный граф вносим две недостающие дуги, определяющиеся однозначно матрицей прядка 2. Получаем гамильтонов контур.

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

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

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

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

Матрица D0:

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

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

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

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

Для каждого нулевого элемента рассчитаем значение Г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. Об этом говорит сайт https://intellect.icu . Внесем в текущий ориентированный граф дугу (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 единицу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Анализ данных, представленных в статье про алгоритм литтла, подтверждает эффективность применения современных технологий для обеспечения инновационного развития и улучшения качества жизни в различных сферах. Надеюсь, что теперь ты понял что такое алгоритм литтла, задачи коммивояжера и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов