Деревянный алгоритм решения задачи коммивояжёра

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

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Магнитогорский государственный технический

университет им. Г.И. Носова»

Многопрофильный колледж

ТЕМА: «деревянный алгоритм решения задачи коммивояжёра»

Пояснительная записка к курсовому проекту

КП 230105.24.00.00. ПЗ

Руководитель проекта

Л.А Фетисова

Разработал студент

Группы ПР-08……….…….……..Н.Т. Сайфулин

Магнитогорск,2012



Содержание

Введение

1. Общая часть

1.1 Деревянный алгоритм

1.2 Пример

1.3 Решение задач средствами Excel

2. Алгоритм решения задачи

2.1 Алгоритм основной программы

2.2 Алгоритм подпрограммы

2.3 Листинг программы

Литература



Введение

В 1859г. Сэр Вильям Гамильтон, знаменитый математик, давший миру теорию комплексного числа и кватерниона, предложил детскую головоломку, в которой предлагалось совершить «круговое путешествие» по 20 городам, расположенных в различных частях земного шара.

Гамильтонова задача о путешественнике нередко преобразуется в задачу о коммивояжёре. Коммивояжёр - не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими - либо другими ресурсами. Гамильтонова задача может стать задачей о коммивояжёре, если каждое из ребёр снабдить числовой характеристикой. Это может быть километраж, время на дорогу, стоимость билета, расход горючего и т.д. Таким образом, условные характеристики дадут числовой ряд, элементы которого могут быть распределены между рёбрами как угодно.

Задача о коммивояжёре, который должен объехать все порученные ему города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд. Это одна из типичных задач, решаемых методом динамического программирования. О сложности её говорит такой факт: если городов - 4, то число возможных маршрутов равно 6, а уже при 11 городах существует более 3,5 млн. допустимых маршрутов. В общем случае, когда число городов «n» количество маршрутов равно (n-1)!. Задача заключается в поиске сокращённых способов расчёта, позволяющих отказываться от сплошного перебора возможных маршрутов.



1. Общая часть

1.1 Деревянный алгоритм

динамический программирование алгоритм задача

Этапы нахождение деревянного алгоритма:

1) Построение остовного дерева

2) Построение эйлерового цикла

3) Нахождение тура

1) Для построения остовного дерева используется алгоритм Прима

Алгоритм Прима обладает тем свойством, что ребра в множестве всегда образуют единое дерево. Дерево начинается с произвольной корневой вершины R и растет до тех пор, пока не охватит все вершины. На каждом шаге к дереву добавляется легкое ребро, соединяющее дерево и отдельную вершину из оставшейся части графа. Данное правило добавляет только безопасные ребра; следовательно, по завершении алгоритма ребра образуют минимальное остовное дерево. Данная стратегия является жадной, поскольку на каждом шаге к дереву добавляется ребро, которое вносит минимально возможный вклад в общий вес.

Пример выполнение алгоритма Прима:

1. Начальная фаза. Минимальный покрывающий лес состоит из корня и пустого множества ребер.

Рисунок 1.

2. Ребро с весом 6 является минимальным ребро, соединяющим корень с остальными вершинами. Добавляем его к минимальному остову.

Рисунок 2.

3. Следующее безопасное ребро с весом 11. Добавляем его.

Рисунок 3.

4-8. Добавляем остальные безопасные ребра.



Рисунок 4.

Рисунок 5.

Рисунок 6.



Рисунок 7.

Рисунок 8.

Ребра с весом 17, 19 и 25 - не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 - безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

2. Построение Эйлерового цикла

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

Ясно, что эйлеров цикл содержит не только все ребра по одному разу, но и все вершины графа (возможно по несколько раз). Очевидно так же, что эйлеровым может быть только связанный граф

3. Нахождение тура

Для нахождения тура, необходимо сложить суммы всех рёбер с 1-го по n-ый. Получившаяся сумма является длинной тура

1.2 Пример

Пример 1. Дана полная сеть, показанная на рисунке 9. Найти тур деревянным алгоритмом.

Рисунок 9.

Таблица 1.

N	1	2	3	4	5	6
1	0	6	4	8	7	14
2	6	0	7	11	7	10
3	4	7	0	4	3	10
4	8	11	4	0	5	11
5	7	7	3	5	0	7
6	14	10	10	11	7	0



