Задача коммивояжера, ДП по подмножествам — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
(Про порядок обхода состояний)
Строка 31: Строка 31:
  
 
== Реализация ==
 
== Реализация ==
 +
Прежде чем писать код, скажем пару слов о порядке обхода состояний. Обозначим за <tex>|mask|</tex> количество единиц в маске (иначе говоря количество пройденных вершин не считая текущей). Тогда, поскольку при рассмотрении состояния <nowiki><</nowiki><tex>i, mask </tex><nowiki>></nowiki> мы смотрим на состояния
 +
 +
<nowiki><</nowiki><tex>j, mask - 2^j </tex><nowiki>></nowiki>, и <tex>|mask| = |mask - 2^j| + 1</tex>, то состояния с большим <tex>|mask|</tex> должны быть посещены позже, чтобы к моменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта.
 
   //Все переменные используются из описания алгоритма, inf = бесконечность
 
   //Все переменные используются из описания алгоритма, inf = бесконечность
 
   d[0][0] = 0;
 
   d[0][0] = 0;

Версия 02:16, 12 января 2013

Задача о коммивояжере (англ. Travelling - salesman problem, TSP) - это задача, в которой коммивояжер должен посетить [math] N [/math] городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?

Варианты решения

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

Так вот задача о коммивояжере относится к классу NP-полных задач. Поэтому, рассмотрим два варианта решения с экспоненциальным временем работы.

Перебор перестановок

Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все [math] N! [/math] всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших [math]N[/math]. Сложность алгоритма [math]O({N!}\times{N})[/math].

Динамическое программирование по подмножествам (по маскам)

Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.

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

Зафиксируем начальную вершину [math]s[/math] и будем искать гамильтонов цикл наименьшей стоимости - путь от [math]s[/math] до [math]s[/math], проходящий по всем вершинам (кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор [math]s[/math] не имеет значения. Поэтому будем считать [math]s = 0 [/math].

Подмножества вершин будем кодировать битовыми векторами, обозначим [math]mask_i[/math] значение [math]i[/math]-ого бита в векторе [math]mask[/math].

Обозначим [math]d[i][mask][/math] как наименьшую стоимость пути из вершины [math]i[/math] в вершину [math]0[/math], проходящую (не считая вершины [math]i[/math]) единожды по всем тем и только тем вершинам [math]j[/math], для которых [math]mask_j = 1[/math] (т.е. [math]d[i][mask][/math] уже найденный оптимальный путь от [math]i[/math]-ой вершины до [math]0[/math]-ой, проходящий через те вершины, где [math]mask_j=1[/math]. Если [math]mask_j=0[/math],то эти вершины еще не посещены).

  • Начальное состояние - когда находимся в 0-й вершине, ни одна вершина не посещена, а пройденный путь равен [math]0[/math] (т.е. [math]i = 0[/math] и [math]mask = 0[/math]).
  • Для остальных состояний ([math]i \ne 0[/math] или [math]mask \ne 0[/math]) перебираем все возможные переходы в [math]i[/math]-ую вершину из любой посещенной ранее и выбираем минимальный результат.
  • Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как [math]\infty[/math]).

Стоимостью минимального гамильтонова цикла в исходном графе будет значение [math] d[0][2^n-1][/math] - стоимость пути из [math]0[/math]-й вершины в [math]0[/math]-ю, при необходимости посетить все вершины. Данное решение требует [math]O({2^n}\times{n})[/math] памяти и [math]O({2^n}\times{n^2})[/math] времени.

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

Реализация

Прежде чем писать код, скажем пару слов о порядке обхода состояний. Обозначим за [math]|mask|[/math] количество единиц в маске (иначе говоря количество пройденных вершин не считая текущей). Тогда, поскольку при рассмотрении состояния <[math]i, mask [/math]> мы смотрим на состояния

<[math]j, mask - 2^j [/math]>, и [math]|mask| = |mask - 2^j| + 1[/math], то состояния с большим [math]|mask|[/math] должны быть посещены позже, чтобы к моменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта.

 //Все переменные используются из описания алгоритма, inf = бесконечность
 d[0][0] = 0;
 for i = 0 to n - 1
   for mask = 0 to mask = 2 ** n - 1
     for j = 0 to n - 1
       if j-ий бит mask == 1
         if w(i, j) существует
           d[i][mask] = min(d[i][mask], d[j][mask - 2 ** j] + w(i, j));
         else
           d[i][mask] = inf;
 print d[0][2 ** n - 1];

Ссылки

Литература

  • Романовский И. В. Дискретный анализ. СПб.: Невский Диалект; БХВ-Петербург, 2003. ISBN 5-7940-0114-3
  • Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4