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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Перенаправление на Гамильтоновы графы)
 
(не показано 87 промежуточных версий 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>(i, j) \in E </tex> имеет некоторый вес <tex> d(i, j)</tex>. Необходимо найти гамильтонов путь, сумма весов по ребрам которого минимальна.
 
 
 
Пусть множество элементов занумеровано и закодировано последовательностью битов длины <tex> N </tex>. Элементами множества будут являться вершины графа. Для простоты мы будем считать, что граф является неориентированным.
 
 
 
<tex> bit(i, pos) </tex> - <tex>i</tex>-й бит последовательности <tex>pos</tex>.
 
 
 
<tex> count(pos)</tex> - количество битов <tex>1</tex> в последовательности <tex>pos</tex>.
 
 
 
Если <tex>i</tex>-й бит последовательности равен <tex>1</tex>, то <tex>i</tex>-й элемент входит в подмножество, иначе - нет.
 
 
 
Пусть <tex> dp[pos][i] </tex> обозначает длину кратчайшего гамильтонова пути подмножества вершин <tex>pos </tex>, заканчивающегося в вершине <tex> i </tex>.
 
 
 
 
 
Динамика считается по следующим соотношениям:
 
 
 
<tex> dp[pos][i] = 0 </tex>, если <tex> count(pos) = 1</tex> и <tex> bit(i, pos) = 1</tex>;
 
 
 
<tex> dp[pos][i] = min_{bit(j, pos)=1,(j, i)\in E} \begin{Bmatrix} dp[pos \oplus 2^i][j]+d(j, i) \end{Bmatrix}</tex>, если <tex> count(pos) > 1 </tex> и <tex> bit(i, pos) = 1</tex>;
 
 
 
<tex>dp[pos][i] = \mathcal {1} </tex> во всех остальных случаях.
 
 
 
Теперь искомая минимальная длина пути <tex> p_{min} = min_{i \in [0...n-1]}\begin{bmatrix}dp[2^n - 1][i] \end{bmatrix}
 
</tex>. Если <tex> p_{min} = \mathcal {1} </tex>, то гамильтонова пути в графе, нет. Восстановить сам путь несложно. Пусть минимальный путь заканчивается в вершине <tex>i</tex>. Тогда <tex> j \neq i</tex>, для которого <tex> dp[2^n - 1][i] =  dp[2^n - 1 \oplus 2^i][j] + d(j, i) </tex> , является предыдущей вершиной пути. Теперь удалим <tex>i</tex> из множества и только что описанным способом найдем вершину предыдущую к <tex>j</tex>. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.
 
 
 
 
 
Данное решение требует <tex>O(2n^n)</tex> памяти и <tex>O(2^nn^2)</tex> времени.
 
 
 
== Источники ==
 
''И.В.Романовский'' - Дискретный анализ;
 
 
 
''Корман, Риверст, Лейзерсон, Штайн'' -  Алгоритмы: построение и анализ;
 
 
 
[http://ru.wikipedia.org/wiki/Задача_коммивояжёра Задача коммивояжёра]
 
 
 
[http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden Problem_des_Handlungsreisenden];
 
 
 
[http://codeforces.ru/blog/entry/337 Динамика по подмножествам и маршруты в графах];
 

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

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