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

Рассмотрим задачу коммивояжера с матрицей расстояний:

	-
		-
			-
				-
					-

В качестве нижней оценки H можно выбрать величину S, равную сумме минимальных элементов по строкам матрицы расстояний или величину C, равную сумме минимальных элементов по столбцам. Так как величину нижней оценки необходимо пытаться увеличивать (тем самым уменьшается интервал возможных значений оптимума исходной задачи), то в качестве нижней оценки можно взять максимальное значение величин S и C.

Величина Н= max{2+2+2+1+2, 2+1+2+2+2}=9.

В качестве верхней оценки может быть выбрана величина значения критерия задачи на любом допустимом решении задачи коммивояжера. Применим для построения допустимого решения так называемый “жадный” алгоритм, основанный на следующей стратегии выбора маршрута движения коммивояжера: коммивояжер из очередного города переходит в город, расстояние до которого минимально из тех городов, в которых коммивояжер еще не был (включая и город, из которого начал свой путь коммивояжер). Получим маршрут коммивояжера, проходящий через города r =(1,4,2,3,5,1), длина которого F(r)=10. Отсюда верхняя оценка равна V=10.

Ветвление будем проводить по всем возможным направлениям.

Из города 1 в город 2:

Нижняя оценка H=4+max(2+2+2+2,2+2+2+2)=12.

Верхняя оценка определяется перестановкой r =(1,2,3,5,4,1) и равна V=14.

Из города 1 в город 3:

Нижняя оценка H=3+max(2+2+1+2, 2+1+3+2)=11,

Верхняя оценка определяется перестановкой r =(1,3,5,4,2,1) и равна V=12.

Из города 1 в город 4:

Нижняя оценка H=2+max(2+2+1+2, 2+1+2+2)=9.

Верхняя оценка определяется перестановкой r =(1,4,2,3,5,1) и равна V=10.

Из города 1 в город 5:

Нижняя оценка H=4+max(2+2+1+2, 2+1+2+3)=12.

Верхняя оценка определяется перестановкой r =(1,5,3,4,2,1) равна V=13.

Анализ вариантов позволяет применить процедуру отбрасывания неперспективных направлений. Так как в направлении “из города 1 в город 4” верхняя (достижимая) оценка V=10, а во всех других направлениях нижняя оценка (лучшее, что можно получить в соответствующем направлении) больше этой величины (в направлении” из города 1 в город 2” H=12, “из города 1 в город 3” H=11, “ из города 1 в город 5” H=12.), то все эти направления можно отбросить не в ущерб оптимальному решению исходной задачи коммивояжера.

Продолжаем процедуру ветвления в направлении “из города 1 в город 4”.

Здесь возможны три направления:

“из города 4 в город 2” - H=2+1+max(2+2+2, 2+2+2)=9.

r =(1,4,2,3,5,1), V=10.

“из города 4 в город 3” - H=2+2+max(2+2+3, 2+3+ 2)=11.

r =(1,4,3,5,2,1), V=13.

“из города 4 в город 5” - H=2+3+max(2+2+2, 2+1+2)=11.

Из рассмотренных направлений можно отбросить направления “из города 4 в город 3” и “из города 4 в город 5”, так как в этих направлениях нижние оценки не меньше верхней оценки в направлении ” из города 4 в город 2” V=10.

Продолжаем ветвление в двух направлениях:

“из города 2 в город 3” - H= 2+1+2+max(2+3, 2+2)=10.

r =(1,4,2,3,5,1), V=10.

“ из города 2 в город 5” -H=2+1+2+max(2+2, 2+2)=9.

r =(1,4,2,5,3,1), V=9.

Первое направление отбрасываем и получаем оптимальное решение исходной задачи коммивояжера r’ =(1,4,2,5,3,1), F(r’)=9.

Дата добавления: 2017-02-01