|
|
| (не показана 1 промежуточная версия этого же участника) |
| Строка 1: |
Строка 1: |
| − | {{Задача
| + | #перенаправление [[Гамильтоновы графы]] |
| − | |definition =
| |
| − | '''Задача о коммивояжере''' (англ. ''Travelling salesman problem, TSP'') — задача, в которой коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?
| |
| − | }}
| |
| − | | |
| − | == Варианты решения ==
| |
| − | | |
| − | [[NP-полнота задач о гамильтоновом цикле и пути в графах]]
| |
| − | | |
| − | Так вот задача о коммивояжере относится к классу NP-полных задач. Поэтому, рассмотрим два варианта решения с экспоненциальным временем работы.
| |
| − | | |
| − | ==== Перебор перестановок ====
| |
| − | Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма <tex>O({N!}\times{N})</tex>.
| |
| − | | |
| − | ==== Динамическое программирование по подмножествам (по маскам) ====
| |
| − | | |
| − | Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.
| |
| − | | |
| − | Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам — дороги. Пусть в графе <tex> G=(V,E)</tex> <tex> N </tex>
| |
| − | вершин, пронумерованных от <tex>0</tex> до <tex>N-1</tex> и каждое ребро <tex>(i, j) \in E </tex> имеет некоторый вес <tex> w(i,j)</tex>. Необходимо найти гамильтонов цикл, сумма весов по ребрам которого минимальна.
| |
| − | | |
| − | [[ Гамильтоновы графы | Подробнее можно прочитать в этой статье.]] | |
| − | | |
| − | ==== Оптимизация решения ====
| |
| − | | |
| − | Пусть <tex>dp[mask][i]</tex> содержит булево значение — существует ли в подмножества <tex>mask</tex> гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.
| |
| − | | |
| − | Сама динамика будет такая: <br>
| |
| − | <tex>
| |
| − | d[mask][i] = \left\{\begin{array}{llcl}
| |
| − | 1&;\ |mask| = 1,\ mask_i = 1\\
| |
| − | \bigvee_{mask[j]=1, (j, i) \in E}\limits d[mask \oplus 2^i][j] &;\ |mask| > 1,\ mask_i= 1 \\
| |
| − | 0&;\ otherwise\\
| |
| − | \end{array}\right.
| |
| − | </tex>
| |
| − | | |
| − | Это решение требует <tex>O(2^nn)</tex> памяти и <tex>O(2^nn^2)</tex> времени. Эту оценку можно улучшить, если изменить динамику следующим образом.
| |
| − | | |
| − | Пусть теперь <tex>d'[mask]</tex> хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве <tex>mask</tex>, заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: <tex>d'[mask]</tex> будет равно <tex>\sum_{i \in [0..n-1]}\limits d[mask][i] \cdot 2 ^i </tex>. Для графа <tex>G</tex> выпишем <tex>n</tex> масок <tex>M_i</tex>, для каждой вершины задающие множество вершин, которые связаны ребром в данной вершиной. То есть <tex>M_i = \sum_{j \in [0..n-1]}\limits 2^i \cdot ((i, j) \in E ? 1:0) </tex>.
| |
| − | | |
| − | Тогда динамика перепишется следующим образом: <br>
| |
| − | <tex>
| |
| − | d'[mask][i] = \left\{\begin{array}{llcl}
| |
| − | 2^i&;\ |mask| = 1,\ mask_i = 1\\
| |
| − | \sum_{j \in [0..n-1]}\limits 2^i \cdot ((d[mask \oplus 2^i] \& M_i) \neq 0?1:0) &;\ |mask| > 1 \\
| |
| − | 0&;\ otherwise\\
| |
| − | \end{array}\right.
| |
| − | </tex>
| |
| − | | |
| − | Особое внимание следует уделить выражению <tex>d[mask \oplus 2^i] \& M_i</tex> . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве <tex>mask</tex> без вершины <tex>i</tex>, а вторая — подмножество вершин, связанных с <tex>i</tex> ребром. Если эти множества пересекаются хотя бы по одной вершине (их <tex>\&</tex> не равен <tex>0</tex>), то, как нетрудно понять, в <tex>mask</tex> существует гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.
| |
| − | | |
| − | Окончательная проверка состоит в сравнении <tex>d[2^n - 1]</tex> c <tex>0</tex>.
| |
| − | | |
| − | Это решение использует <tex>O(2^n)</tex> памяти и имеет асимптотику <tex>O(2^nn)</tex>.
| |
| − | | |
| − | == Реализация ==
| |
| − | Прежде чем писать код, скажем пару слов о порядке обхода состояний. Обозначим за <tex>|mask|</tex> количество единиц в маске (иначе говоря количество пройденных вершин не считая текущей). Тогда, поскольку при рассмотрении состояния <tex>\langle i, mask \rangle</tex> мы смотрим на состояния
| |
| − | | |
| − | <tex>\langle j, mask - 2^j \rangle</tex>, и <tex>|mask| = |mask - 2^j| + 1</tex>, то состояния с большим <tex>|mask|</tex> должны быть посещены позже, чтобы к моменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта.
| |
| − | Однако если использовать рекурсию, об этом можно не беспокоиться (и сэкономить немало кода, времени и памяти).
| |
| − | <span style="color:Green">//Все переменные используются из описания алгоритма, <tex>\infty</tex> = бесконечность</span>
| |
| − | '''function''' findCheapest(i, mask):
| |
| − | '''if''' d[i][mask] != <tex>\infty</tex>
| |
| − | '''return''' d[i][mask]
| |
| − | '''for''' j = 0 .. n - 1
| |
| − | '''if''' w(i, j) существует '''and''' j-ый бит mask == 1
| |
| − | d[i][mask] = '''min'''(d[i][mask], findCheapest(j, mask - 2 ** j) + w(i, j))
| |
| − | '''return''' d[i][mask]
| |
| − |
| |
| − | '''for''' i = 0 .. n - 1
| |
| − | '''for''' mask = 0 .. 2 ** n - 1
| |
| − | d[i][mask] = <tex>\infty</tex>
| |
| − | d[0][0] = 0;
| |
| − | ans = findCheapest(0, 2 ** n - 1)
| |
| − | '''if''' ans == <tex>\infty</tex>
| |
| − | exit
| |
| − | Дальше ищем сам путь:
| |
| − | i = 0
| |
| − | mask = 2 ** n - 1
| |
| − | path.push(0)
| |
| − | '''while''' mask != 0
| |
| − | '''for''' j = 0 .. n - 1
| |
| − | '''if''' w(i, j) существует '''and''' j-ый бит mask == 1 '''and''' d[i][mask] == d[j][mask - 2 ** j] + w(i, j)
| |
| − | path.push(j)
| |
| − | i = j
| |
| − | mask = mask - 2 ** j
| |
| − | '''continue'''
| |
| − | | |
| − | == См. также ==
| |
| − | | |
| − | *[[Кратчайший путь в ациклическом графе]]
| |
| − | *[[Задача о наибольшей общей подпоследовательности]]
| |
| − | *[[Задача о наибольшей возрастающей подпоследовательности]]
| |
| − | *[[Задача о рюкзаке]]
| |
| − | *[[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
| |
| − | *[[Гамильтоновы графы]]
| |
| − | | |
| − | == Источники информации ==
| |
| − | *[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
| |
| − | | |
| − | [[Категория: Дискретная математика и алгоритмы]]
| |
| − | [[Категория: Динамическое программирование]]
| |
