Пример решения задачи коммивояжера

Имеем «чисто» математическую задачу, которую решим, используя метод Ветвей и Границ.

В симметричном графе, изображенном на рис.3, определить кратчайший путь из вершины 1 в вершину 2, проходящим через все вершины графа только по одному разу.

Шаг 0. Значение . Пометим вершину 1 признаком

Шаг 1. Пометим вершину 3 признаками

Рис.3. Шаг З. Имеем .

Шаг 1. Пометим следующие вершины: вершину 4 –признаками вершину 5 –признаками

Шаг 3. Имеем .

Шаг 1. Пометим вершину 5 признаками

Шаг 3. Имеем .

Шаг 1. Пометим вершину 3 признаками

Шаг 3. Имеем .

Шаг 1. Пометим вершину 4 признаками

Шаг 1. Пометим вершину 2 –признаками так как , то искомый путь построен.

Шаг 2. Искомый путь составляет последовательность вершин 1, 5, 3, 4, 2.

Общее затрачиваемое время в пути составит 13.