Главная|Решения онлайн |Теория | Основные формулы и обозначения |Обратная связь |


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

   Алгоритм Литтла применяют для поиска решения задачи коммивояжера в виде гамильтонова контура. Данный алгоритм используется для поиска оптимального гамильтонова контура в графе, имеющем N вершин, причем каждая вершина i связана с любой другой вершиной j двунаправленной дугой. Каждой дуге приписан вес Сi,j, причем веса дуг строго положительны (Сi,j0). Веса дуг образуют матрицу стоимости. Все элементы по диагонали матрицы приравнивают к бесконечности (С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

Пример 2

 

Назад



R336709263964 - WebMoney 41001419134483 - Яндекс Деньги
WebMoneyПонравился сайт? Окажите помощь в развитиияндекс