Метод ветвей и границ для задачи коммивояжера

Дана задача коммивояжера в классической формулировке: для некоторой группы городов с заданными расстояниями между ними требуется найти кратчайший маршрут посещения каждого города один раз с возвращением в исходный пункт. Кратчайший маршрут находится полным переборомбез учета повторяющихся путей (например, 1-2-3-1 и 2-3-1-2). При этом на плоскости полученный маршрут является границей многоугольника.

1.Постановка задачи…………………………………………………..... 3
2. Математические основы решения задачи коммивояжера
2.1. Формулировка и некоторые свойства решений задачи коммивояжера…………………………………………………………….……
2.2. Постановка задачи коммивояжера как задачи на графе...…………………………………………..……………………………….
4
6
3. Постановка и описание алгоритма решения задачи
3.1. Алгоритм решения задачи…………………..……………….….
3.2. Оценка трудоемкости…………………………………………….
3.3. Результаты выполнения программы……………………………. 7
8
9
Приложение………………………………………………………………. 13
Литература………………………………………………………………… 17