Размещено на http://www.allbest.ru/

Министерство образования и науки Украины

Национальный аэрокосмический университет

им. Н.Е. Жуковского

Кафедра компьютерных систем и сетей

Расчетно-графическая работа

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

по курсу «Алгоритмы и методы вычислений»

Выполнила: студентка гр. 525-Б

Кибец Ю.Н.

Проверила: ассистент каф.503

Бутенко В. О.

Харьков 2015

Постановка задачи:

Решить задачу коммивояжёра:

а) методом динамического программирования

б) методом ветвей и границ

в) жадным методом

коммивояжёр программирование оптимизация алгоритм

Вариант № 9:

i	j
	1	2	3	4	5
1	-	4	5	7	6
2	5	-	5	4	7
3	5	4	-	6	6
4	7	5	4	-	7
5	6	8	5	7	-

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

В соответствии с выражением:

W₁(G^*,i) = W(j,i) = r(i,j) + r(j,1),

на первом шаге оптимизации определим расстояния через любые две вершины в начальную (всего таких значений будет, как ранее отмечалось, (n-1)(n-2), т.е. в нашем случае 12):

1. W({2},3) = r(3,2) + r(2,1) = 4+5=9;

2. W({2},4) = r(4,2) + r(2,1) = 5+5=10;

3. W({2},5) = r(5,2) + r(2,1) = 8+5=13;

4. W({3},2) = r(2,3) + r(3,1) = 5+5=10;

5. W({3},4) = r(4,3) + r(3,1) = 4+5=9;

6. W({3},5) = r(5,3) + r(3,1) = 5+5=10;

7. W({4},2) = r(2,4) + r(4,1) = 4+7=11;

8. W({4},3) = r(3,4) + r(4,1) = 6+7=13;

9. W({4},5) = r(5,4) + r(4,1) = 7+7=14;

10. W({5},2) = r(2,5) + r(5,1) =7+6=13;

11. W({5},3) = r(3,5) + r(5,1) = 6+6=12;

12. W({5},4) = r(4,5) + r(5,1) = 7+6=13;

Полученные значения будут использоваться на втором шаге оптимизации (i = 2). В данном случае нужно определить значений.

1. W({3,4},2) = min[r(2,3) + W({4},3); r(2,4) + W({3},4)] =

= min[5+13;4+9] = 13;

2. W({3,5},2) = min[r(2,3) + W({5},3); r(2,5) + W({3},5)] =

= min[5+12;7+9] = 16;

3. W({4,5},2) = min[r(2,4) + W({5},4); r(2,5) + W({4},5)] =

= min[4+13; 7+14] = 17;

4. W({2,4},3) = min[r(3,2) + W({4},2); r(3,4) + W({3},4)] =

= min[4+11; 6+9] = 15;

5. W({2,5},3) = min[r(3,2) + W({5},2); r(3,5) + W({2},5)] =

= min[4+13; 6+13] = 17;

6. W({4,5},3) = min[r(3,4) + W({5},4); r(3,5) + W({4},5)] =

= min[6+13; 6+14] = 19;

7. W({2,3},4) = min[r(4,2) + W({3},2); r(4,3) + W({2},3)] =

= min[5+10; 4+9] = 13;

8. W({2,5},4) = min[r(4,2) + W({5},2); r(4,5) + W({2},5)] =

= min[5+13; 7+13] = 18;

9. W({3,5},4) = min[r(4,3) + W({5},3); r(4,5) + W({3},5)] =

= min[4+12; 7+10] = 16;

10. W({2,3},5) = min[r(5,3) + W({2},3); r(5,2) + W({3},2)] =

= min[5+9; 8+10] = 14;

11. W({2,4},5) = min[r(5,2) + W({4},2); r(5,4) + W({2},4)] =

= min[8+11; 7+10] = 17;

12. W({3,4},5) = min[r(5,3) + W({4},3); r(5,4) + W({3},4)] =

= min[5+13; 7+9] = 16.

Полученные значения будут использоваться на третьем (i = 3) -предпоследнем - шаге. В данном случае необходимо определить значения.

W({3,4,5},2) =min[r(2,3)+W({4,5},3); r(2,4)+W({3,5},4); r(2,5)+W({3,4},5)] =

= min[5+19; 4+16; 7+16] = 20.

W({2,4,5},3) =min[r(3,2)+W({4,5},2); r(3,4)+W({2,5},4); r(3,5)+W({2,4},5)] =

= min[4+17; 6+18; 6+17] = 21;

W({2,3,5},4) =min[r(4,2)+W({3,5},2); r(4,3)+W({2,5},3); r(4,5)+W({2,3},5)] =

= min[5+17; 4+17; 7+14] = 21.

W({2,3,4},5) =min[r(5,2)+W({3,4},2); r(5,3)+W({2,4},3); r(5,4)+W({2,3},4)] =

= min[8+13; 5+15; 7+13] = 20.

Наконец, на последнем шаге, учитывая результаты, полученные на предыдущем шаге, получим:

