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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
(Перенаправление на Гамильтоновы графы)
 
(не показано 47 промежуточных версий 9 участников)
Строка 1: Строка 1:
'''Задача о коммивояжере''' (англ. '''Travelling - salesman problem, TSP''') - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из <tex> N </tex> точек на плоскости.
+
#перенаправление [[Гамильтоновы графы]]
 
 
== Формулировка задачи ==
 
Коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?
 
 
 
== Варианты решения  ==
 
В теории алгоритмов NP-полная (NPC, NP-complete) задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». Cтатус NP-полных задач пока что неизвестен. Для их решения до настоящего времени не разработано алгоритмов с полиномиальным временем работы, но и не доказано, что для какой-то из них алгоритмов не существует. Этот так называемый вопрос P<tex>\neq</tex>NP с момента своей постановки в 1971 году стал одним из самых трудных в теории вычислительных систем.
 
 
 
Так вот задача о коммивояжере относится к классу NP-полных задач. Рассмотрим два варианта решения.
 
==== Перебор перестановок ====
 
 
 
Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма  <tex>O(N!)</tex>.
 
 
 
==== Динамическое программирование по подмножествам (по маскам) ====
 
 
 
Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.
 
 
 
Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам - дороги. Пусть в графе <tex> G = (V, E)</tex>  <tex> N </tex>
 
вершин, пронумерованных от <tex>0</tex> до <tex>N-1</tex> и каждое ребро <tex>(i, j) \in E </tex> имеет некоторый вес <tex> p(i, j)</tex>. Необходимо найти гамильтонов цикл, сумма весов по ребрам которого минимальна.
 
 
 
Зафиксируем начальную вершину <tex>s</tex> и будем искать гамильтонов цикл наименьшей стоимости - путь от <tex>s</tex> до <tex>s</tex>, проходящий по всем вершинам(кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор <tex>s</tex> не имеет значения. Поэтому будем считать <tex>S = 0 </tex>.
 
 
 
Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>mask_i</tex> значение <tex>i</tex>-ого бита в векторе <tex>mask</tex>.
 
 
 
Обозначим <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>mask = 0</tex>). Для остальных состояний перебираем все возможные переходы из <tex>i</tex>-й вершины в одну из непосещенных ранее и выбираем способ, дающий минимальный результат. Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).
 
 
 
То есть, <tex>d[i][mask]</tex> считается по следующему правилу:
 
 
 
<tex> d[i][mask] =
 
\begin{cases}
 
0, &\text{if }i = 0\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>-ю, при необходимости посетить все вершины.
 
 
 
Восстановить сам цикл несложно. Для этого воспользуемся соотношением <tex> d[i][mask] = p(i, j) + d[j][mask - 2^j] </tex>,  которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> i = 0 </tex>, <tex> mask = 2^n - 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> mask = mask - 2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> mask = 0 </tex>.
 
 
 
Данное решение требует <tex>O({2^n}\times{n})</tex> памяти и <tex>O({2^n}\times{n^2})</tex> времени.
 
 
 
== Реализация ==
 
  //Все переменные используются из описания алгоритма, inf = бесконечность
 
  inputData(); //считывание данных
 
  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 p(i, j) существует
 
            d[i][mask] = min(d[i][mask], d[j][mask - 2 ^ j]);
 
          else
 
            d[i][mask] = inf;
 
  writeData(); // запись данных, ответ хранится в d[0][2 ^ n - 1]
 
 
 
== Ссылки ==
 
*[http://ru.wikipedia.org/wiki/Задача_коммивояжёра Задача коммивояжера в русской википедии]
 
 
 
*[http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden Задача коммивояжера в немецкой википедии]
 
 
 
== Литература ==
 
*''Романовский И. В.'' Дискретный анализ. СПб.: Невский Диалект; БХВ-Петербург, 2003. ISBN 5-7940-0114-3
 
 
 
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4
 
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Динамическое программирование]]
 

Текущая версия на 20:48, 9 января 2016

Перенаправление на: