📄Работа №189461
Тема: РЕАЛИЗАЦИЯ ПРИБЛИЖЕННОГО ПАРАЛЛЕЛЬНОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ КОММВОЯЖЕРА
Характеристики работы
Тип работы
Дипломные работы, ВКР
Предмет
Информатика и вычислительная техника
Объем:
27 листов
Год:
2019
Просмотров:
74
4800
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Реферат
Введение 4
1. Постановка задачи 5
2. Алгоритмы решения задачи коммивояжера 5
3. Смешанный приближенный алгоритм 7
3.1 Реализация приближенного алгоритма 9
4. Модифицированный алгоритм 11
4.1 Реализация модифицированного алгоритма 12
5. Оптимизация при помощи библиотеки параллельного
программирования OpenMP 13
6. Вычислительный эксперимент 15
Заключение 24
Литература 25
Приложение А 26
Введение 4
1. Постановка задачи 5
2. Алгоритмы решения задачи коммивояжера 5
3. Смешанный приближенный алгоритм 7
3.1 Реализация приближенного алгоритма 9
4. Модифицированный алгоритм 11
4.1 Реализация модифицированного алгоритма 12
5. Оптимизация при помощи библиотеки параллельного
программирования OpenMP 13
6. Вычислительный эксперимент 15
Заключение 24
Литература 25
Приложение А 26
📖 Аннотация
Работа посвящена реализации приближенного параллельного алгоритма для решения задачи коммивояжера. Актуальность исследования обусловлена потребностью транспортных, логистических и курьерских служб в эффективных методах оптимизации маршрутов, где точные алгоритмы неприменимы из-за вычислительной сложности NP-полной задачи. В ходе исследования был реализован и модифицирован приближенный алгоритм, оптимизированный с использованием библиотеки параллельного программирования OpenMP для повышения производительности. Проведенный вычислительный эксперимент показал, что точность алгоритма возрастает с увеличением количества генерируемых дополнительных маршрутов, однако это приводит к компромиссу между скоростью работы и качеством решения. Результаты демонстрируют, что текущая реализация уступает по временной эффективности ряду существующих аналогов, но обладает потенциалом для дальнейшего распараллеливания и замены базового алгоритма ближайшего соседа на более эффективные методы. Практическая значимость работы заключается в возможности применения разработанного алгоритма в программных комплексах для планирования маршрутов в логистических компаниях и сервисах такси. Анализ литературы позволил систематизировать основные подходы к решению задачи, что послужило основой для выбора и модификации алгоритма.
📖 Введение
Задача коммивояжера — одна из самых известных задач оптимизации. Несмотря на простоту формулировки, задача является NP-сложной, и поэтому существует большое количество подходов к ее решению и созданных на их основе различных алгоритмов. Тем не менее, со временем задача меняет свой контекст, и теперь разработка новых алгоритмов необходима не столько для решения конкретных вариантов задачи и поиска пути, сколько в контексте прикладном. В настоящее время задача является актуальной в сфере транспорта, поскольку транспортные, логистические и курьерские службы, а также службы такси заинтересованы в оптимизации своих маршрутов [1].
В последнее время более перспективными для модификаций считаются приближенные и эвристические алгоритмы, поскольку они достаточно просты для программной реализации и дают за приемлемое время результат в пределах необходимой точности. Кроме того, эти алгоритмы отличаются большей, по сравнению с точными методами, гибкостью за счет параметров. Эти алгоритмы хорошо поддаются оптимизации в том числе распараллеливанием.
Целью данной работы является реализация приближенного параллельного алгоритма решения задачи коммивояжера.
Задачи представлены ниже:
1. Изучение существующих алгоритмов решения задачи коммивояжера.
2. Реализация приближенного алгоритма, его модификация и оптимизация.
3. Проведение вычислительного эксперимента.
В последнее время более перспективными для модификаций считаются приближенные и эвристические алгоритмы, поскольку они достаточно просты для программной реализации и дают за приемлемое время результат в пределах необходимой точности. Кроме того, эти алгоритмы отличаются большей, по сравнению с точными методами, гибкостью за счет параметров. Эти алгоритмы хорошо поддаются оптимизации в том числе распараллеливанием.
Целью данной работы является реализация приближенного параллельного алгоритма решения задачи коммивояжера.
Задачи представлены ниже:
1. Изучение существующих алгоритмов решения задачи коммивояжера.
2. Реализация приближенного алгоритма, его модификация и оптимизация.
3. Проведение вычислительного эксперимента.
✅ Заключение
Полученные результаты позволяют сделать некоторые выводы:
1. Наиболее точные варианты алгоритма создают небольшую долю от общего количества дополнительных маршрутов, однако чем больше отношение количества дополнительных маршрутов к количеству вершин, тем более точен результат.
2. Наиболее быстрые варианты алгоритма создают менее разнообразные маршруты и за счет этого теряют в точности.
3. На данный момент алгоритм сильно уступает во временной эффективности многим существующим алгоритмам.
4. Алгоритм обладает перспективами к дальнейшему распараллеливанию, а также к дальнейшей оптимизации путем полной замены алгоритма ближайшего соседа на алгоритм с большей эффективностью.
Были выполнены следующие задачи:
1. Изучение существующих алгоритмов решения задачи коммивояжера.
2. Реализация приближенного алгоритма, его модификация и оптимизация.
3. Проведение вычислительного эксперимента.
1. Наиболее точные варианты алгоритма создают небольшую долю от общего количества дополнительных маршрутов, однако чем больше отношение количества дополнительных маршрутов к количеству вершин, тем более точен результат.
2. Наиболее быстрые варианты алгоритма создают менее разнообразные маршруты и за счет этого теряют в точности.
3. На данный момент алгоритм сильно уступает во временной эффективности многим существующим алгоритмам.
4. Алгоритм обладает перспективами к дальнейшему распараллеливанию, а также к дальнейшей оптимизации путем полной замены алгоритма ближайшего соседа на алгоритм с большей эффективностью.
Были выполнены следующие задачи:
1. Изучение существующих алгоритмов решения задачи коммивояжера.
2. Реализация приближенного алгоритма, его модификация и оптимизация.
3. Проведение вычислительного эксперимента.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.