93
правки
Изменения
→Динамическое программирование по подмножествам
Стоимостью минимального гамильтонова цикла в исходном графе будет значение <tex> dp[0][2^n-1]</tex> - стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины.
Восстановить сам цикл несложно. Для этого воспользуемся соотношением <tex> dp[i][m] = d(i, j) + dp[j][m - 2^j] </tex>, которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> i = 0 </tex>,<tex> m = 2^n - 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> m = m - 2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> m = 0 </tex>. Данное решение требует <tex>O(2^nn)</tex> памяти и <tex>O(2^nn^2)</tex> времени.
Данное решение требует <tex>O({2^n}\times{n})</tex> памяти и <tex>O({2^n}\times{n^2})</tex> времени.
== Ссылки ==
