Алгоритм Литтла – метод решения задачи коммивояжера

Алгоритм Литтла применяют для поиска решения задачи коммивояжера в виде гамильтонова контура. Данный алгоритм используется для поиска оптимального гамильтонова контура в графе, имеющем N вершин, причем каждая вершина i связана с любой другой вершиной j двунаправленной дугой. Каждой дуге приписан вес С_i,j, причем веса дуг строго положительны (С_i,j≥0). Веса дуг образуют матрицу стоимости. Все элементы по диагонали матрицы приравнивают к бесконечности (С_j,j=∞).
В случае, если пара вершин i и j не связана между собой (граф не полносвязный), то соответствующему элементу матрицы стоимости приписываем вес, равный длине минимального пути между вершинами i и j. Если в итоге дуга (i, j) войдет в результирующий контур, то ее необходимо заменить соответствующим ей путем. Матрицу оптимальных путей между всеми вершинами графа можно получить применив алгоритм Данцига или Флойда.
Алгоритм Литтала является частным случаем применения метода “ветвей и границ” для конкретной задачи. Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.
Алгоритм Литтла

1. 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
Пример 2