Курсовая работа: Методы решения задачи коммивояжера

ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ
Оптимальное решение – это решение, которое приводит к по крайней мере такому же хорошему известному или ожидаемому результату, как и все другие доступные варианты решения.
NP трудная задача – множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее значения некоторого многочлена от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения).
Ориентированный граф - граф, рёбрам которого присвоено направление.

1 ЗАДАЧА КОММИРОЯЖЕРА

1.1 Введение

Задача коммивояжёра является самой распространенной задачей комбинаторной оптимизации. Основная цель данной задачи: поиске самого выгодного маршрута проходящего через указанные города с последующим возвратов в исходный город. Для решения данной задачи используются критерии выгодности маршрута, такие как: стоимость, время, длина маршрута и тд.
Данная задача относится к классу NP-трудных задач, т е отсутствуют эффективные алгоритмы для ее решения. Основные трудности, вызванные решением – поиск самой выгодной комбинации, заключаются в необходимости оценки всех комбинаций маршрутов.
Задачи делятся на симметричные и асимметричные. Симметричными, являются задачи, в которых все пары ребер между одними и теми же вершинами имеют одинаковую длину, следовательно, маршрутов вдвое меньше ассиметричного случая. В нашем случае используется асимметричный способ решения при помощи моделирования ориентированного графа. При этом учитывается в каком направлении находятся ребра.

1.2 Методы решения задачи коммивояжера

Для решения задачи коммивояжера могут использоваться такие алгоритмы, как: муравьиный, генетический, жадный, а также метод градиентного спуска и метод отжига.
Рассмотрим данные методы подробнее:
- Муравьиный алгоритм. Основной целью данного метода является использование модели поведения муравьев, и представляет собой метаэвристическую оптимизацию.
Генетический алгоритм. Основан