Поиск по сайту.

Другие алгоритмы.

Математика : Графы.

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

Written by Sergey Radkevich

Назначение алгоритма

Алгоритм предназначен для нахождения минимального гамильтонова контура на графе с N вершинами.

Входные данные

Если между вершинами i и j нет дуги, то ставится символ "бесконечность". Этот же символ ставится по диагонали, что означает запрет на возвращение в вершину, через которую уже проходил контур.

Идея алгоритма

Основная идея метода состоит в том, что вначале строят нижнюю границу длин множества гамильтоновых контуров омега0. Затем множество контуров разбмвается на два подмножества таким образом, чтобы первое подмножество омега1ij состояло из гамильтоновых контуров, содержащих некоторую дугу (i,j), а другое подмножество омега1not ij не содержало этой дуги. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества гамильтоновых контуров. Полученные нижние границы подмножеств омега1ij и омега1not ij оказываются не меньше нижней границы всего множества гамильтоновых контуров, т.е.

фи(омега0)<=фи1ij,
фи(омега0)<=фи1not ij

Сравнивая нижние границы фи1ij и фи1not ij, можно выделить среди них то, которое с большей вероятностью содержит гамильтонов контур минимальной длины.

Затем одно из подмножеств омега1ij или омега1not ij по аналогичному правилу разбивается на два новых омега2ij и омега2ij. Для них снова отыскиваются нижние границы фи2ij и фи2not ij и т.д. Процесс ветвления продолжается до тех пор, пока не отыщется единственный гамильтонов контур. Его называют первым рекордом. Затем просматривают оборванные ветви. Если их нижние границы больше длины первого рекорда, то задача решена, если же есть такие, для которых нижние границы меньше, чем длина первого рекорда, то подмножество с наименьшей нижней границей подвергается дальнейшему ветвлению, пока не убеждаются, что оно не содержит лучшего гамильтонова контура.

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

Для практической реализации метода ветвей и границ применительно к задаче комивояжера нужно указать прием определения нижних границ подмножеств и разбиения множества гамильтоновых контуров на подмножества (ветвление).

Определение нижних границ

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

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

Константа приведения может быть выбрана в качестве нижней границы длины гамильтоновых контуров.

Разбиение множества контуров на подможества

Для выделения претендентов на включение в множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени теттаij нулевых элементов этой матрицы. Степень нулевого элемента cij равна сумме минимальных элементов в строке i и столбце j при блокировании перехода (i,j) бесконечностью. С наибольшей вероятностью искомому гамильтонову контуру принадлежат дуги с максимальной степенью нуля.

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

Множество контуров, не включающих дугу (i,j) получаем путем замены элемента cij на бесконечность.