Решение задачи о коммивояжере, прямой алгоритм. Курсовая работа (т). Информационное обеспечение, программирование.

🛑 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

Информационное обеспечение, программирование

Вы можете узнать стоимость помощи в написании студенческой работы.


Помощь в написании работы, которую точно примут!

Похожие работы на - Решение задачи о коммивояжере, прямой алгоритм

Скачать Скачать документ
Информация о работе Информация о работе


Скачать Скачать документ
Информация о работе Информация о работе


Скачать Скачать документ
Информация о работе Информация о работе


Скачать Скачать документ
Информация о работе Информация о работе

Нужна качественная работа без плагиата?

Не нашел материал для своей работы?


Поможем написать качественную работу Без плагиата!

Тема Решение задачи о коммивояжере, прямой алгоритм



В настоящее время существуют такие типы задач как задачи математического программирования. Существуют множество видов таких задач и способов их решения. В данном случае мы будем рассматривать вид задач математического программирования под названием задачи «Коммивояжёра». Цель задачи - отыскать наилучший маршрут для торговца, который должен объехать города и вернуться в исходный город, как правило за кратчайшее время или с наименьшими затратами. Такие задачи актуальны во многих областях таких как: автомобильные, судовые, железно - дорожные перевозки или в конвейерном производстве. В условиях задачи указывается критерий маршрута и соответствующие матрицы расстояний или стоимостей и т.д. В задачах указывается, что маршрут должен быть одинарным. В современной интерпретации задачи торговца формулируется так: в произвольном порядке обойти все вершины графа по кратчайшему пути и вернуться в исходную вершину, причем каждая вершина проходится 1 раз. Обычно задачу о торговце решают с помощью прямого алгоритма, т.к. для человека расчет такой задачи занимает много времени, и создаются программы для облегчения вычислений.

В данном курсовом проекте будет рассмотрен вопрос о создании программы для решения задачи «коммивояжёра» прямым алгоритмом.


.1.1 Экономическая постановка задачи

В условиях данной задачи сказано, что коммивояжер должен обойти 7 городов, чтобы найти оптимальный маршрут, расстояние которого будет самым коротким.

Расстояния между городами указаны в таблице 1.


12345671 51163158 2 5712672 3 1173637 4 61232413 5 366225 6 1573414 7 8271354

1.1.2 Математическая постановка задачи- число городов.j , i, j=1..N - матрица затрат, где Ci j - затраты на переход из i-го города в j-й.j - матрица переходов с компонентами:

Ui - Uj + N × Xi j £ N-1, i, j = 1..N, i ¹ j. (4)


Условие (2) означает, что коммивояжер из каждого города выезжает только 1 раз;

Условие (3) о том , что в каждый город въезжает только 1 раз;

Условие (4) обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель.


Задачи «коммивояжера» решаются несколькими способами:

Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:

маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;

в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.

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

Общая идея метода может быть описана на примере поиска минимума и максимума функции f ( x ) на множестве допустимых значений x . Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

Процедура ветвления состоит в разбиении области допустимых решений на подобласти меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево <#"justify">. Технологическая часть


2.1 Нелинейное программирование. Общий вид задач нелинейного программирования Модели нелинейного программирования. Методы решения задач нелинейного программирования


Нелинейное программирование - случай математического программирования <#"justify">Как правило, в практических задачах необходимо определить наибольшее и наименьшее значения функции (глобальный экстремум) в некоторой области. Говорят, что функция z = f (X) имеет в точке X 0 заданной области D глобальный максимум (наибольшее значение) или глобальный минимум (наименьшее значение), если неравенство f(X) ≤ f(X 0 ) или соответственно выполняется для любой точки X € D.

Если область D замкнута и ограничена, то дифференцируемая функция z = f (X) достигает в этой области своих наибольшего и наименьшего значений или в стационарной точке, или в граничной точке области (теорема Вейерштрасса).

