Алгоритм решения

Алгоритм решения. Дана матрица расстояний, представленная в таблице 1. Необходимо с помощью алгоритма Литтла решить задачу коммивояжера.

Табл.1 j i 1 Справа к таблице присоединяем столбец Ui, в котором записываем минимальные элементы соответствующих строк. Вычитаем элементы Ui из соответствующих элементов строки матрицы. j i123456Ui 2 Внизу полученной матрицы присоединяем строку Vj, в которой записываем минимальные элементы столбцов.

Вычитаем элементы Vj из соответствующих столбцов матрицы. j i Vj000202 3 В результате вычислений получаем матрицу, приведенную по строкам и столбцам, которая изображена в виде таблицы 2. Табл.2 j i 4 Находим константу приведения. Таким образом, нижней границей множества всех гамильтоновых контуров будет число . 5 Находим степени нулей полностью приведенной матрицы. Для этого как бы заменяем в ней все нули на знак и устанавливаем сумму минимальных элементов соответствующей строки и столбца.

Степени нулей записаны в правых верхних углах клеток, для которых . 6 Определяем максимальную степень нуля. Она равна 19 и соответствует клетке 15. Таким образом, претендентом на включение в гамильтонов контур является дуга 15. 7 Разбиваем множество всех гамильтоновых контуров на два и. Матрицу с дугой 15 получаем табл.2 путем вычеркивания строки 1 и столбца 5. Чтобы не допускать образования негамильтонова контура, заменяем элемент 51 на знак . j i Матрицу гамильтоновых контуров получим из таблицы 2 путем замены элемента 15 на знак . j i 9 Делаем дополнительное приведение матрицы контуров 0. Нижняя граница множества равна . 10 Находим константу приведения для множества контуров. Следовательно, нижняя граница множества равна . 11 Сравниваем нижние границы подмножеств и. Так как, то дальнейшему ветвлению подвергаем множество. На рис.1 представлено ветвление по дуге 15. рис.1 Переходим к ветвлению подмножества. Его приведенная матрица представлена в таблице ниже. j i Узнаем степени нулей матрицы.

Претендентами на включение в гамильтонов контур будут несколько дуг 52 и 63. Для дальнейших расчетов выберем дугу 63. Разбиваем множество на два подмножества и табл. 3 и 4. Чтобы не допустить образования негамильтонова контура, в таблице 3 заменяем элемент 36 на знак Табл.3 j i124620083220264300501047 Табл.4 j i Определим константы приведения для этих матриц Следовательно Так как, то дальнейшему ветвлению подлежит подмножество. Находим степени нулей матрицы. j i Претендентом к включению в гамильтонов контур станет дуга 32. Разбиваем множество на два и . j i14620084305104710 j i Очевидно Следовательно, очередному ветвлению нужно подвергнуть подмножество. Переходим к ветвлению подмножества. Его приведенная матрица представлена в таблице ниже. j i14620300843011503737 Определяем степени нулей.

Претендентом на включение в гамильтонов контур является дуга 54. Разбиваем множество на два подмножества и . j i16208430 j i146200843053737 Находим нижние границы Следовательно, очередному ветвлению нужно подвергнуть подмножество. Но его матрица имеет размерность. Поэтому в гамильтонов контур следует включить дуги, соответствующие в матрице нулевым элементам.

Это дуги 21 и 46. На рис.2 представлено дерево ветвлений. Определим полученный гамильтонов контур.

В него вошли дуги. Длина контура равна. Так как границы оборванных ветвей больше длины контура 1 5 4 6 3 2 1, то этот контура имеет наименьшую длину. рис.25. Выводы Задача коммивояжера является частичным случаем гамильтоновой задачи о путешественнике.

Суть задачи коммивояжера состоит в нахождении суммарной минимальной характеристики расстояния, стоимости проезда и т.д при этом коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал. Существуют несколько методов решения задачи коммивояжера метод полного перебора, с помощью метода ветвей и границ алгоритм Литтла, алгоритма Крускала, деревянного алгоритма и т.д. Однако только метод ветвей и границ дает нам в итоге самое оптимальное решение.

Основная идея метода Литтла состоит в том, что вначале строят нижнюю границу длин маршрутов для всего множества гамильтоновых контуров. Затем все множество контуров разбивают на два подмножества таким образом, чтобы первое подмножество состояло из гамильтоновых контуров, содержащих некоторую дугу i, j, а другое подмножество не содержало этой дуги. Для практической реализации идеи метода ветвей и границ применительно к задаче коммивояжера нужно найти метод определения нижних границ подмножества и разбиения множества гамильтоновых контуров на подмножества ветвление. Такое определение нижних границ базируется на том утверждении, что если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять число, то задача останется эквивалентной прежней, то есть оптимальность маршрута коммивояжера не изменится, а длина любого гамильтонова контура изменится на данную величину. Используя ЭВМ, методом ветвей и границ можно решить задачи коммивояжера для . 6.