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

Пусть задана следующая исходная матрица весов (расстояний) c_ij.

	j=1	j=2	j=3	j=4	j=5	j=6
i=1	∞
i=2		∞
i=3			∞
i=4				∞
i=5					∞
i=6						∞

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

Имеется граф:

2

1 3

6 4

Решаем задачу о назначениях.

	j=1	j=2	j=3	j=4	j=5	j=6
i=1					0^*
i=2						0^*
i=3				0^*
i=4			0^*
i=5	0^*
i=6		0^*

2

1 3

I=30

Разрываем цепь с наименьшем количеством дуг(вес соответствующей дуги становится равным ∞)

P₀=30

P₁=31

C₁₅=∞ C₅₁=∞

P₂=31

C₃₄=∞ C₄₃=∞ C₃₄=∞ C₄₃=∞

	P3=34		P4=33		P5=33		P6=34

Если C₁₅=∞, I=31

1 2 3

6 5 4

Восстанавливаем 1-5, а 5-1-разрываем.

1 2 3

I=31

6 5 4

C₁₅=∞, C₃₄=∞

2

1 3

I=34

6 5 4

C₁₅=∞, C₄₃=∞

1 3

I=33

6 4

C₅₁=∞, C₃₄=∞

1 3

I=33

6 4

C₅₁=∞, C₄₃=∞

2

1 3

I=34

6 5 4

Решение задачи о наименьшем покрытии

Дата добавления: 2015-08-21