Изменения
Нет описания правки
==== Динамическое программирование по подмножествам ====
Задача о коммивояжере сводится к поиску кратчайшего гамильтонова пути цикла в графе.
Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам - дороги. Пусть в графе <tex> P = (V, E)</tex> <tex> N </tex>
вершин, пронумерованных от <tex>0</tex> до <tex>N-1</tex> и каждое ребро <tex>(i, j) \in E </tex> имеет некоторый вес <tex> d(i, j)</tex>. Необходимо найти гамильтонов цикл, сумма весов по ребрам которого минимальна.
Зафиксируем начальную вершину <tex>s</tex> и будем искать гамильтонов цикл наименьшей стоимости - путь от <tex>s</tex> до <tex>s</tex>, проходящий по всем вершинам(кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор <tex>s</tex> не имеет значения. Поэтому будем считать <tex>S = 0 </tex>.
Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>m_i</tex> значение <tex>i</tex>-ого бита в векторе <tex>m</tex>.
Стоимостью минимального гамильтонова цикла в исходном графе будет значение <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> времени.
