Создание приложения для нахождения кратчайшего пути между городами

Оглавление

Введение        2

ГЛАВА 1. ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ ЗАДАЧИ НА РАССЧЕТ КРАТЧАЙШЕГО ПУТИ        3

1.1        Описание задачи коммивояжера        3

1.2        Обзор аналогов.        6

1.3        Требования к программному обеспечению рассчета кратчайшего пути между городами.        10

1.4 Выводы        11

ГЛАВА 2. ПРОЕКТИРОВАНИЕ И РАЗРАБОТКА ПРОГРАММНОГО ПРОДУКТА.        12

2.1. Проектирование интерфейса        12

2.2. Разработка ПО.        16

2.3 Описание работы пользователя с приложением.        20

2.4 Тестирование ПО.        24

2.5 Выводы        24

Заключение        25

СПИСОК ИСТОЧНИКОВ И ЛИТЕРАТУРЫ        26

Приложение        27

Введение

Цель:

• Разработать приложение для нахождения кратчайшего пути между городами.

Задачи:

• Рассмотреть задачу с математической точки зрения.
• Рассмотреть пути решения задачи.
• Ознакомиться с существующим ПО по данной теме и провести их анализ.
• Спроектировать предварительный вид приложения.
• Описать среду разработки и язык программирования.
• Применив полученные в процессе обучения навыки – создать приложение.
• Провести тестирование приложения на наличие ошибок.
• Описать работу пользователя с приложением.

ГЛАВА 1. ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ ЗАДАЧИ НА РАССЧЕТ КРАТЧАЙШЕГО ПУТИ

1. Описание задачи коммивояжера

Задача на рассчет кратчайшего расстояния между городами или, как ее еще называют, задача коммивояжера – это одна из самых известных задач на комбинаторику и оптимизацию. Ее смысл заключается в том, что необходимо найти кратчайший(самый дешёвый, совокупный критерий и тому подобное) путь, который пройдет коммивояжер. При этом нужно посетить каждый город и вернуться в начальную точку. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Проблема выражается в переборе всех вариантов маршрута, чтобы найти оптимальный и самый короткий.  Подразумевается, что торговец хочет затратить как можно меньше времени, при этом посетив все торговые точки. Задача коммивояжёра относится к числу трансвычислительных(задача, для решения которой требуется обработка более чем 1093 бит информации): уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.  Существует множество решений этой задачи, от самых неоптимальных, таких как перебор, до сложных и продвинутых алгоритмов, например метод ветвей и границ, венгерский метод, алгоритм Литтла или исключение подциклов.

Математическая модель коммивояжера выглядит следующим образом. Пусть хij=1, если путешественник переезжает из i-ого города в j-ый и хij=0, если это не так. Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.
Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u1=0, un+1=n. Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные xij и переменные ui (ui целые неотрицательные числа).