Редактирование: Задача коммивояжера, ДП по подмножествам
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 1: | Строка 1: | ||
| − | + | {{Задача | |
| + | |definition = | ||
| + | '''Задача о коммивояжере''' (англ. '''''Travelling - salesman problem, TSP''''') — задача, в которой коммивояжер должен посетить <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!}\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>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>d[i][mask]</tex> уже найденный оптимальный путь от <tex>i</tex>-ой вершины до <tex>0</tex>-ой, проходящий через те вершины, где <tex>mask_j=1</tex>. Если <tex>mask_j=0</tex>,то эти вершины еще не посещены). | ||
| + | |||
| + | *Начальное состояние - когда находимся в 0-й вершине, ни одна вершина не посещена, а пройденный путь равен <tex>0</tex> (т.е. <tex>i = 0</tex> и <tex>mask = 0</tex>). | ||
| + | *Для остальных состояний (<tex>i \ne 0</tex> или <tex>mask \ne 0</tex>) перебираем все возможные переходы в <tex>i</tex>-ую вершину из любой посещенной ранее и выбираем минимальный результат. | ||
| + | *Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>). | ||
| + | |||
| + | Стоимостью минимального гамильтонова цикла в исходном графе будет значение <tex> d[0][2^n-1]</tex> - стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины. Данное решение требует <tex>O({2^n}\times{n})</tex> памяти и <tex>O({2^n}\times{n^2})</tex> времени. | ||
| + | |||
| + | Для того, чтобы восстановить сам путь, воспользуемся соотношением <tex> d[i][mask] = w(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>dp[mask][i]</tex> содержит булево значение - существует ли в подмножества <tex>mask</tex> гамильтонов путь, заканчивающийся в вершине <tex>i</tex>. | ||
| + | |||
| + | Сама динамика будет такая: <br> | ||
| + | <tex>d[mask][i] = 1</tex>, если <tex>|mask| = 1</tex> и <tex>mask[i] = 1</tex> <br> | ||
| + | <tex>d[mask][i] = OR_{mask[j]=1, (j, i) \in E}d[mask \oplus 2^i][j]</tex>, если <tex>|mask| > 1</tex> и <tex>mask[i]= 1</tex> <br> | ||
| + | <tex>d[mask][i] = 0</tex> во всех остальных случаях. <br> | ||
| + | |||
| + | Это решение, как и решение 2, требует O(2nn) памяти и O(2nn2) времени. Эту оценку можно улучшить, если изменить динамику следующим образом. | ||
| + | |||
| + | Пусть dp'[mask] хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве mask, заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: dp'[mask] будет равно . Для графа G выпишем n масок Mi, для каждой вершины задающие множество вершин, которые связаны ребром в данной вершиной. То есть . | ||
| + | |||
| + | Тогда динамика перепишется следующим образом: | ||
| + | dp'[mask] = 2i, если count(mask) = 1 и bit(i, mask) = 1; | ||
| + | , если count(mask) > 1; | ||
| + | dp'[mask] = 0 во всех остальных случаях. | ||
| + | |||
| + | Особое внимание следует уделить выражению . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве mask без вершины i, а вторая - подмножество вершин, связанных с i ребром. Если эти множества пересекаются хотя бы по одной вершине (их and не равен 0), то, как нетрудно понять, в mask существует гамильтонов путь, заканчивающийся в вершине i. | ||
| + | |||
| + | Окончательная проверка состоит в сравнении dp[2n - 1] c 0. | ||
| + | |||
| + | Это решение использует O(2n) памяти и имеет асимптотику O(2nn). | ||
| + | |||
| + | == Реализация == | ||
| + | Прежде чем писать код, скажем пару слов о порядке обхода состояний. Обозначим за <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> должны быть посещены позже, чтобы к моменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта. | ||
| + | Однако если использовать рекурсию, об этом можно не беспокоиться (и сэкономить немало кода, времени и памяти). | ||
| + | //Все переменные используются из описания алгоритма, inf = бесконечность | ||
| + | '''function''' findCheapest(i, mask): | ||
| + | '''if''' d[i][mask] != inf | ||
| + | '''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] = inf | ||
| + | d[0][0] = 0; | ||
| + | ans = ''findCheapest'' (0, 2 ** n - 1) | ||
| + | if ans == inf | ||
| + | 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''' | ||
| + | |||
| + | == См. также == | ||
| + | |||
| + | *[[NP-полнота задач о гамильтоновом цикле и пути в графах]] | ||
| + | |||
| + | == Источники информации == | ||
| + | *[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 | ||
| + | |||
| + | [[Категория: Дискретная математика и алгоритмы]] | ||
| + | [[Категория: Динамическое программирование]] | ||
