📄Работа №67598
Тема: Исследование эвристических методов решения задачи коммивояжера
Характеристики работы
Тип работы
Бакалаврская работа
Предмет
Математика
Объем:
44 листов
Год:
2016
Просмотров:
456
4290
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 3
Глава 1. Обзор транспортных задач. Актуальность задачи
коммивояжера 5
1.1. Транспортные задачи 5
1.2. Постановка задачи коммивояжера 7
Глава 2. Алгоритмы решения задачи коммивояжера 8
2.1. Метод полного перебора 8
2.2. Метод ближайшего соседа 11
2.3. Усовершенствованный метод ближайшего соседа 15
2.4. Метод ветвей и границ 18
Глава 3. Моделирование загруженности транспортной сети .. 25
3.1. Дорожные заторы (пробки) 25
Глава 4. Сравнительный анализ эвристических методов решения задачи коммивояжера 29
4.1. Разработка скрипта для параллельных генерации и вычислений
алгоритмов 29
4.2. Способ генерации матриц времен для задачи коммивояжера в
условиях городского цикла 31
4.3. Сравнительный анализ эвристических методов решения задачи
коммивояжера 32
Выводы 37
Заключение 38
Список литературы 40
Приложение
Глава 1. Обзор транспортных задач. Актуальность задачи
коммивояжера 5
1.1. Транспортные задачи 5
1.2. Постановка задачи коммивояжера 7
Глава 2. Алгоритмы решения задачи коммивояжера 8
2.1. Метод полного перебора 8
2.2. Метод ближайшего соседа 11
2.3. Усовершенствованный метод ближайшего соседа 15
2.4. Метод ветвей и границ 18
Глава 3. Моделирование загруженности транспортной сети .. 25
3.1. Дорожные заторы (пробки) 25
Глава 4. Сравнительный анализ эвристических методов решения задачи коммивояжера 29
4.1. Разработка скрипта для параллельных генерации и вычислений
алгоритмов 29
4.2. Способ генерации матриц времен для задачи коммивояжера в
условиях городского цикла 31
4.3. Сравнительный анализ эвристических методов решения задачи
коммивояжера 32
Выводы 37
Заключение 38
Список литературы 40
Приложение
📖 Введение
В жизни современных предприятий самого разного рода существенное место занимают транспортные потоки: для каждой компании актуален вопрос о своевременной доставке товара потребителям в кратчайшие сроки. Для осуществления этого руководство компании, по сути, занимается решением так называемой задачи коммивояжера.
Представим себе ситуацию, в том или ином виде возникающую на любом предприятии, которое специализируется на доставке товаров и грузов. Допустим, курьеру компании необходимо развезти продукцию в определенное число мест и вернуться в офис. Задача формулируется следующим образом: определить в каком порядке курьер должен посещать клиентов, чтобы дорога заняла наименьшее время (все пункты посещаются один раз).
Задача коммивояжера в такой постановке является NP-трудной. Это означает, что не существует алгоритма, который находил бы точное решение задачи коммивояжера за полиномиальное время. Единственным же алгоритмом, который в принципе может гарантировать нахождение точного решения, является метод полного перебора. Однако работа программы, реализующей этот алгоритм, занимает адекватное время только при очень малой размерности входных данных (при числе пунктов < 20).
В связи с отсутствием эффективных точных методов решения задачи коммивояжера, становится необходимым использование методов эвристических. Эвристическими называют методы, которые будучи основанными на некой эвристике (правиле), не всегда следующей из строгих математических принципов, в подавляющем большинстве случаев дают решение, близкое к точному.
Таким образом, ставится следующая цель: исследовать различные эвристические методы решения задачи коммивояжера и оценить качество полученного решения для задач с различным числом посещаемых пунктов.
Для реализации поставленной в работе цели ставятся следующие задачи:
• изучить единственный точный метод решения задачи коммивояжера - метод полного перебора,
• исследовать некоторые эвристические алгоритмы,
• программно реализовать их,
• проанализировать время и результаты работы программных реализаций алгоритмов,
• улучшить алгоритмы, если это возможно,
• разработать способ учета изменяющейся дорожной обстановки в методах,
• разработать способ генерации входных данных для задачи коммивояжера с учетом специфики постановки задачи,
• организовать возможность параллельной работы методов на разных экземплярах задач,
• сравнить время и результаты работы программных реализаций усовершенствованных алгоритмов с исходными.
Представим себе ситуацию, в том или ином виде возникающую на любом предприятии, которое специализируется на доставке товаров и грузов. Допустим, курьеру компании необходимо развезти продукцию в определенное число мест и вернуться в офис. Задача формулируется следующим образом: определить в каком порядке курьер должен посещать клиентов, чтобы дорога заняла наименьшее время (все пункты посещаются один раз).
Задача коммивояжера в такой постановке является NP-трудной. Это означает, что не существует алгоритма, который находил бы точное решение задачи коммивояжера за полиномиальное время. Единственным же алгоритмом, который в принципе может гарантировать нахождение точного решения, является метод полного перебора. Однако работа программы, реализующей этот алгоритм, занимает адекватное время только при очень малой размерности входных данных (при числе пунктов < 20).
В связи с отсутствием эффективных точных методов решения задачи коммивояжера, становится необходимым использование методов эвристических. Эвристическими называют методы, которые будучи основанными на некой эвристике (правиле), не всегда следующей из строгих математических принципов, в подавляющем большинстве случаев дают решение, близкое к точному.
Таким образом, ставится следующая цель: исследовать различные эвристические методы решения задачи коммивояжера и оценить качество полученного решения для задач с различным числом посещаемых пунктов.
Для реализации поставленной в работе цели ставятся следующие задачи:
• изучить единственный точный метод решения задачи коммивояжера - метод полного перебора,
• исследовать некоторые эвристические алгоритмы,
• программно реализовать их,
• проанализировать время и результаты работы программных реализаций алгоритмов,
• улучшить алгоритмы, если это возможно,
• разработать способ учета изменяющейся дорожной обстановки в методах,
• разработать способ генерации входных данных для задачи коммивояжера с учетом специфики постановки задачи,
• организовать возможность параллельной работы методов на разных экземплярах задач,
• сравнить время и результаты работы программных реализаций усовершенствованных алгоритмов с исходными.
✅ Заключение
Поставленные в данной работе цели и задачи были успешно выполнены:
• изучена литература, посвященная задаче, отмечены основные направления современных исследований в данной области;
• изучен метод полного перебора; показано, что он не может успешно применяться на практике ввиду быстрого роста времени работы его программной реализации при увеличении количества посещаемых пунктов;
• подробно описаны метод ближайшего соседа и метод ветвей и границ, проиллюстрированы шаги работы алгоритмов, приведены их логические схемы, оба метода успешно реализованы на языке C++;
• на основе широкой выборки сгенерированных матриц построены сравнительные таблицы и графики, на основании которых были сделаны выводы о полезности применения алгоритмов на практике;
• произведено усовершенствование метода ближайшего соседа путем введения в рассмотрение фиктивных стартовых пунктов; на основании применения усовершенствованного метода к различным экземплярам задачи, сделан вывод о том, что эффективность метода повысилась;
• разработана модель учета изменения дорожной ситуации, проведена демонстрация работы модели на примере;
• разработан удобный способ генерации входных данных, обоснована его
адекватность специфике рассматриваемой постановки задачи;
разработан скрипт, позволяющий генерировать входные данные и осуществлять программное решение задачи одновременно для нескольких экземпляров задачи.
Результаты проделанной работы докладывались и публиковались на конференциях с международным участием, проводимых Санкт-Петербургским государственным университетом и Санкт-Петербургским политехническим университетом Петра Великого, а так же на международной научно-исследовательской конференции «INFO-эксперт»- 2016. Статья «Один из способов моделирования дорожной ситуации для решения задачи коммивояжера в условиях города» была отмечена дипломом победителя II-ой степени в номинации «Computer science - IT- эксперт» на международной научно-исследовательской конференции «ЮТО-эксперт»-2016.
• изучена литература, посвященная задаче, отмечены основные направления современных исследований в данной области;
• изучен метод полного перебора; показано, что он не может успешно применяться на практике ввиду быстрого роста времени работы его программной реализации при увеличении количества посещаемых пунктов;
• подробно описаны метод ближайшего соседа и метод ветвей и границ, проиллюстрированы шаги работы алгоритмов, приведены их логические схемы, оба метода успешно реализованы на языке C++;
• на основе широкой выборки сгенерированных матриц построены сравнительные таблицы и графики, на основании которых были сделаны выводы о полезности применения алгоритмов на практике;
• произведено усовершенствование метода ближайшего соседа путем введения в рассмотрение фиктивных стартовых пунктов; на основании применения усовершенствованного метода к различным экземплярам задачи, сделан вывод о том, что эффективность метода повысилась;
• разработана модель учета изменения дорожной ситуации, проведена демонстрация работы модели на примере;
• разработан удобный способ генерации входных данных, обоснована его
адекватность специфике рассматриваемой постановки задачи;
разработан скрипт, позволяющий генерировать входные данные и осуществлять программное решение задачи одновременно для нескольких экземпляров задачи.
Результаты проделанной работы докладывались и публиковались на конференциях с международным участием, проводимых Санкт-Петербургским государственным университетом и Санкт-Петербургским политехническим университетом Петра Великого, а так же на международной научно-исследовательской конференции «INFO-эксперт»- 2016. Статья «Один из способов моделирования дорожной ситуации для решения задачи коммивояжера в условиях города» была отмечена дипломом победителя II-ой степени в номинации «Computer science - IT- эксперт» на международной научно-исследовательской конференции «ЮТО-эксперт»-2016.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.