Временная сложность алгоритма Хельда-Карпа для ТСП

9

Когда я посмотрел « Динамический программный подход к решению задач секвенирования » Майкла Хелда и Ричарда М. Карпа, у меня возник следующий вопрос: почему сложность их алгоритма для TSP равна (k=2n1k(k1)(n1k))+(n1) (стр. 199), я имею в виду, где они берут фактор k ? Если я правильно понял, k1 означает количество дополнений для каждого подмножества городов. Тогда почему каждая операция сложения связана с неизвестными мне k операциями? Я предполагаю, что это как-то связано с получением минимума, но для вычисления минимума не требуется такого количества операций.

Алгоритм динамического программирования Хелда и Карпа и независимо от него Беллмана работает следующим образом: для каждой пары (S,ci) , означающей путь, проходящий через c1 , все элементы S и заканчивающиеся в ci вычисляются

OPT[S,ci]=min{OPT[S{ci},cj]+d(cj,ci):cjS{ci}},

где d(сJ,ся) означает расстояние между городами сJ и ся . Тогда в формуле из бумаги К означает размер S .

Александр бондаренко
источник

Ответы:

5

Приложение к настоящему документу, разъясняющее термины k(k1) :

Итак, если вы изучите термины в выражении, вы можете представить (как аналогию), что термин является перечислением всех двоичных строк, содержащих 1, которые имеют 1 в первой позиции. Другими словами, мы позволяем каждой позиции в двоичной строке представлять выбор того, находится ли данный один из городов в задаче в точном подмножестве, которое мы рассматриваем в то время. Так, для 5 городов 10101 соответствует подмножеству {1,3,5}.(n1k)kn

Таким образом, чтобы вычислить все подмножества {1, ..., }, мы просто считаем по каждому двоичному подмножеству (т.е. считаем по двоичным строкам) размера = 2 (т.е. двоичные строки размером которые содержат две единицы), затем размер = 3, затем размер = 4, ... затем размер = n. (Обратите внимание, что подмножество size = 1 должно содержать только первый город, и поэтому вычислять его частичное расстояние не имеет значения, поскольку расстояние от 1 -> всех других городов в подмножестве -> 1 равно 0.)nn

В каждом подмножестве с городами мы должны рассмотреть до оптимальных для кандидатов частичных путей. В частности, оптимальный, общий путь мог бы, вероятно, пройти через данное подмножество и в конечном итоге оказаться в любом из городов, кроме первого города. Затем для каждого такого подходящего подпути мы вычисляем оптимальный маршрут до этой точки как минимум любого из предыдущих подпутей size = плюс расстояние от конечного города для этого подпути до конечный город для текущего пути-кандидата. Это дает такие сравнения, которые мы должны сделать. Расхождение между моим членом иkk1k1k1(k1)(k2)(k1)(k2)k(k1)термин в связанном анализе представляет собой нотационную разницу (я бы суммировал в другом диапазоне, учитывая мое определение чем они сделали). Однако, по крайней мере, он должен иллюстрировать сложность квадратичного порядка этого термина.k


Как интересно - я только что закончил кодировать этот точный алгоритм на C ++ несколько минут назад. (Так что простите касательную из чистой теории в небольшое практическое обсуждение. :))

Это стоит времени и пространства - по крайней мере, в моей реализации. Тем не менее, с практической точки зрения, когда ваши потребности в пространстве растут так быстро, они становятся более болезненными, чем требования времени. Например, на моем ПК (с 4 ГБ ОЗУ) я могу решать экземпляры с количеством городов до 24 - даже больше, и мне не хватает памяти.O(2nn2)O(2nn)

Конечно, я мог быть просто плохим программистом, и вы могли бы добиться большего успеха, чем я на практике. :)

Изменить: немного больше деталей по одной детали вашего вопроса: термин происходит от того факта, что в худшем случае вы должны рассчитать частичное, оптимальное расстояние от предыдущих подмножеств (их максимум из них; обратите внимание, что суммируется по в анализе, который вы связали) с текущим. Это требует, опять же в худшем случае, сравнения с подмножествами размера для общего количества .k(k1)nknO(k)k1O(k2)

