Решение задачи коммивояжера методом ветвей и границ

(алгоритм Литтла)

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

Рассмотрим алгоритм поиска гамильтонова цикла минимальной длины на графе с вершинами (алгоритм Литтла). Если между вершинами и нет дуги, то ставится символ . Этот же символ ставится на главной диагонали, что означает запрет на возвращение в вершину, через которую уже проходил цикл. Основная идея метода состоит в том, что сначала строят нижнюю границу длин множества гамильтоновых циклов . Затем множество циклов разбивается на два подмножества таким образом, что первое подмножество состояло из гамильтоновых циклов, содержащих некоторую дугу , а другое подмножество не содержало эту дугу. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества гамильтоновых циклов. Полученные нижние границы подмножеств и оказываются не меньше нижней границы для всего множества гамильтоновых циклов, то есть

.

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

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

Рис. 4.2