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

Табл.3

ji	1	2	4	6
2	0	∞	0	8
3	22	0	26	∞
4	3	0	∞	0
5	∞	0	10	47

Табл.4

ji	1	2	3	4	6
2	0	∞	8	0	8
3	22	0	∞	26	4
4	3	0	17	∞	0
5	∞	0	17	10	47
6	37	12	∞	2	∞	2
8

Определим константы приведения для этих матриц

,

Следовательно

,

Так как

, то дальнейшему ветвлению подлежит подмножество . Находим степени нулей матрицы.

ji	1	2	4	6
2	03	∞	02	8
3	22	022	26	∞
4	3	00	∞	08
5	∞	010	10	47

Претендентом к включению в гамильтонов контур станет дуга (3;2). Разбиваем множество

на два и .

ji	1	4	6
2	0	0	8
4	3	∞	0
5	∞	10	47	10

ji	1	2	4	6
2	0	∞	0	8
3	22	∞	26	∞	22
4	3	0	∞	0
5	∞	0	10	47

Очевидно

,

Следовательно, очередному ветвлению нужно подвергнуть подмножество

.

Переходим к ветвлению подмножества

. Определяем степени нулей. Претендентом на включение в гамильтонов контур является дуга (5;4). Разбиваем множество на два подмножества: и .

Находим нижние границы

,

Следовательно, очередному ветвлению нужно подвергнуть подмножество

. Но его матрица имеет размерность . Поэтому в гамильтонов контур следует включить дуги, соответствующие в матрице нулевым элементам.

Определим полученный гамильтонов контур. В него вошли дуги

Длина контура равна

Так как границы оборванных ветвей больше длины контура 1 – 5 – 4 – 6 – 3 – 2 – 1, то этот контура имеет наименьшую длину.

алгоритм крускал коммивояжер

Рис.25

Выводы

Задача коммивояжера является частичным случаем гамильтоновой задачи о путешественнике. Суть задачи коммивояжера состоит в нахождении суммарной минимальной характеристики (расстояния, стоимости проезда и т.д.), при этом коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал.

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

Основная идея метода Литтла состоит в том, что вначале строят нижнюю границу длин маршрутов для всего множества гамильтоновых контуров

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

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

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

Используя ЭВМ, методом ветвей и границ можно решить задачи коммивояжера для

.

6. Список использованной литературы

1. О. Е. Акимов «Дискретная математика. Логика, группы, графы», Москва, 2003, 376 с., ил., изд. дом «Лаборатория базовых знаний».

2. Ф. А. Новиков «Дискретная математика для программистов» С.-Петербург, 2002 г. 304 с., ил., изд. дом «Питер».

3. В. М. Бондарев «Основы программирования» 1998 г., 368 с. изд. дом «Феникс»