Граница области D аналитически может быть задана системой уравнений (условий) относительно переменных x 1 , x 2 , ..., x n . Поэтому, исследуя экстремальные свойства функции на границе, необходимо решить задачу определения условного экстремума.

Условный экстремум. Пусть необходимо найти экстремум функции z = f (x 1 , x 2 , ..., x n ) при условии, что переменные x 1 , x 2 , ..., x n удовлетворяют, уравнениям


φ i (x 1 , x 2 , ..., x n ) = 0, i = 1, 2, ..., m,m < n(1)

Предполагается, что функции f и φ i , имеют непрерывные частные производные по всем переменным. Уравнения (1) называют уравнениями связи. Говорят, что в точке удовлетворяющей уравнениям связи(1), функция z = f (X) имеет условный максимум (минимум), если неравенство f(X 0 ) ≥ f(X) (f(X 0 ) ≤ f(X)) имеет место для всех точек X, координаты которых удовлетворяют уравнениям связи.

Легко заметить, что задача определения условного экстремума совпадает с задачей нелинейного программирования.

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


x i = ψ i (x m + 1 , ..., x n ), i = 1, 2, ..., m,(2)

Подставив полученные выражения для x f в функцию z, получи мz i = f(ψ i (x m + 1 , ..., x n ), ..., ψ m (x m + 1 , ..., x n ), x m + 1 , ..., x n ) или


Задача сведена к нахождению локального (глобального) экстремума для функции (3) от n - m переменных. Если в точке функция (3) имеет экстремум, то в точке функция z = f (x 1 , ..., x n ) имеет условный экстремум.



Для того, чтобы начать решать задачу необходимы условия задачи, в данном случае они представлены в виде таблицы. В таблице даны расстояния между городов.

В условии сказано, что коммивояжер начинает свой маршрут из города 1.

)По таблице находим город 1 и по строке начинаем искать тот город, который будет давать наименьшее приращение к длине пути или город, ближайший к городу 1.

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

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

) После того как все города использованы в маршруте, наша задача вернуться в город 1, откуда начинался маршрут, по строке последнего города смотрим расстояние до города 1 и прибавляем его к получившейся сумме расстояний между городов.

) В результате этих действий находят оптимальный маршрут, с самым коротким расстоянием между городов.


.2 Решение задачи теста для написания и отладки программы


В данной таблице приведены все условия для решения задачи, а именно длинны путей между городами. Q - расстояние, L - шаг


1234567151163158257126723117363746123241353662256157341478271354

= = 1->5= Q = 1->5->4= Q + Q + = 5 + 3 = 8= 1->5->4->3= Q + = 1->5->4->3->6= Q + = 1->5->4->3->6->7= Q + = 1->5->4->3->6->7->2= Q + = 1->5->4->3->6->7->2->1



В результате решения задачи самым оптимальным маршрутом между данными городами был выявлен маршрут, состоящий из семи шагов, а именно:

Длинна пройденного пути для этого маршрута оказалась самой наименьшей:

После того как пользователь запустил исполняемый файл, на рабочем столе появится пустое окно (рис В1), в котором пользователь должен ввести цифру количества столбцов и строк таблицы. Число строк соответствует числу городов. Так как созданная таблица будет квадратная , то пользователю достаточно ввести одну цифру. Данная форма создаст число переменных в соответствии с количеством ячеек таблицы.

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

После того, как все поля таблицы заполнены, следует нажать кнопку «Продолжить» будет произведен подсчет согласно формулам подсчета задач коммивояжера.

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

После выполнения всех этих действий пользователь может закрыть окно с программой, после чего она завершает работу.


.5 Обоснование выбора средств разработки


На сегодняшний день существует достаточно языков и сред программирования, при помощи которых можно создавать приложения. Наиболее известные: Delphi, Pascal, C# и т.д.

