Iv. Динамические структуры данных

Задача коммивояжера. Коммивояжер (бродячий торговец) должен выйти из первого города и, 
посетив по разу в неизвестном порядке города 2,3,...n, вернуться обратно в первый город. В 
каком порядке надо обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчай-
шим? 
 Метод грубой силы 
Этот метод предусматривает просто перебор всех вариантов. Сначала нам надо получить 
некоторую допустимую последовательность обхода вершин. Поскольку первый город (1) за-
фиксирован, всего таких перестановок будет (n-1)!. Получив очередную перестановку надо 
найти длину пути и, если она окажется меньше уже найденного кратчайшего пути, ее надо за-
помнить и перейти к следующей перестановке. 
Поскольку нами уже написана процедура получения всех перестановок из целых чисел от 
1 до N (см. пункт Комбинации и перестановки раздела Рекурсия в главе III), имеет смысл ее 
использовать. Удобно ввести глобальные переменные 
int Pmin[N],
// лучшая перестановка 
P[N],
// текущая перестановка
 
Lmin,
// минимальная длина
 
L, 
 
// текущая длина
 
D[N][N]; 
// матрица расстояний
 
Основная программа будет инициализировать глобальные переменные, вызывать рекурсивную 
процедуру построения оптимального пути и распечатывать результат: 
void main() 
{ 
Lmin = 32767;
 // большое число 
L = 0; 
P[0] = 1;
// начальная вершина 1 
Commi(1);
// построить тур 
for ( int i = 0; i < N; i ++ )
// вывести результат 
 printf("%d ", Pmin[i]); 
} 
Ниже приведена рекурсивная процедура, решающая задачу коммивояжера, приводится ниже. 
Текущая длина пути вычисляется последовательно с добавление каждого нового звена.