методом ветвей и границ

Задача про коммивояжера. Пусть n есть городов. Известна матрица расстояний между любой парой городов .Выезжая из начального города, коммивояжер должен побывать во всех городах ровно один раз и вернуться в начальный город. Необходимо узнать в каком порядке нужно объезжать города, чтобы пройденный путь был минимальным.

Введем неизвестные

Тогда получаем задачу

Первая группа ограничений говорит о том , что коммивояжер выезжает из каждого города один раз, а вторые о том, что он один раз въезжает в каждый город.

Пример:Рассмотрим пример объезда 4 городов. Задана матрица расстояний между городами:

	i \ j	1	2	3	4
	1	¥	4	5	3
	2	6	¥	7	2
	3	5	7	¥	8
	4	4	2	3	¥

Необходимо найти последовательность объезда городов так чтобы путь был минимальным.

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

i \ j	1	2	3	4
1	¥	4	5	3	3
2	6	¥	7	2	2
3	5	7	¥	8	5
4	4	2	3	¥	2

i \ j	1	2	3	4
1	¥	1	2	0
2	4	¥	5	0
3	0	2	¥	3
4	2	0	1	¥
	0	0	1	0

Обозначим полученную матрицу через .

В ней на месте минимальных переездов стоят 0.

Посчитаем оценку данного множества:

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

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

Нашли первую пару городов объезда - переезд из города 2 в город 4. Проверим это. Для этого множество разобьем на два множества: .

Множество - множество всех переездов, в которых разрешен переезд из города 2 в город 4. Этому множеству соответствует матрица, полученная из матрицы вычеркиванием 2 строки и 4 столбца и запретом обратного переезда, т.е. элемент .

Множество - - множество всех переездов, в которых запрещен переезд из города 2 в город 4. Этому множеству соответствует матрица, полученная из матрицы заменой элемента .

Рассмотрим :

i \ j	1	2	3
1	¥	1	1
3	0	2	¥
4	2		0

i \ j	1	2	3
1	¥	1	1	1
3	0	2	¥	0
4	2		0	0

i \ j	1	2	3
1	¥	0	0
3	0	2	¥
4	2		0
	0	0	0

Рассмотрим :

i \ j	1	2	3	4
1	¥	1	1	0
2	4	¥	4
3	0	2	¥	3
4	2	0	0	¥

Так как то дальше дробить мы будем множество . Для этого оценим нули множество :

Нашли следующую пару объезда: .

Дробим множество .

Рассмотрим :

i \ j	2	3
1	0
4		0

Мы получили матрицу второго порядка. Дальнейшее дробление невозможно. Получили объезд:

Длина объезда:

Рассмотрим :

i \ j	1	2	3
1	¥	0	0
3		2	¥
4	2		0

Так как , то найденный переход оптимален и его длина 14.

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