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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Динамическое программирование по подмножествам)
(Перенаправление на Гамильтоновы графы)
 
(не показано 76 промежуточных версий 9 участников)
Строка 1: Строка 1:
Задача о коммивояжере (англ. '''travelling - salesman problem''') - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из <tex> N </tex> точек на плоскости.
+
#перенаправление [[Гамильтоновы графы]]
 
 
== Формулировка задачи ==
 
Коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?
 
 
 
== Представление ==
 
 
 
Чтобы использовать математические процессы для решения, реальная ситуация должна отображаться сначала простой моделью. Задачу коммивояжера можно смоделировать с помощью графа. При этом вершины можно считать городами, в то время как каждая дуга <tex>(i, j) </tex> описывает связь между этими 2 вершинами <tex>i</tex> и <tex>j</tex>. Каждая дуга имеет свой вес <tex> с(i, j) </tex>. Поездка - это цикл в этом графе, который проходит через каждую вершину ровно один раз. Целью является найти более короткую поездку.
 
 
 
== Варианты решения  ==
 
 
 
==== Решение перебором ====
 
 
 
Можно предположить, что для решения задачи необходимо сгенерировать все <tex> N! </tex> всевозможных перестановок вершин полного графа, подсчитать для перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>.
 
 
 
Так же известно, что задача о коммивояжере относится к NP-полным задачам.
 
 
 
==== Динамическое программирование по подмножествам ====
 
 
 
Задача о коммивояжере сводится к поиску кратчайшего гамильтонова пути в графе.
 
 
 
Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам - дороги. Пусть в графе <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[i][m]</tex> как наименьшую стоимость пути из вершины <tex>i</tex> в вершину <tex>S</tex>, проходящую (не считая вершины <tex>i</tex>) единожды по всем тем и только тем вершинам <tex>j</tex>, для которых <tex>m_j = 1</tex> (т.е. <tex>m</tex> - подмножество вершин исходного графа, которые осталось посетить).
 
 
 
Конечное состояние - когда находимся в 0-й вершине, все вершины посещены (т.е. <tex>i = 0</tex>, <tex>m = 0</tex>). Для остальных состояний перебираем все возможные переходы из i-й вершины в одну из непосещенных ранее и выбираем способ, дающий минимальный результат. Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).
 
 
 
То есть, <tex>dp[i][m]</tex> считается по следующим соотношениям:
 
 
 
<tex>dp[i][m] = 0</tex>, если <tex>i = 0</tex> и <tex>m = 0</tex>
 
 
 
Иначе
 
 
 
<tex>dp[i][m] = min_{j: m_j=1, (i, j) \in E} \begin{Bmatrix} d(i, j) + dp[j][m - 2^j] \end{Bmatrix}</tex>, если <tex>i\neq 0</tex> и <tex> m \neq 0 </tex>
 
 
 
<tex>dp[i][m] = \infty </tex>, если <tex>i \neq 0</tex>,  <tex>m\neq0</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> j \neq i</tex>, для которого <tex> dp[0][2^n - 1] =  d(i, j) + dp[j][m - 2^j]  </tex> , является предыдущей вершиной пути. Теперь удалим <tex>i</tex> из множества и только что описанным способом найдем вершину предыдущую к <tex>j</tex>. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.
 
 
 
 
 
Данное решение требует <tex>O(2^nn)</tex> памяти и <tex>O(2^nn^2)</tex> времени.
 
 
 
== Источники ==
 
''И.В.Романовский'' - Дискретный анализ;
 
 
 
''Корман, Риверст, Лейзерсон, Штайн'' -  Алгоритмы: построение и анализ;
 
 
 
[http://ru.wikipedia.org/wiki/Задача_коммивояжёра Задача коммивояжёра]
 
 
 
[http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden Problem_des_Handlungsreisenden];
 

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

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