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

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

Поскольку нижняя граница этого подмножества (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.

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

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

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

Зачатки водяного отопления

Первой по времени возникновения действительно централизованной системой отопления была дымо-трубная система. Дата и изобретатель ее неизвестны, но все литературные источники, упоминающие о начале применения ее в разных странах Европы, указывают на то, что туда она была перенесена из Англии; поэтому Англия является, видимо, родиной этой дымо-трубной системы. Идея ее состоит в следующем. От обычной…

Реферат