ЗАКЛЮЧЕНИЕ
Задача коммивояжера является частичным случаем гамильтоновой задачи о путешественнике. Суть задачи коммивояжера состоит в нахождении суммарной минимальной характеристики (расстояния, стоимости проезда и т.д.), при этом коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал.
Существуют несколько методов решения задачи коммивояжера: метод полного перебора, «жадные» методы (Крускала, Прима, и т.п.), генетические алгоритмы и еще множество их обобщений. Однако только метод ветвей и границ дает нам в итоге самое оптимальное решение.
В основе метода ветвей и границ лежит следующая идея если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева).
Задача о коммивояжере имеет множество обобщений и методы её решения в различных проявлениях используются на практике.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1 Моисеев Н.Н. Методы оптимизации: Моисеев Н.Н., Иванилова Ю.П., Столярова Е.М.-М., 1978, 352 с;
2 Черноусько Ф.Л. Вариационные задачи механики и управления: Численные методы/ Черноусько Ф.Л., Баничук Н.В.-М.,1973;
3 http://dic.academic.ru/;
4 http://www.lobanov-logist.ru/index.php?newsid=470;
5 http://swsys.ru/index.php?page=article&id=827;
6 http://e-maxx.ru/algo/mst_prim;
7 http://www.dissercat.com/content/nekotorye-zadachi-marshrutizatsii-i-raspredeleniya-zadanii-metod-dinamicheskogo-programmirov;
8 www.vecon.ru.