Рисунок 10.

Решение:

Деревянный алгоритм вначале строит остовное дерево, показанное на рисунке 10 штриховой линией, затем эйлеров цикл 1-2-1-3-4-3-5-6-5-3-1, затем тур 1-2-3-4-5-6-1 длиной 43, который показан сплошной линией на рисунке 10

1.3 Решение задач средствами Excel

Решение задачи при помощи надстройки MS Excel «Поиск решения»

Программа Поиск решений - дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения определенных систем уравнений, линейных и нелинейных задач оптимизации

С помощью этой надстройки можно определить, при каких значениях указанных влияющих ячеек формула в целевой ячейке принимает нужное значение (минимальное, максимальное или равное какой-либо величине). Для процедуры поиска решения можно задать ограничения, причем не обязательно, чтобы при этом использовались те же влияющие ячейки, данные которых, определяют значение целевой ячейки. Для расчета заданного значения применяются различные математические методы поиска. Вы можете установить режим, в котором полученные значения переменных автоматически заносятся в таблицу. Кроме того, результаты работы программы могут быть оформлены в виде отчета.

Расстояния между городами заданы следующей матрицей:

Таблица 2. Расстояния между городами

N	1	2	3	4	5
1	0	6	3	8	6
2	6	0	2	6	5
3	3	2	0	7	4
4	8	6	7	0	9
5	6	5	4	9	0

Рисунок 11. Исходные данные задачи

Вводим формулы:



Таблица 3. Формулы

Ячейка	Формула	Примечание
B9	= СУММ(B4:B8)	Распространяем на диапазон B9:F9
G4	= СУММ(B4:F4)	Распространяем на диапазон G4:G8
B19	=СУММПРОИЗВ(B4:F8;B13:F17)	Целевая функция
E19	=B4+C5+D6+E7+F8	Исключение пути

Добавляем ограничения в окно «Поиск решений»

Рисунок 12. Окно «Поиск решений»



Рисунок 13. Окно «Параметры поиска решений»

Рисунок 14. Результат решения задачи



Вывод

В ходе анализа полученных результатов, приходим к выводу, что наш путь:

1-3-2-5-4-1

Расстояние = 27



2. Алгоритм решения задачи

2.1 Алгоритм основной программы - Derevo



2.2 Алгоритм подпрограммы - Derevalgor



2.3 Листинг программы

Program Derevo;

uses crt;

var

a:array[1..100,1..100] of integer;

posetil,q:array[1..105] of integer;

n,z,i,j,z:longint;

Procedure Derevalgor;

var

ps,pe,max,min,k,I,j,x:longint

begin

ps:=1;

pe:=1;

max:=0;

c:=0;

k:=z;

posetil[k]:=1;

q[ps]:=k;

for i:=1 to n do

for j:=1 to n do

begin

if a[i,j]>max then begin

max:=a[i,j];

end;

end;

max:=max+1;

while ps<=n do begin

min:=max;

for i:=1 to n do

if (a[k,i]<>0) and (posetil[i]<>1) and (a[k,i]<min) then begin

min:=a[k,i];

x:=i;

end;

c:=c+a[k,x];

pe:=pe+1;

q[pe]:=x;

posetil[x]:=1;

ps:=ps+1;

k:=q[ps];

end;

c:=c+a[n,z];

n:=n+1;

q[n]:=q[1];

end;

begin

clrscr;

write('Vvedite kol-vo gorodov:');

readln(n);

write('Vvedite gorod s kotorogo sleduet nachat');

readln(z);

for i:=1 to n do

for j:=1 to n do

begin

if (i=j) then a[i,j]:=0;

if (i<j) then

begin

write('Vvedite rasstoyanie v ycheiku (a[',i,',',j,']=)');

readln(a[i,j]);

a[j,i]:=a[i,j];

end;

end;

for i:=1 to n do

begin

for j:=1 to n do

write(a[i,j],'':4);

writeln;

end;

readln;

Derevalgor;

writeln('put po derevynnomu algoritmu:');

for i:=1 to n do

write(q[i],'':4);

readln;

writeln('tur');

write(c);

writeln;

readln;

end.



Литература

1) В.П.Агальцов, И.В.Волдайская. - Математические методы в программировании.

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