C#, являясь последним из широко распространенных языков программирования, должен впитать в себя весь имеющийся опыт и вобрать лучшие стороны существующих языков программирования, при этом являясь специально созданным для работы в .NET. Сама архитектура .NET продиктовала ему (как и многим другим языкам, на которых можно писать под .NET) объектно-ориентированную направленность. Конечно, это не является правилом, возможно создание компиляторов даже функциональных языков по .NET, на эту тему существуют специальные работы.
Конечно, излюбленным объектом для сравнения с C# у мировой коммьюнити является Java. Также разработанный для работы в виртуальной среде выполнения, имеющей объектно-ориентированную архитектуру и сборщик мусора, осноыванный на механизме ссылок. При сравнении с этим языком сразу выделаются такие особенности, как возможность объявлять несколько классов в одном файле, из чего следует синтаксическая поддержка иерархической системы пространств имен. Из реализации ООП-концепций сходство в механизме наследования и реализации (и в Java и в C# возможно единичное наследование, но множественная реализация интерфейсов,

в отличие от C++). Но в Java отсутствуют свойства и индексаторы (а также делегаты и события, но они отсутствуют еще много где). Также есть возможность перечисления контейнеров.

Из вещей, включенных в спецификацию языка, но не являющихся чисто "программистскими" необходимо отметить возможность использование комментариев в формате XML. Если комментарии отвечают специально описанной структуре, компилятор по ним может сгенерировать единый XML-файл документации.

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

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


Программа состоит из трех частей - форм.

Первая форма отвечает за задание параметров для создаваемой таблицы. Невозможно продолжить работу с программой, пока первая форма не будет заполнена.

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

Третья форма выводит ответ из результатов работы программы над условиями, заданными во второй форме.


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

У данной программы есть только один недостаток - если при решении задачи могут иметься несколько вариантов решений, то программа будет рассматривать только одно, так что пользователю будет выведена информация только об одном решении.


После того как пользователь запустил исполняемый файл, на рабочем столе появится пустое окно (рис В1), в котором пользователь должен ввести цифру количества столбцов и строк таблицы. Число строк соответствует числу городов. Так как созданная таблица будет квадратная , то пользователю достаточно ввести одну цифру.

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

После того, как все поля таблицы заполнены, следует нажать кнопку «Продолжить»

В третьем окне появится результат подсчетов программы, а именно оптимальный маршрут между данными городами и расстояние, потраченное на прохождение этого маршрута.(рис.В3)



коммивояжёр программирование нелинейный

В данном курсовом проекте был рассмотрен вопрос о создании программы для решения задачи «коммивояжёра» прямым алгоритмом.

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

маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;

в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.

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

Для того, чтобы начать решать задачу необходимы условия задачи, в данном случае они представлены в виде таблицы 1. В таблице даны расстояния между городов.

В результате решения задачи самым оптимальным маршрутом между данными городами был выявлен маршрут, состоящий из семи шагов, а именно:

Длинна пройденного пути для этого маршрута оказалась самой наименьшей:

Ответ совпал с ответом задачи, решенной программистом, значит программа написана верно.

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

После того как пользователь запустил исполняемый файл, на рабочем столе появится пустое окно (рис В1), в котором пользователь должен ввести цифру количества столбцов и строк таблицы. Число строк соответствует числу городов. Так как созданная таблица будет квадратная , то пользователю достаточно ввести одну цифру.

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

После того, как все поля таблицы заполнены, следует нажать кнопку «Продолжить»

В третьем окне появится результат подсчетов программы, а именно оптимальный маршрут между данными городами и расстояние, потраченное на прохождение этого маршрута.(рис.В3)

Подведем итог, после всех перечисленных шагов, получилась программа, позволяющая высчитать ответ, согласно решению задач «коммивояжера» все пункты были детально рассмотрены и выполнены, благодаря этому цель курсового проекта была достигнута.


1.Агальцов В.П., Валдайская И.В. Математические методы в программировании: Учебник. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006. - 224 с.: ил. - (Профессиональное образование).

2.Голицына О.Л., Попов И.И. Основы алгоритмизации и программирования: Учебное пособие. - М.: Форум: Инфра-М, 2014

.Орлов В.В. Технологии разработки программных продуктов. -СПб.: Питер, 2003. - 437 с.

