Содержание 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
Актуальность работы
В настоящее время поиск лучшего маршрута для путешествий - актуальная тема почти для каждого современного человека. Всё чаще люди пользуются различными информационными системами для туризма и путешествий. Интересных мест в больших городах огромное количество, а способов посетить их все - еще больше. Но может случиться так, что выбранный порядок посещений окажется крайне неэффективным: удастся посетить лишь пару мест, да и те окажутся скучными и не стоящими внимания. В такие моменты на помощь приходят популярные сервисы-путеводники, веб-сайты с их персональными гидами по городу, но все они несовершенны: не позволяют построить маршрут, учитывающий необходимые ограничения, или же не позволяют увидеть все возможные варианты. Для того чтобы решить описанные выше проблемы постоянно разрабатываются новые вспомогательные информационные системы на основе различных алгоритмов, в зависимости от нужды пользователей. При разработке подобных систем со стороны разработчиков встаёт вопрос об организации архитектуры таким образом, чтобы необходимые расчеты производились быстро и без непозволительных трудозатрат.
Представленный в данной работе алгоритм поиска оптимизирующего маршрута позволит реализовать разработчикам собственные проекты под нужды пользователей и в результате туристам и гостям города больше не нужно будет тратить время на составление удобного маршрута.
Результатом этой работы стал комплекс программ позволяющий определить и визуализировать наиболее “интересный” маршрут на графе.
Цель работы
Основной целью данной работы является создание и реализация эффективного алгоритма поиска, способного обрабатывать входные данные и выдавать результат за приемлемое время. Также должен быть проведен анализ схожих задач и подходов к их решению, для составления наиболее полной картины в данной сфере. В дополнение должна быть сформирована архитектура программного комплекса, позволяющая в короткие сроки и без чрезмерных усилий встроить реализованный алгоритм в свою структуру, не закрывая при этом доступа к модификации и расширению возможностей.
Теория графов
Формулировка нашей задачи содержит в себе термины из теории графов, а алгоритм был разработан с целью решения вычислительных проблем которые могут быть сведены к поиску нужных путей в графах. Следовательно, базовые знания из теории графов помогут понять как проблему, так и ее решение. Далее будут описаны несколько основных определений. Следующие определения взяты из [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 предоставляет приемлемое взаимодействие потоков, но написанная специально под нашу задачу функциональность должна сократить время простоя потоков в блокировке и улучшить обмен информацией между ветвями.
Самым перспективным улучшением работы алгоритма является предварительная обработка входных данных: изначально удаленные излишние переходы между вершинами, склеивание накладывающихся вершин друг на друга. В идеале входные данные должны быть без лишних переходов и тогда алгоритм всегда будет отрабатывать за лучшее время.
