Примеры решения задач

Пример 1. Пусть задан граф G, изображенный на рис. 16.24. Решить задачу коммивояжера для заданного графа, используя алгоритм Хелда─Карпа.

Рис. 16.24. Исходный граф

Решение: Построим матрицу расстояний заданного графа:

1. В соответствии с заданным алгоритмом определяем прямые пути из вершины x ₁ в вершину x_j, где j = (2, 3, 4): d ₁₂= 3; d ₁₃= 1; d ₁₄= 4.

2. Теперь определяем пути из вершины x ₁ в вершину x_j через одну промежуточную вершину:

d ³₁₂ = d ₁₃ + d ₃₂ = 1 + 5 = 6; d ³₁₄ = d ₁₃ + d ₃₄ = 1 + 4 = 5; d ²₁₃ = d ₁₂ + d ₂₃ = 3 + 5 = 8;

d ²₁₄ = d ₁₂ + d ₂₄ = 3 + 6 = 9; d ⁴₁₂ = d ₁₄ + d ₄₂ = 2 + 6 = 8; d ⁴₁₃ = d ₁₄ + d ₄₃ = 2 + 4 = 6.

3. Определяем пути из вершины x ₁ в вершину x_j через две промежуточные вершины:

d ^3,4₁₂ = d ³₁₄ + d ₄₂ = d ₁₃ + d ₃₄ + d ₄₂ = 1 + 4 + 6 = 11; d ^2,4₁₃ = d ²₁₄ + d ₄₃ = d ₁₂ + d ₂₄ + d ₄₃ = 3 + 6 + 4 = 13; d ^2,3₁₄ = d ²₁₃ + d ₃₄ = d ₁₂ + d ₂₃ + d ₃₄ = 3 + 5 + 4 = 12;

d ^4,3₁₂ = d ⁴₁₃ + d ₃₂ = d ₁₄ + d ₄₃ + d ₃₂ = 2 + 4 + 5 = 11; d ^4,2₁₃ = d ⁴₁₂ + d ₂₃ = d ₁₄ + d ₄₂ + d ₂₃

= 2 + 6 + 5 = 13; d ^3,2₁₄ = d ³₁₂ + d ₂₄ = d ₁₃ + d ₃₂ + d ₂₄ = 1 + 5 + 6 = 12.

4. Теперь к полученной длине пути добавляем длину возвращения в исходный пункт:

d ₁₂ = d ^3,4₁₂ (или d ⁴³₁₂) + d ₂₁ = 11 + 3 = 14; d ₁₃ = d ²⁴₁₃ (или d ⁴²₁₃) + d ₃₁ = 13 + 1 = =14; d ₁₄ = d ²³₁₄ (или d ³²₁₄) + d ₄₁ = 12 + 2 = 14.

Таким образом, в результате работы алгоритма выяснилось, что длина пути коммивояжера при любом варианте обхода вершин графа одинакова и равна 14.

Пример 2. Пусть задан граф G = (X, U). Решить задачу о коммивояжере для заданного графа геометрическим методом.

Решение: Зададим граф G = (X, U) матрицей расстояний, а поскольку граф неориентированный, то для его однозначного задания вполне достаточно треугольной матрицы

		1	2	3	4	5	6
R =	1	¥	40	29	66	52	36	.
	2		¥	41	63	37	50
	3			¥	38	48	42
	4				¥	28	56
	5					¥	32
	6						¥

1. Определяем по матрице R элемент с максимальным весом. Это элемент r ₁₄ = 66. Вершины x ₁ и x ₄ фиксируем.

2. Строим треугольники с основанием x ₁ – x ₃ (рис. 16.25,а).

Вычисляем периметры получившихся треугольников:

П₁₂₄ = 40 + 63 = 103;

П₁₃₄ = 29 + 38 = 67;

П₁₅₄ = 52 + 28 = 80;

П₁₆₄ = 36 + 56 = 92.

3. Выбираем треугольник П₁₂₄, имеющий максимальную длину. Фиксируем вершины x ₁, x ₂, x ₄. Выделяем два звена L₁ = (x ₁ – x ₄) и L₂= (x ₁ – x ₂ и x ₂ – x ₄) (рис. 16.25, б).

а б

Рис. 16.25. Построение пути коммивояжера а – шаг 1; б – шаг 2

4. Подсчитываем значения DR для вершин x ₃, x ₅, x ₆.

а) Для вершины x ₃:

DR₁₂ = r ₁₃ + r ₃₂ - r ₁₂ = 29 + 41 - 40 = 30;

DR₁₄ = r ₁₃ + r ₃₄ - r ₁₄ = 29 + 38 - 66 = 1;

DR₂₄ = r ₂₃ + r ₃₄ - r ₂₄ = 41 + 38 - 63 = 16.

б) Для вершины x ₅:

DR₁₂ = r ₁₅ + r ₅₂ - r ₁₂ = 52 + 37 - 40 = 49;

DR₁₄ = r ₁₅ + r ₅₄ - r ₁₄ = 52 + 28 - 66 = 24;

DR₂₄ = r ₂₅ + r ₅₄ - r ₂₄ = 37 + 28 - 63 = 2.

в) Для вершины x ₆:

DR₁₂ = r ₁₆ + r ₆₂ - r ₁₂ = 36 + 50 - 40 = 46;

DR₁₄ = r ₁₆ + r ₆₄ - r ₁₄ = 36 + 56 - 66 = 26;

DR₂₄ = r ₂₆ + r ₆₄ - r ₂₄ = 50 + 56 - 63 = 43.

5. В результате проведенных подсчетов получилось, что вершина x ₅ должна быть отнесена к отрезку x ₂ – x ₄, вершины x ₃ и x ₆ относятся к отрезку x ₁ – x ₄. Следовательно, заменяем отрезок x ₂ – x ₄ двумя отрезками x ₂ – x ₅ и x ₅ – x ₄. Сравниваем полученные значения DR₁₄ для вершин x ₃ (DR₁₄ = 1) и x ₆ (DR₁₄ = 26). Вершину (x ₃), соответствующую меньшему из двух значению DR₁₄, оставляем, а через вершину x ₆ строим обход x ₁ – x ₆ и x ₆ – x ₄ (рис. 16.25, в). После чего переходим к пункту 6.

6. Для вершины x ₃ подсчитываем значения DR₁₆ и DR₆₄, для того чтобы определить к какому из этих двух отрезков она должна быть отнесена (рис. 16.25,г).

Для вершины x ₃:

DR₁₆ = r ₁₃ + r ₃₆ – r ₁₆ = 29 + 42 – 36 = 35;

DR₆₄ = r ₆₃ + r ₃₄ – r ₆₄ = 42 + 38 – 56 = 24.

Вершину x ₃ отнесем к отрезку x ₄ – x ₆. После этого шага все вершины графа рассмотрены.