Решение задачи коммивояжёра

РефератПомощь в написанииУзнать стоимостьмоей работы

Поскольку нижняя граница этого подмножества (5,4) меньше, чем подмножества (5*, 4*), то ребро (5,4) включаем в маршрут. Поскольку нижняя граница этого подмножества (3,1) меньше, чем подмножества (3*, 1*), то ребро (3,1) включаем в маршрут. Поскольку нижняя граница этого подмножества (2,5) меньше, чем подмножества (2*, 5*), то ребро (2,5) включаем в маршрут. Поскольку нижняя граница этого… Читать ещё >

Решение задачи коммивояжёра (реферат, курсовая, диплом, контрольная)

Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр — странствующий торговец) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз.

1. Задача

Требуется найти кратчайший из замкнутых маршрутов, проходящих точно по одному разу через каждый из шести городов A1, A2,…, A6. Задана матрица расстояний между любыми парами городов, причём расстояние от города Ai до города Aj может не совпадать с расстоянием от Ai до Aj. Элемент матрицы aij считается равным расстоянию от Ai до Aj, где с = m + n.


	A1.	A2.	A3.	A4.	A5.	A6.
A1.	;	c+2.	2c.	c+3.	2c.	c+1.
A2.	c.	;	c+5.	c-1.	c-1.	3c.
A3.	c.	c+1.	;	c+7.	c+2.	c+3.
A4.	c-1.	c+2.	c.	;	c+1.	c-1.
A5.	c+5.	c+2.	c.	c.	;	2c.
A6.	c.	c+1.	c+2.	c+5.	c+7.	;

Решение.

Возьмем в качестве произвольного маршрута:

X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1).

Тогда F (X0) = 4 + 7 + 9 + 3 + 4 + 2 = 29.

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

di = min (j) dij.


i j.							di.
	M.
		M.
			M.
				M.
					M.
						M.

Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:

dj = min (i) dij.


i j.
	M.
		M.
			M.
				M.
					M.
						M.
dj.

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.


i j.
	M.
		M.
			M.
				M.
					M.
						M.

Шаг№ 1.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i, j) и (i*, j*).


i j.							di.
	M.	0(0).				0(0).
		M.		0(0).	0(1).
	0(0).	0(0).	M.
	0(0).			M.		0(0).
			0(1).	0(0).	M.
	0(0).	0(0).				M.
dj.

Наибольшая сумма констант приведения равна (0 + 1) = 1 для ребра (2,5), следовательно, множество разбивается на два подмножества (2,5) и (2*, 5*).

Нижняя граница гамильтоновых циклов этого подмножества:


i j.							di.
	M.
		M.			M.
			M.
				M.
					M.
						M.
dj.

В результате получим другую сокращенную матрицу (5×5), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:


i j.						di.
	M.
			M.
				M.
		M.
					M.
dj.

Поскольку нижняя граница этого подмножества (2,5) меньше, чем подмножества (2*, 5*), то ребро (2,5) включаем в маршрут.

Шаг№ 2.


i j.						di.
	M.	0(0).			0(0).
	0(0).	0(0).	M.
	0(0).			M.	0(0).
		M.	0(1).	0(2).
	0(0).	0(0).			M.
dj.

Наибольшая сумма констант приведения равна (0 + 2) = 2 для ребра (5,4), следовательно, множество разбивается на два подмножества (5,4) и (5*, 4*). коммивояжер матрица математический редукция Нижняя граница гамильтоновых циклов этого подмножества:


i j.						di.
	M.
			M.
				M.
		M.		M.
					M.
dj.

В результате получим другую сокращенную матрицу (4×4), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:


i j.				di.
	M.
		M.

			M.
dj.

Чтобы исключить подциклы, запретим следующие переходы: (4,2).

Поскольку нижняя граница этого подмножества (5,4) меньше, чем подмножества (5*, 4*), то ребро (5,4) включаем в маршрут.

Шаг№ 3.


i j.					di.
	M.	0(0).	0(0).	0(0).
	0(0).	0(0).	M.
	0(0).	M.	0(0).	0(0).
	0(0).	0(0).		M.
dj.

Наибольшая сумма констант приведения равна (0 + 0) = 0 для ребра (1,2), следовательно, множество разбивается на два подмножества (1,2) и (1*, 2*).

Нижняя граница гамильтоновых циклов этого подмножества:


i j.					di.
	M.	M.
			M.
		M.
				M.
dj.

В результате получим другую сокращенную матрицу (3×3), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:


i j.			di.
	M.

		M.
dj.

Чтобы исключить подциклы, запретим следующие переходы: (4,2), (4,1),.

Поскольку нижняя граница этого подмножества (1,2) меньше, чем подмножества (1*, 2*), то ребро (1,2) включаем в маршрут.

Шаг№ 4.


i j.				di.
	0(3).	M.
	M.	0(1).	0(3).
	0(1).		M.
dj.

Наибольшая сумма констант приведения равна (3 + 0) = 3 для ребра (3,1), следовательно, множество разбивается на два подмножества (3,1) и (3*, 1*).

Нижняя граница гамильтоновых циклов этого подмножества:


i j.				di.
	M.	M.
	M.
			M.
dj.

В результате получим другую сокращенную матрицу (2×2), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:


i j.		di.

	M.
dj.

Поскольку нижняя граница этого подмножества (3,1) меньше, чем подмножества (3*, 1*), то ребро (3,1) включаем в маршрут.

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,6) и (6,3).

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(2,5), (5,4), (4,6), (6,3), (3,1), (1,2).

Длина маршрута равна F (Mk) = 13.

Показать весь текст

Заполнить форму текущей работой

Другие работы

Аппараты мокрой очистки газов

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

Реферат