Решение замкнутой задачи Коммивояжера

  • 30 апр. 2016 г.
  • 1710 Слова
Северо - Кавказский Горно-металлургический институт.
Кафедра: Автоматизированные Системы Обработки и
Управление Информацией.


Курсовая работа
По дисциплине
<<Теория Принятия Решений>>

На тему: Решение замкнутой задачи Коммивояжера
Методом полного перебора.





Выполнил: Бугулов А.М.
Студент 3 курса гр. АСУ 08 1
Руководитель: Гроппен В.О.

Задание

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













Оглавление.
1. Задача Коммивояжера.
2.Методы решения задачи коммивояжера.
3.Метод полного перебора.
4.Пример решения метода.
5.Алгоритм, блок-схема.
6.Описание переменных.7.Листинг программы.
8. Скриншоты.
9. Производительность программы.
10.Список использованной литературы.









1.
Задача коммивояжера
Общее описание Задача коммивояжера (в дальнейшем сокращённо - ЗК) является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великуютеорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных задач) ЗК служит своеобразным полигоном, на котором испытываются всё новые методы.
 
Содержательная  постановка.
 
Коммивояжеру требуется обойти все города (вершины графа), побывав в каждом  по одному разу таким образом, чтобы суммарные затраты были минимальны. Если при этомсправедливо требование возврата в исходную точку, то говорят о замкнутой задаче коммивояжера, в противном случае – о разомкнутой. Вес r(i,j)  каждой дуги (i, j) графа G(X, U) соответствует затратам, связанным с переездом из i-го города в  j-й. 
 

Формальная  постановка задачи.
Ниже используются следующие обозначения:
A(G) – множество контуров на графе G(X, U);

y(i,j) -  булевапеременная, равная единице, если коммивояжер выбрал путь
             из i – го города в  j-й, и равная нулю в противном случае. 
















2.
Методы решения Задачи Коммивояжера.

1.Метод ветвей и границ(«поиск с возвратом»)
2.Фронтальный спуск
3.Случайный перебор
Перечисленные мной выше три методагарантируют глобально-оптимальное решение Задачи Коммивояжера.

Задача коммивояжёра, известная также как Задача о сверлильном станке или алгоритм коммивояжёра, широко применяется при разработке программного обеспечения (и не только для этого). Постановка задачи коммивояжёра и решение задачи коммивояжёра являются темой для данной курсовой работы. В курсовой работе кратко рассмотрены некоторые методырешения задачи коммивояжера и разработана программа, реализующая один из методов решения данной задачи (этот метод известен под названием полный перебор)








3.
Полный перебор

Полный перебор (или метод «грубой силы» от англ. brute force) — метод решения задачи путем перебора всех возможныхвариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.
Любая задача из класса NP может быть решена полным перебором. При этом, даже если вычисление целевой функции от каждого конкретного возможного решения задачи может быть осуществлена заполиномиальное время, в зависимости от количества всех возможных решений полный перебор может потребовать экспоненциального времени работы.
В криптографии на вычислительной сложности полного перебора основывается оценка криптостойкости шифров. В частности, шифр считается криптостойким, если не существует метода «взлома» существенно более быстрого чем полный перебор...
tracking img