Кроме того, если мое объяснение не было достаточно ясным, вот несколько хороших конспектов Вазирани ( PDF ). Прокрутите вниз до P. 188 для обсуждения TSP, включая анализ Хельда-Карпа.

Даниэль Апон
источник
О Конечно! Я чувствую себя глупо, думая об этом сейчас; Я обновлю свой ответ. Я действительно слышал этот точный комментарий раньше, и просто передал его, не думая об этом. И да - запись в файл / чтение из файла позволит вам эффективно достичь сколь угодно высокого числа городов. ... это также боль, о которой не стоит беспокоиться, если только вы не пытаетесь решить задачи TSP для реальных целей. Мой был решительно не для практических целей. ;)
Даниэль Апон
2
Время реализовать алгоритм Бьорклунда :)
Суреш Венкат
@ Суреш: Хорошая идея!
Даниэль Апон
@Daniel Apon Не могли бы вы, пожалуйста, уточнить, зачем нам нужны сравнения при расчете "частичного, оптимального расстояния"?
Александр Бондаренко
@ Александр: Конечно, я добавлю это в начало моего ответа.
Даниэль Апон
0

Основная нота

Важно отметить, что мы вычисляем и храним не
«расстояние оптимального пути для combination of k cities»,
а
«расстояние оптимального пути для combination of k cities AND для end-point city from this combination».
Понимание этого поможет понять значение первых двух множителей в следующей формуле.

Первая фаза

Число операций на первом этапе:

ΣК> =2(N-1К-1)выберите комбинацию городаразмера = К-1(К-1)выберите город последнимот К-1 городав выбранной комбинации((N-1)-(К-1))выбрать городэто не в выбранной комбинациидобавить к пути

Отсутствующий верхний индекс в сумме означает for all k>=2 that is valid for binomial coefficient. Таким образом, последний действительный ненулевой член суммы будет для Это означает, что наша сумма не захватывает последние выборы города, чтобы соединиться с первым городом. Есть городов для подключения к первому городу. Итак, наконец, мы добавим этот термин к сумме.Кзнак равноN-1

(N-1N-2)(N-2)1
N-1

Позвольте преобразовать формулу в форму, которую вы предоставляете, которая также находится на странице Википедии Held-Karp .

ΣК> =2(N-1К-1)(К-1)((N-1)-(К-1))знак равноΣК> =2(N-1)!(К-1)!(N-К)!(К-1)(N-К)знак равноΣК> =2(N-1)!К!(N-1-К)!К(К-1)знак равноΣК> =2(N-1К)К(К-1)
Управление биномиальными коэффициентами приводит к: Таким образом, количество операций в первом фаза
ΣК> =2(N-1К)К(К-1)знак равноΣК> =2(N-1)!К!(N-1-К)!К(К-1)знак равноΣК> =2(N-3)!(К-2)!(N-3-(К-2))!(N-1)(N-2)знак равно(N-1)(N-2)ΣК> =2(N-3К-2)знак равно(N-1)(N-2)2N-3
(N-1)(N-2)2N-3+(N-1)

Второй этап

Второй этап - восстановление оптимального пути по меткам, которые мы сделали на первом этапе, одновременно с вычислением расстояний.

Для каждого оптимального пути «для combination of k cities И для end-point city from this combination» мы сохранили второй по последнему слову город.

Чтобы отследить оптимальный путь, нам нужно попросить некоторую структуру данных вернуть второй по величине город «для combination of k cities И для end-point city from this combination». Так что эта структура данных должна быть примерно такой
Map<combination of k cities, Map<last city, second-to-last city>>. В качестве индекса combination of k citiesмы можем использовать, например binary_string[city id]=1 if city id is in combination,. Поэтому нам нужно рассмотреть все элементы, combination of k citiesчтобы идентифицировать комбинацию и индексировать нашу структуру данных. Это дает нам количество операций для второй фазы:

ΣК> =2N-1Кзнак равно(N)(N-1)2-1

dimathe47
источник