W({2,3,4,5},1)= min[r(1,2) + W({3,4,5},2); r(1,3) + W({2,4,5},3); r(1,4) + + W({2,3,5},4); r(1,5) + W({2,3,4}),5] = min[4+20; 5+21; 7+21; 6+20] = 24.

Таким образом, минимальная длина маршрут коммивояжёра равна 24.

Данный результат показывает, что, начиная с начальной вершины, коммивояжёру следует двигаться в пункт 2, поскольку дуга (1,2) принадлежит оптимальному маршруту коммивояжёра длиной 24. Принимая во внимание результаты, полученные на предыдущих шагах, можно установить, что оптимальный маршрут коммивояжёра проходит, начиная от начальной, через вершины 2, 4, 3, 5, т.е. гамильтонов контур минимальной длины имеет вид (1 2 4 3 5 1). Иначе, в терминах комбинаторики можно сказать, что искомая перестановка из 4-х чисел 2, 4, 3, 5, характеризующая оптимальное решение, имеет вид (2, 4, 3, 5).

Решение задачи коммивояжёра методом ветвей и границ с помощью алгоритма Литтла

Матрица расстояний представлена в таблице 1. Найти минимальный гамильтонов контур.

Таблица 1

j i	1	2	3	4	5
1	?	4	5	7	6
2	5	?	5	4	7
3	5	4	?	6	6
4	7	5	4	?	7
5	6	8	5	7	?

Справа к таблице присоединяем столбец Ui, в котором записываем минимальные элементы соответствующих строк (выделены синим цветом в табл. 1). Вычитая элементы Ui из соответствующих элементов строки матрицы, получаем табл. 2.

Таблица 2

j i	1	2	3	4	5	Ui
1	?	0	1	3	2	4
2	1	?	1	0	3	4
3	1	0	?	2	2	4
4	3	1	0	?	3	4
5	1	3	0	2	?	5

Внизу полученной матрицы присоединяем строку Vj, в которой записываем минимальные элементы столбцов (выделены зелёным цветом в табл. 2). Вычитая элементы Vj из соответствующих столбцов матрицы, получаем табл. 3.

Таблица 3

j i	1	2	3	4	5
1	?	0	1	3	0
2	0	?	1	0	1
3	0	0	?	2	0
4	2	1	0	?	1
5	0	3	0	2	?
Vj	1	0	0	0	2

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

Таблица 4

j i	1	2	3	4	5
1	?	00	1	3	00
2	00	?	1	02	1
3	00	00	?	2	00
4	2	1	01	?	1
5	00	3	00	2	?

Находим константу приведения:

,

которая, очевидно, представляет собой сумму элементов последнего столбца табл. 2 и последней строки табл.3.

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

Определяем из табл. 4 максимальную степень нулевого элемента. Она равна 2 и соответствует клетке (2;4) (выделено коричневым). Таким образом, претендентом на включение в гамильтонов контур является дуга (2;4).

Разбиваем множество всех гамильтоновых контуров на два подмножества, включающих и не включающих дугу (2;4) соответственно: и . Матрицу, соответствующую подмножеству с дугой (2;4), получаем из табл. 4 путем вычеркивания строки 2 и столбца 4. Чтобы не допустить образования негамильтонова контура (цикла в графе), заменяем элемент (2;4) на знак «?» (табл. 5).

Таблица 5

j i	1	2	3	5
1	?	0	1	0
3	0	0	?	0
4	2	1	0	1
5	0	3	0	?

Поскольку в каждой строке и каждом столбце табл. 5 присутствует как минимум один нулевой элемент, то необходимости в дополнительном приведении матрицы контуров, соответствующей подмножеству , нет. В этом случае = 0 и нижняя граница подмножества равна , т.е. совпадает с величиной .

Матрицу гамильтоновых контуров получим из таблицы 4 путём замены элемента (2;4) на знак «?» (табл. 6).

Таблица 6

j i	1	2	3	4	5
1	?	0	1	3	0
2	0	?	1	?	1
3	0	0	?	2	0
4	2	1	0	?	1
5	0	3	0	2	?

В результате такой замены получилось, что в четвертом столбце табл. 6 нет нулевых элементов. Для этого необходимо осуществить приведение данной таблицы (матрицы, соответствующей подмножеству ). Это достигается путём вычитания минимального элемента четвертого столбца (число 2). В этом случае константа приведения для подмножества контуров , равна 2, а нижняя граница подмножества равна .

Сравнивая нижние границы подмножеств и , устанавливаем, что , поэтому дальнейшему ветвлению подвергаем подмножество , как имеющее меньшую нижнюю границу.

Произведём ветвление подмножества . Для этого необходимо осуществить приведение матрицы, соответствующей этому подмножеству, т.е., матрицы, представленной табл. 5. Поскольку в каждой строке и столбце этой таблицы присутствует как минимум один нулевой элемент, то данная матрица не нуждается в приведении. Далее определяем степени нулей матрицы (табл. 7).

