Имеет место (для xÎ m): выражение
min {mintour(m, x)4-d(x, x0)}
xÎm
вычисляет длину минимального замкнутого пути через множество вершин m и {хо} и тем самым решает задачу коммивояжера. .Это выражение равносильно (так как х() е
v) выражению
mintour(v, x0). Мы вычисляем mintour по предписанию
fct mintour = (set node m, node
i: i Î m) nat:
if ÷mç == I then d(xo, i)
else min {mintour(m\{i}, k)+d(k, i): k Î m\{i}} fi
Сложность алгоритма получается из его структуры вызовов (пусть úmê = п+1), это дерево вызовов приведено на рис. 10.3.
Уровень Степень разветвления Число вершин
 |
2 n-1 n*(n-1)
n 1 n!
Рис.10.3.. Дерево вызовов с п уровнями для множества с п + 1 элементами
Это дерево имеет высоту n и на каждом слое вершин в уровне t имеет П 1 £ i £ n-i+l
вершин. На уровне n оно имеет n! вершин. Впрочем, на каждом уровне встречается лишь
t
