Постановка задачи. Рассмотрим задачу о коммивояжере. Имеются n городов, расстояния стоимость проезда, расход горючего на дорогу и т.д. между которыми известны. Коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал.
Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние стоимость проезда и т.д. будет минимальным. Очевидно, что задача коммивояжера это задача отыскания кратчайшего гамильтонова цикла в полном графе. Можно предложить следующую простую схему решения задачи коммивояжера сгенерировать все n возможных перестановок вершин полного графа, подсчитать для каждой перестановки длину маршрута и выбрать кратчайший. Однако, n с ростом n растет быстрее, чем любой полином от n, и даже быстрее, чем. Таким образом, решение задачи коммивояжера методом полного перебора оказывается практически неосуществимым, даже при достаточно небольших n. Решить задачу коммивояжера также можно с помощью алгоритма Крускала и деревянного алгоритма.
Эти методы ускоряют разработку алгоритма по сравнению с методом полного перебора, однако не всегда дают оптимальное решение. Существует метод решения задачи коммивояжера, который дает оптимальное решение. Этот метод называется методом ветвей и границ.
Решение задачи коммивояжера методом ветвей и границ по-другому называют алгоритмом Литтла. Если считать города вершинами графа, а коммуникации i, j его дугами, то требование нахождения минимального пути, проходящего один и только один раз через каждый город, и возвращения обратно, можно рассматривать как нахождение на графе гамильтонова контура минимальной длины. Для практической реализации идеи метода ветвей и границ применительно к задаче коммивояжера нужно найти метод определения нижних границ подмножества и разбиения множества гамильтоновых контуров на подмножества ветвление.
Определение нижних границ базируется на том утверждении, что если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять число, то задача останется эквивалентной прежней, то есть оптимальность маршрута коммивояжера не изменится, а длина любого гамильтонова контура изменится на данную величину. Опишем алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами.
Граф представляют в виде матрицы его дуг. Если между вершинами Xi и Xj нет дуги, то ставится символ. Алгоритм Литтла для решения задачи коммивояжера можно сформулировать в виде следующих правил 1. Находим в каждой строке матрицы минимальный элемент и вычитаем его из всех элементов соответствующей строки. Получим матрицу, приведенную по строкам, с элементами . 2. Если в матрице, приведенной по строкам, окажутся столбцы, не содержащие нуля, то приводим ее по столбцам.
Для этого в каждом столбце матрицы выбираем минимальный элемент, и вычитаем его из всех элементов соответствующего столбца. Получим матрицу, каждая строка и столбец, которой содержит хотя бы один нуль. Такая матрица называется приведенной по строкам и столбцам. 3. Суммируем элементы и, получим константу приведения, которая будет нижней границей множества всех допустимых гамильтоновых контуров, то есть . 4. Находим степени нулей для приведенной по строкам и столбцам матрицы. Для этого мысленно нули в матице заменяем на знак и находим сумму минимальных элементов строки и столбца, соответствующих этому нулю. Записываем ее в правом верхнем углу клетки . 5. Выбираем дугу, для которой степень нулевого элемента достигает максимального значения . 6. Разбиваем множество всех гамильтоновых контуров на два подмножества и. Подмножество гамильтоновых контуров содержит дугу ее не содержит.
Для получения матрицы контуров, включающих дугу, вычеркиваем в матрице строку и столбец. Чтобы не допустить образования негамильтонова контура, заменим симметричный элемент на знак . 7. Приводим матрицу гамильтоновых контуров. Пусть - константа ее приведения.
Тогда нижняя граница множества определится так . 8. Находим множество гамильтоновых контуров, не включающих дугу. Исключение дуги достигается заменой элемента в матрице на . 9. Делаем приведение матрицы гамильтоновых контуров. Пусть - константа ее приведения.
Нижняя граница множества определится так . 10. Сравниваем нижние границы подмножества гамильтоновых контуров и. Если, то дальнейшему ветвлению в первую очередь подлежит множество. Если же, то разбиению подлежит множество. Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений. 11. Если в результате ветвлений получаем матрицу, то определяем полученный ветвлением гамильтонов контур и его длину. 12. Сравниваем длину гамильтонова контура с нижними границами оборванных ветвей.
Если длина контура не превышает их нижних границ, то задача решена. В противном случае развиваем ветви подмножеств с нижней границей, меньшей полученного контура, до тех пор, пока не получим маршрут с меньшей длиной или не убедимся, что такого не существует. 3.