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

Задачи, решаемые методом динамического программирования. Основные этапы нахождения деревянного алгоритма решения задачи. Выполнение алгоритма Прима. Построение Эйлерового цикла. Решение задач средствами Excel. Алгоритм основной программы - Derevo.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 04.04.2015
Размер файла 586,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на 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


Подобные документы

  • Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения.

    курсовая работа [2,0 M], добавлен 12.02.2013

  • Описание алгоритма решения транспортной задачи по планированию перевозки зерна. Ход решения задачи вручную, в программе TORA методом наименьшего элемента, с помощью MS Excel. Разработка программы для решения задачи в общем виде средствами Delphi.

    курсовая работа [2,5 M], добавлен 22.11.2012

  • Выполнение арифметических операций, этапы решения задач с помощью ЭВМ - постановка задачи, составление алгоритма решения, программная реализация алгоритма в среде Qbasic. Решение систем линейных уравнений по формулам Крамера. Графический режим Qbasic.

    курсовая работа [101,7 K], добавлен 29.09.2009

  • Поиск верхних и нижних границ для оптимального значения на подобласти допустимых решений. Методы и проблемы решения задач нелинейного программирования. Написание и отладка программы. Создание программы для решения задачи "коммивояжёра" прямым алгоритмом.

    курсовая работа [176,9 K], добавлен 22.01.2016

  • Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

    курсовая работа [1,1 M], добавлен 21.03.2012

  • Оптимизация решения задачи с помощью алгоритма отжига. Анализ теории оптимизации как целевой функции. Метод градиентного спуска. Переменные и описание алгоритма отжига. Представление задачи коммивояжера через граф. Сведение задачи к переменным и решение.

    курсовая работа [784,0 K], добавлен 21.05.2015

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

    курсовая работа [2,5 M], добавлен 27.02.2011

  • Особенности метода неопределенных множителей Лагранжа, градиентного метода и метода перебора и динамического программирования. Конструирование алгоритма решения задачи. Структурная схема алгоритма сценария диалога и описание его программной реализации.

    курсовая работа [1010,4 K], добавлен 10.08.2014

  • Краткий обзор решения транспортных задач. Экономическая интерпретация поставленной задачи. Разработка и описание алгоритма решения задачи. Построение математической модели. Решение задачи вручную и с помощью ЭВМ. Анализ модели на чувствительность.

    курсовая работа [844,3 K], добавлен 16.06.2011

  • Основные принципы функционирования ПК. Определение конфигурации компьютера с требуемыми характеристиками. Характеристики основных компонентов современного ПК. Описание алгоритма решения задачи с использованием MS Excel. Блок-схема алгоритма решения задач.

    курсовая работа [3,5 M], добавлен 20.12.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.