Вирішити завдання за допомогою алгоритму перебору з поверненням.
Завдання по варіанту: Вирішити задачу комівояжера методом перебору з поверненням. Ціни квитків задані за допомогою симетричною n'n матриці.
Завдання комівояжера полягає в наступному: є nгородов і відомі ціни квитків. Комівояжер повинен відвідати всі nгородов по одному разу, повернувшись в той, з якого почав. Потрібно знайти такий маршрут руху, при якому сумарна ціна квитків буде мінімальною. Схема маршрутів задана графом (див. Рис. 1). Дане завдання зводиться до пошуку Гамільтона циклу в графі з мінімальною сумою вартостей шляхів між вузлами.
Для вирішення завдання необхідно перебрати всі Гамільтона цикли і знайти серед них цикл найменшої вартості.
Шлях будемо представляти у вигляді послідовності вершин (x1, x2, ..., xk). Такий шлях буде простим якщо і тільки якщо xi ¹ xj для всіх i¹j, i, jÎ.
Для того, щоб послідовності вершин (x1, x2, ... xk) задовольняли умові xi ¹xj. будемо розфарбовувати вершини цих послідовностей і враховувати розмальовку при виборі черг вершини. Гамильтонов цикл, з початком x1 = n0. представимо як послідовність (x1, x2, ..., xn, xn + 1), де xn + 1 = x1 = n0.
Нехай Ak - безліч вершин, суміжних з xk. cn - розфарбування вершини n. Згідно загальній схемі алгоритму перебору з поверненням, отримуємо наступний алгоритм для перебору гамільтонових циклів:
void Gamilton (int k)