93
правки
Изменения
→Динамическое программирование по подмножествам (по маскам)
Обозначим <tex>d[i][mask]</tex> как наименьшую стоимость пути из вершины <tex>i</tex> в вершину <tex>0</tex>, проходящую (не считая вершины <tex>i</tex>) единожды по всем тем и только тем вершинам <tex>j</tex>, для которых <tex>mask_j = 1</tex> (т.е. <tex>mask</tex> - подмножество вершин исходного графа, которые осталось посетить).
Конечное состояние - когда находимся в 0-й вершине, все вершины посещены (т.е. <tex>i = 0</tex>, <tex>m = 0</tex>). Для остальных состояний перебираем все возможные переходы из <tex>i</tex>-й вершины в одну из непосещенyых непосещенных ранее и выбираем способ, дающий минимальный результат. Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).
То есть, <tex>d[i][mask]</tex> считается по следующим соотношениямследующему правилу:
<tex>d[i][mask] = \begin{cases} 0</tex>, если <tex>&\text{if }i = 0</tex> и <tex>\text{ and }mask = 0\\ min_{j: mask_j=1, (i, j) \in E} \begin{Bmatrix} p(i, j) + d[j][mask - 2^j] \end{Bmatrix}, & \text{if } i\neq 0 \text{ or } mask \neq 0\\ \infty, & \text{if } i \neq 0 \text{ and } mask \neq 0 \text{ and set of possible transitions is empty}\end{cases}</tex>
где, <tex> \text {and ---}</tex> и, <tex>\text {or ---} </tex> или, <tex>\text {set of possible transitions is empty ---}</tex> множество переходов пусто.
Стоимостью минимального гамильтонова цикла в исходном графе будет значение <tex> d[0][2^n-1]</tex> - стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины.