Таблица 7

j i	1	2	3	5
1	?	00	1	00
3	00	00	?	00
4	2	1	02	1
5	00	3	00	?

Определяем из табл. 7 максимальную степень нулевого элемента. Она равна 2 и соответствует клетке (4;3) . Таким образом, претендентом на включение в гамильтонов контур является дуга (4;3).

Разбиваем множество на два подмножества: и . Определим константы приведения для этих подмножеств. Для получения матрицы подмножества вычёркиваем из табл. 7 строку 4 и столбец 3, получая таким образом табл. 8. Поскольку в каждой строке и столбце табл. 8 присутствует как минимум один нулевой элемент, то матрица, соответствующая подмножеству , не нуждается в приведении, поэтому константа её приведения .

Таблица 8

j i	1	2	5
1	?	0	0
3	0	0	0
5	0	3	?

Что касается константы приведения матрицы, соответствующей подмножеству , заменяем в табл. 7 элемент (4;3) на знак «?» и получаем табл. 9. Согласно табл. 9, минимальным элементом строки 4 является 1, поэтому константа приведения подмножества .

Таблица 9

j i	1	2	3	5
1	?	0	1	0
3	0	0	?	0
4	2	1?	?	1
5	0	3	0	?

Следовательно, значение нижней границы подмножества , а подмножества . Так как , то дальнейшему ветвлению подлежит подмножество .

Находим степени нулей таблицы 8, соответствующей подмножеству , и получаем табл. 10.

Таблица 10

j i	1	2	5
1	?	00	00
3	00	0?	00
5	03	3	?

Определяем из табл. 10 максимальную степень нулевого элемента. Она равна 3 и соответствует клетке (5;1) . Таким образом, претендентом на включение в гамильтонов контур является дуга (5;1).

Разбиваем множество на два подмножества: и . Определим константы приведения для этих подмножеств. Для получения матрицы подмножества вычёркиваем из табл. 10 строку 5 и столбец 1, получая таким образом табл. 11. Поскольку в каждой строке и столбце табл. 11 присутствует как минимум один нулевой элемент, то матрица, соответствующая подмножеству , не нуждается в приведении, поэтому константа её приведения .

Таблица 11

j i	2	5
1	0	0?
3	0?	0

Что касается константы приведения матрицы, соответствующей подмножеству , заменяем в табл. 10 элемент (5;1) на знак «?» и получаем табл. 12. Согласно табл. 12, минимальным элементом строки 5 является 3, поэтому константа приведения подмножества .

Таблица 12

j i	1	2	5
1	?	0	0
3	0	0?	0
5	?	3	?

Следовательно, значение нижней границы подмножества , а подмножества . Так как , то дальнейшему ветвлению подлежит подмножество .

Находим степени нулей таблицы 11, соответствующей подмножеству , и получаем табл. 13.

Таблица 13

j i	2	5
1	00	0?
3	0?	00

Претендентами на включение в гамильтонов контур, как видно из табл. 10, будут дуги (1;2) и (3;5), как соответствующие нулевым элементам с наибольшей степенью.

На рис. 1 представлено результирующее дерево ветвлений. В полученный гамильтонов контур вошли дуги (3,5); (2,1); (5,1); (4,3); (2,4); , т.е. сам контур имеет вид: 1 2 4 3 5 1, а его длина, согласно табл. 1, равна 6 + 5 + 6 + 4 + 4 = 25, что соответствует величине нижней границы подмножества . Так как границы оборванных ветвей (висячих вершин) больше длины полученного контура (за исключением вершины, соответствующей подмножеству , величина нижней границы которой совпадает с длиной гамильтонова контура), то этот контур имеет наименьшую длину и, таким образом, является оптимальным маршрутом коммивояжёра.

Рисунок 1.

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

Таблица 1 - Матрица расстояний

i	j
	1	2	3	4	5
1	-	4	5	7	6
2	5	-	5	4	7
3	5	4	-	6	6
4	7	5	4	-	7
5	6	8	5	7	-

Шаг 1. Минимальным элементом первой строки есть элемент, находящийся во 2-м столбце, поэтому из вершины с номером 1 путь коммивояжёра может пролегать только в вершину с номером 2.

Шаг 2. Минимальным элементом строки с номером 2 является элемент со значением 4, находящийся в 4-м столбце.

Шаг 3. Минимальным элементом строки с номером 4 является элемент со значением 4, находящийся в 3-м столбце, поэтому из вершины с номером 4 путь коммивояжёра будет пролегать в вершину с номером 3.

Шаг 4 (последний). Поскольку маршрут коммивояжёра пролегает через все вершины, кроме вершины с номером 5, то, очевидно, из вершины с номером 3 этот маршрут пройдёт в вершину с номером 5, из которой затем - в начальную вершину.

Таким образом, маршрут коммивояжёра имеет вид: 1 2 4 3 5 1, а его длина равна 24.

Размещено на Allbest.ru

...