Изменения

В теории алгоритмов NP-полная (NPC, NP-complete) задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». Cтатус NP-полных задач пока что неизвестен. Для их решения до настоящего времени не разработано алгоритмов с полиномиальным временем работы, но и не доказано, что для какой-то из них алгоритмов не существует. Этот так называемый вопрос P<tex>\neneq</tex>NP с момента своей постановки в 1971 году стал одним из самых трудных в теории вычислительных систем.

Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам - дороги. Пусть в графе <tex> P G = (V, E)</tex> <tex> N </tex>вершин, пронумерованных от <tex>0</tex> до <tex>N-1</tex> и каждое ребро <tex>(i, j) \in E </tex> имеет некоторый вес <tex> dp(i, j)</tex>. Необходимо найти гамильтонов цикл, сумма весов по ребрам которого минимальна.

Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>m_imask_i</tex> значение <tex>i</tex>-ого бита в векторе <tex>mmask</tex>.

Обозначим <tex>dpd[i][mmask]</tex> как наименьшую стоимость пути из вершины <tex>i</tex> в вершину <tex>0</tex>, проходящую (не считая вершины <tex>i</tex>) единожды по всем тем и только тем вершинам <tex>j</tex>, для которых <tex>m_j mask_j = 1</tex> (т.е. <tex>mmask</tex> - подмножество вершин исходного графа, которые осталось посетить).

Конечное состояние - когда находимся в 0-й вершине, все вершины посещены (т.е. <tex>i = 0</tex>, <tex>m = 0</tex>). Для остальных состояний перебираем все возможные переходы из <tex>i</tex>-й вершины в одну из непосещенных непосещенyых ранее и выбираем способ, дающий минимальный результат. Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).

То есть, <tex>dpd[i][mmask]</tex> считается по следующим соотношениям:

<tex>dpd[i][mmask] = 0</tex>, если <tex>i = 0</tex> и <tex>m mask = 0</tex>

<tex>dpd[i][mmask] = min_{j: m_jmask_j=1, (i, j) \in E} \begin{Bmatrix} dp(i, j) + dpd[j][m mask - 2^j] \end{Bmatrix}</tex>, если <tex>i\neq 0</tex> или <tex> m mask \neq 0 </tex>

<tex>dpd[i][mmask] = \infty </tex>, если <tex>i \neq 0</tex>, <tex>mmask\neq0</tex> и множество возможных переходов пусто.

Стоимостью минимального гамильтонова цикла в исходном графе будет значение <tex> dpd[0][2^n-1]</tex> - стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины.

Восстановить сам цикл несложно. Для этого воспользуемся соотношением <tex> dpd[i][mmask] = d(i, j) + dpd[j][m - 2^j] </tex>, которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> i = 0 </tex>, <tex> m mask = 2^n - 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> m mask = m mask - 2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> m mask = 0 </tex>.