📄Работа №130386
Тема: Эвристический параллельный алгоритм поиска оптимизирующего маршрута на связном графе
Характеристики работы
Тип работы
Бакалаврская работа
Предмет
Программирование
Объем:
35 листов
Год:
2018
Просмотров:
85
4800
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Содержание 2
Введение 3
Актуальность работы 3
Цель работы 4
Теория графов 5
Постановка задачи 6
Сравнение с типовыми задачами 7
Задача коммивояжера 7
Single vehicle pickup and delivery problem with hard windows 7
Поиск кратчайших путей 8
Способы решения 9
Алгоритм имитации отжига (Simulated annealing) 9
Tabu search (TS) 10
Ant colony optimization (ACO) 12
Алгоритм решения 13
Использованные средства 14
Эвристика 14
Параллельность 16
Реализация 17
Архитектура программного комплекса 17
Предобработка 18
Первый этап - “Поиск” 18
Второй этап - “Возврат” 20
Временная сложность 21
Последовательный вариант алгоритма 21
Параллельный вариант алгоритма 23
Тесты 24
Примеры решений 27
Пример 1. 27
Пример 2. 28
Пример 3. 29
Пример 4. 30
Выводы 31
Заключение 32
Список использованных источников 33
Приложение 35
Введение 3
Актуальность работы 3
Цель работы 4
Теория графов 5
Постановка задачи 6
Сравнение с типовыми задачами 7
Задача коммивояжера 7
Single vehicle pickup and delivery problem with hard windows 7
Поиск кратчайших путей 8
Способы решения 9
Алгоритм имитации отжига (Simulated annealing) 9
Tabu search (TS) 10
Ant colony optimization (ACO) 12
Алгоритм решения 13
Использованные средства 14
Эвристика 14
Параллельность 16
Реализация 17
Архитектура программного комплекса 17
Предобработка 18
Первый этап - “Поиск” 18
Второй этап - “Возврат” 20
Временная сложность 21
Последовательный вариант алгоритма 21
Параллельный вариант алгоритма 23
Тесты 24
Примеры решений 27
Пример 1. 27
Пример 2. 28
Пример 3. 29
Пример 4. 30
Выводы 31
Заключение 32
Список использованных источников 33
Приложение 35
📖 Введение
Актуальность работы
В настоящее время поиск лучшего маршрута для путешествий - актуальная тема почти для каждого современного человека. Всё чаще люди пользуются различными информационными системами для туризма и путешествий. Интересных мест в больших городах огромное количество, а способов посетить их все - еще больше. Но может случиться так, что выбранный порядок посещений окажется крайне неэффективным: удастся посетить лишь пару мест, да и те окажутся скучными и не стоящими внимания. В такие моменты на помощь приходят популярные сервисы-путеводники, веб-сайты с их персональными гидами по городу, но все они несовершенны: не позволяют построить маршрут, учитывающий необходимые ограничения, или же не позволяют увидеть все возможные варианты. Для того чтобы решить описанные выше проблемы постоянно разрабатываются новые вспомогательные информационные системы на основе различных алгоритмов, в зависимости от нужды пользователей. При разработке подобных систем со стороны разработчиков встаёт вопрос об организации архитектуры таким образом, чтобы необходимые расчеты производились быстро и без непозволительных трудозатрат.
Представленный в данной работе алгоритм поиска оптимизирующего маршрута позволит реализовать разработчикам собственные проекты под нужды пользователей и в результате туристам и гостям города больше не нужно будет тратить время на составление удобного маршрута.
Результатом этой работы стал комплекс программ позволяющий определить и визуализировать наиболее “интересный” маршрут на графе.
Цель работы
Основной целью данной работы является создание и реализация эффективного алгоритма поиска, способного обрабатывать входные данные и выдавать результат за приемлемое время. Также должен быть проведен анализ схожих задач и подходов к их решению, для составления наиболее полной картины в данной сфере. В дополнение должна быть сформирована архитектура программного комплекса, позволяющая в короткие сроки и без чрезмерных усилий встроить реализованный алгоритм в свою структуру, не закрывая при этом доступа к модификации и расширению возможностей.
Теория графов
Формулировка нашей задачи содержит в себе термины из теории графов, а алгоритм был разработан с целью решения вычислительных проблем которые могут быть сведены к поиску нужных путей в графах. Следовательно, базовые знания из теории графов помогут понять как проблему, так и ее решение. Далее будут описаны несколько основных определений. Следующие определения взяты из [1].
• Конечный граф G состоит из двух конечных множеств V и E . Элемент v из V называется вершиной (узлом), а элемент е из E называется ребром. Если необходимо указать принадлежность вершины или ребра к графу пишется V(G) или E(G) соответственно.
• Маршрутом (путем) в графе называется чередующаяся последовательность вершин и ребер v0, e0>1, v1, ..., ek.1;k, vk, в которой любые два соседних элемента инцидентны. Если v0 = vk, то маршрут замкнут, иначе открыт. В условиях нашей задачи рассматривается поиск именно замкнутого маршрута, который будет обозначаться P.
• Путь называется простым, если не проходит дважды через одно ребро.
• Граф называется связным, если между каждой парой вершин существует как минимум один путь.
• Полный граф — граф, в котором для каждой пары вершин v1 v2, существует ребро, инцидентное v1 и инцидентное v2 (каждая вершина соединена ребром с любой другой вершиной).
В настоящее время поиск лучшего маршрута для путешествий - актуальная тема почти для каждого современного человека. Всё чаще люди пользуются различными информационными системами для туризма и путешествий. Интересных мест в больших городах огромное количество, а способов посетить их все - еще больше. Но может случиться так, что выбранный порядок посещений окажется крайне неэффективным: удастся посетить лишь пару мест, да и те окажутся скучными и не стоящими внимания. В такие моменты на помощь приходят популярные сервисы-путеводники, веб-сайты с их персональными гидами по городу, но все они несовершенны: не позволяют построить маршрут, учитывающий необходимые ограничения, или же не позволяют увидеть все возможные варианты. Для того чтобы решить описанные выше проблемы постоянно разрабатываются новые вспомогательные информационные системы на основе различных алгоритмов, в зависимости от нужды пользователей. При разработке подобных систем со стороны разработчиков встаёт вопрос об организации архитектуры таким образом, чтобы необходимые расчеты производились быстро и без непозволительных трудозатрат.
Представленный в данной работе алгоритм поиска оптимизирующего маршрута позволит реализовать разработчикам собственные проекты под нужды пользователей и в результате туристам и гостям города больше не нужно будет тратить время на составление удобного маршрута.
Результатом этой работы стал комплекс программ позволяющий определить и визуализировать наиболее “интересный” маршрут на графе.
Цель работы
Основной целью данной работы является создание и реализация эффективного алгоритма поиска, способного обрабатывать входные данные и выдавать результат за приемлемое время. Также должен быть проведен анализ схожих задач и подходов к их решению, для составления наиболее полной картины в данной сфере. В дополнение должна быть сформирована архитектура программного комплекса, позволяющая в короткие сроки и без чрезмерных усилий встроить реализованный алгоритм в свою структуру, не закрывая при этом доступа к модификации и расширению возможностей.
Теория графов
Формулировка нашей задачи содержит в себе термины из теории графов, а алгоритм был разработан с целью решения вычислительных проблем которые могут быть сведены к поиску нужных путей в графах. Следовательно, базовые знания из теории графов помогут понять как проблему, так и ее решение. Далее будут описаны несколько основных определений. Следующие определения взяты из [1].
• Конечный граф G состоит из двух конечных множеств V и E . Элемент v из V называется вершиной (узлом), а элемент е из E называется ребром. Если необходимо указать принадлежность вершины или ребра к графу пишется V(G) или E(G) соответственно.
• Маршрутом (путем) в графе называется чередующаяся последовательность вершин и ребер v0, e0>1, v1, ..., ek.1;k, vk, в которой любые два соседних элемента инцидентны. Если v0 = vk, то маршрут замкнут, иначе открыт. В условиях нашей задачи рассматривается поиск именно замкнутого маршрута, который будет обозначаться P.
• Путь называется простым, если не проходит дважды через одно ребро.
• Граф называется связным, если между каждой парой вершин существует как минимум один путь.
• Полный граф — граф, в котором для каждой пары вершин v1 v2, существует ребро, инцидентное v1 и инцидентное v2 (каждая вершина соединена ребром с любой другой вершиной).
✅ Заключение
Построение маршрута для прогулок всегда было актуальным в среде туризма, а с развитием информационных технологий алгоритмы, подобные описанным в данной работе, будут становиться лишь востребованней.
Разработанная архитектура далека от идеала, но остается открытой для модификаций. Среди возможных улучшений можно выделить следующие:
• Перенос вычислений в облачную архитектуру: разгрузка вычислительных мощностей мобильных устройств всегда будет хорошо воспринята со стороны пользователей;
• Улучшение работы алгоритма с эвристикой: на текущий момент алгоритм использует эвристику лишь для сокращения числа рассматриваемых вариантов, но в перспективе правильно выбранная эвристика позволит достичь значительного возрастания производительности;
• Улучшение синхронизации потоков: использование функциональности ThreadPool предоставляет приемлемое взаимодействие потоков, но написанная специально под нашу задачу функциональность должна сократить время простоя потоков в блокировке и улучшить обмен информацией между ветвями.
Самым перспективным улучшением работы алгоритма является предварительная обработка входных данных: изначально удаленные излишние переходы между вершинами, склеивание накладывающихся вершин друг на друга. В идеале входные данные должны быть без лишних переходов и тогда алгоритм всегда будет отрабатывать за лучшее время.
Разработанная архитектура далека от идеала, но остается открытой для модификаций. Среди возможных улучшений можно выделить следующие:
• Перенос вычислений в облачную архитектуру: разгрузка вычислительных мощностей мобильных устройств всегда будет хорошо воспринята со стороны пользователей;
• Улучшение работы алгоритма с эвристикой: на текущий момент алгоритм использует эвристику лишь для сокращения числа рассматриваемых вариантов, но в перспективе правильно выбранная эвристика позволит достичь значительного возрастания производительности;
• Улучшение синхронизации потоков: использование функциональности ThreadPool предоставляет приемлемое взаимодействие потоков, но написанная специально под нашу задачу функциональность должна сократить время простоя потоков в блокировке и улучшить обмен информацией между ветвями.
Самым перспективным улучшением работы алгоритма является предварительная обработка входных данных: изначально удаленные излишние переходы между вершинами, склеивание накладывающихся вершин друг на друга. В идеале входные данные должны быть без лишних переходов и тогда алгоритм всегда будет отрабатывать за лучшее время.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.