📄Работа №105092
Тема: Исследование различных методов решения задачи коммивояжёра
Характеристики работы
Тип работы
Бакалаврская работа
Предмет
Информатика и вычислительная техника
Объем:
71 листов
Год:
2019
Просмотров:
390
4230
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 5
ГЛАВА 1 ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА 7
1.1 Общая характеристика задачи коммивояжера 7
1.1.1 Постановка задачи коммивояжера 7
1.1.2 Математическая модель задачи коммивояжера 9
1.2 Методы решения задачи коммивояжера 11
1.2.1 Точные методы 13
1.2.2 Приближенные и эвристические методы 30
ГЛАВА 2 РЕАЛИЗАЦИЯ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА 39
2.1 Структура программы 39
2.2 Реализация метода ближайшего соседа 40
2.3 Реализация метода ветвей и границ 42
2.4 Интерфейс приложения 45
ГЛАВА 3 СРАВНИТЕЛЬНЫЙ АНАЛИЗ РЕАЛИЗАЦИЙ 47
3.1 Технические данные для сравнительного анализа 47
3.2 Метод ближайшего соседа 47
3.3 Метод ветвей и границ 50
3.4 Сравнение двух реализованных алгоритмов 53
ЗАКЛЮЧЕНИЕ 56
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 57
ПРИЛОЖЕНИЕ А 60
ГЛАВА 1 ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА 7
1.1 Общая характеристика задачи коммивояжера 7
1.1.1 Постановка задачи коммивояжера 7
1.1.2 Математическая модель задачи коммивояжера 9
1.2 Методы решения задачи коммивояжера 11
1.2.1 Точные методы 13
1.2.2 Приближенные и эвристические методы 30
ГЛАВА 2 РЕАЛИЗАЦИЯ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА 39
2.1 Структура программы 39
2.2 Реализация метода ближайшего соседа 40
2.3 Реализация метода ветвей и границ 42
2.4 Интерфейс приложения 45
ГЛАВА 3 СРАВНИТЕЛЬНЫЙ АНАЛИЗ РЕАЛИЗАЦИЙ 47
3.1 Технические данные для сравнительного анализа 47
3.2 Метод ближайшего соседа 47
3.3 Метод ветвей и границ 50
3.4 Сравнение двух реализованных алгоритмов 53
ЗАКЛЮЧЕНИЕ 56
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 57
ПРИЛОЖЕНИЕ А 60
📖 Введение
Задача о коммивояжере - относится к классу NP-полных задач дискретной оптимизации. Время работы алгоритма, решающего задачу коммивояжера, существенно зависит от размера входных данных, то есть от количества городов.
Для нее до сих пор не найдено быстрых полиномиальных алгоритмов. Для графов задача формулируется следующим образом: требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе. То есть каждую вершину графа нужно посетить ровно один раз.
Актуальность: Задача коммивояжера на сегодняшнее время применяется в различных сферах, таких как: маршрутизация транспортных потоков и выбор оптимальной траектории движения рабочего инструмента, а также в сферах, которые на первый взгляд не связаны с маршрутизацией: секвенирования нуклеотидных последовательностей биополимеров, эвристического определения схожести строк, построения практических алгоритмов исследования специально определённых бесконечных грамматических структур и построения эволюционных деревьев.
Объект исследования - задача коммивояжера.
Предмет исследования - метод ветвей и границ и метод ближайшего соседа для решения задачи коммивояжера.
Цель бакалаврской работы - анализ существующих методов решения задачи коммивояжера и реализация рассмотренных алгоритмов, выявление их достоинств и недостатков.
Для достижения цели работы необходимо решить следующие задачи:
1. Рассмотреть существующие методы решения задачи коммивояжера;
2. Реализовать метод ветвей и границ для решения задачи
коммивояжера на языке программирования Python;
3. Реализовать метод ближайшего соседа для решения задачи коммивояжера на языке программирования Python;
4. Выявить достоинства каждого реализованного метода.
Обзор по главам:
1) В первой главе приводиться общая характеристика задачи коммивояжера, описание и постановки этой задачи, математическая модель и описание существующих методов решения задачи коммивояжера;
2) Во второй главе - разработка двух выбранных методов - ветвей и границ и ближайшего соседа, описание структуры программной реализации.
3) В третьей главе-проведение вычислительных экспериментов и сравнительный анализ полученных результатов.
Для нее до сих пор не найдено быстрых полиномиальных алгоритмов. Для графов задача формулируется следующим образом: требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе. То есть каждую вершину графа нужно посетить ровно один раз.
Актуальность: Задача коммивояжера на сегодняшнее время применяется в различных сферах, таких как: маршрутизация транспортных потоков и выбор оптимальной траектории движения рабочего инструмента, а также в сферах, которые на первый взгляд не связаны с маршрутизацией: секвенирования нуклеотидных последовательностей биополимеров, эвристического определения схожести строк, построения практических алгоритмов исследования специально определённых бесконечных грамматических структур и построения эволюционных деревьев.
Объект исследования - задача коммивояжера.
Предмет исследования - метод ветвей и границ и метод ближайшего соседа для решения задачи коммивояжера.
Цель бакалаврской работы - анализ существующих методов решения задачи коммивояжера и реализация рассмотренных алгоритмов, выявление их достоинств и недостатков.
Для достижения цели работы необходимо решить следующие задачи:
1. Рассмотреть существующие методы решения задачи коммивояжера;
2. Реализовать метод ветвей и границ для решения задачи
коммивояжера на языке программирования Python;
3. Реализовать метод ближайшего соседа для решения задачи коммивояжера на языке программирования Python;
4. Выявить достоинства каждого реализованного метода.
Обзор по главам:
1) В первой главе приводиться общая характеристика задачи коммивояжера, описание и постановки этой задачи, математическая модель и описание существующих методов решения задачи коммивояжера;
2) Во второй главе - разработка двух выбранных методов - ветвей и границ и ближайшего соседа, описание структуры программной реализации.
3) В третьей главе-проведение вычислительных экспериментов и сравнительный анализ полученных результатов.
✅ Заключение
В ходе выполнения бакалаврской работы были рассмотрены существующие методы решения задачи коммивояжера, достоинства и недоставки всех методов, а также была произведена реализация метода ближайшего соседа и метода ветвей и границ на языке программирования Python.
В ходе работы были выполнены следующие задачи:
1. Рассмотрены существующие методы решения задачи коммивояжера;
2. Реализован метод ближайшего соседа для решения задачи
коммивояжера на языке программирования Python;
3. Реализован метод ветвей и границ для решения задачи
коммивояжера на языке программирования Python;
4. Выявлены достоинства каждого реализованного метода.
5. Проведены сравнения реализованных методов.
Были пошагово реализованы методы ближайшего соседа и ветвей и границ на языке программирования Python, с использованием пользовательского графического интерфейса.
Проведены вычислительные эксперименты, состоящие в сравнении времени работы данных методов, которые показали, что метод ближайшего соседа работает намного быстрее, чем метод ветвей и границ.
В ходе работы были выполнены следующие задачи:
1. Рассмотрены существующие методы решения задачи коммивояжера;
2. Реализован метод ближайшего соседа для решения задачи
коммивояжера на языке программирования Python;
3. Реализован метод ветвей и границ для решения задачи
коммивояжера на языке программирования Python;
4. Выявлены достоинства каждого реализованного метода.
5. Проведены сравнения реализованных методов.
Были пошагово реализованы методы ближайшего соседа и ветвей и границ на языке программирования Python, с использованием пользовательского графического интерфейса.
Проведены вычислительные эксперименты, состоящие в сравнении времени работы данных методов, которые показали, что метод ближайшего соседа работает намного быстрее, чем метод ветвей и границ.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.