. Партыка т.Л., Попов И.И. Математические методы: Учебник. - М.: ФОРУМ: ИНФРА-М, 2010. - 464с.: ил. - ( Профессиональное образование)



using System;System.Collections.Generic;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Windows.Forms;

private void Form1_Load(object sender, EventArgs e)

string starting = (start + 1).ToString();

if (i != start && matrix[start, i] < second[count] && !vis[i])

_q += string.Format(" + {0}", second[count]);

_l += string.Format(" -> {0}", start + 1);

new_matrix[start, j_min] = second[count];

_l += string.Format(" -> {0} -> {1}", start + 1, starting);

_q += string.Format(" + {0}", matrix[start, Convert.ToInt16(starting) - 1]);

q += matrix[start, Convert.ToInt16(starting) - 1];

new_matrix[start, Convert.ToInt16(starting) - 1] = matrix[start, Convert.ToInt16(starting) - 1];

label1.Text = string.Format("Q = {0} = {1} L = {2}", _q, q, _l);
lb.Text = string.Format("Город {0}", i + 1);

lab.Text = string.Format("Город {0}", i + 1);

lab.Location = new Point(lo_x, 30);

if (i != j && new_matrix[i, j] != 0)

lbl[i, j].Text = new_matrix[i, j].ToString();

lbl[i, j].Location = new Point(l_x + 15, l_y);

using System;System.Collections.Generic;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Windows.Forms;

private void button1_Click(object sender, EventArgs e)

try { x = Convert.ToInt16(textBox1.Text); }

MessageBox.Show("Значение введено не верно !");

MessageBox.Show("Значение введено не верно !");

private void textBox1_TextChanged(object sender, EventArgs e)

public int getResult() { return x; }

using System;System.Collections.Generic;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Windows.Forms;

lb.Text = string.Format("Город {0}", i + 1);

lb.Location = new Point(14, l_y + 4);

lab.Text = string.Format("Город {0}", i + 1);

lab.Location = new Point(lo_x, 37);

tb[i, j].TextAlign = HorizontalAlignment.Center;

tb[i, j].Font = new System.Drawing.Font("Microsoft Sans Serif", 11F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(204)));

tb[i, j].Location = new Point(l_x, l_y);

try { matrix[i, j] = Convert.ToInt16(tb[i, j].Text); }

MessageBox.Show("Значения введены не верно !");

public Class1 getResultate() { Class1 gr = new Class1(x, matrix, comboBox1.SelectedIndex); return gr; }

Приложение В. Видовые экраны работы программы




Похожие работы на - Решение задачи о коммивояжере, прямой алгоритм Курсовая работа (т). Информационное обеспечение, программирование.
Исследование Графика Функции Контрольная Работа
Реферат: General Lee Essay Research Paper General Lee
Реферат: Гемолитическая болезнь новорожденных
Курсовая работа по теме Договор в гражданском праве России
Собрание Сочинений Название
Отчет По Учебной Практике Бухгалтера
Курсовая работа по теме Капітальний ремонт кришки підшипника ведучого вала коробки передач
Экономическая Оценка Предприятия Курсовая
Контрольная работа по теме Ткани внутренней среды организма
Реферат по теме Способы изучения богатства и бедности россиян
Курсовая работа: Сучасні проблеми розвитку підприємницької діяльності в Україні
Реферат: По праву памяти
Дипломная работа по теме Работа с молодежью в России
Сочинение Описание Местности Природы
Контрольная Работа Неметаллы 1 Вариант
Контрольная работа: Современные технологии переработки нефти и газа
Контрольная работа по теме Европейский Союз: цели, история становления, экономика и политика
Курсовая работа по теме Учет архивных документов: современное состояние, перспективы развития
Контрольная Работа По Информатике 2
Реферат Техногенные Аварии Источники Негативных Факторов
Курсовая работа: Маркетинговая деятельность предприятия. на примере ОАО Шихан
Реферат: Великая Отечественная Война
Похожие работы на - Синтез и анализ последовательностных устройств