Приложение к настоящему документу, разъясняющее термины k(k−1) :
Итак, если вы изучите термины в выражении, вы можете представить (как аналогию), что термин является перечислением всех двоичных строк, содержащих 1, которые имеют 1 в первой позиции. Другими словами, мы позволяем каждой позиции в двоичной строке представлять выбор того, находится ли данный один из городов в задаче в точном подмножестве, которое мы рассматриваем в то время. Так, для 5 городов 10101 соответствует подмножеству {1,3,5}.(n−1k)kn
Таким образом, чтобы вычислить все подмножества {1, ..., }, мы просто считаем по каждому двоичному подмножеству (т.е. считаем по двоичным строкам) размера = 2 (т.е. двоичные строки размером которые содержат две единицы), затем размер = 3, затем размер = 4, ... затем размер = n. (Обратите внимание, что подмножество size = 1 должно содержать только первый город, и поэтому вычислять его частичное расстояние не имеет значения, поскольку расстояние от 1 -> всех других городов в подмножестве -> 1 равно 0.)nn
В каждом подмножестве с городами мы должны рассмотреть до оптимальных для кандидатов частичных путей. В частности, оптимальный, общий путь мог бы, вероятно, пройти через данное подмножество и в конечном итоге оказаться в любом из городов, кроме первого города. Затем для каждого такого подходящего подпути мы вычисляем оптимальный маршрут до этой точки как минимум любого из предыдущих подпутей size = плюс расстояние от конечного города для этого подпути до конечный город для текущего пути-кандидата. Это дает такие сравнения, которые мы должны сделать. Расхождение между моим членом иkk−1k−1k−1(k−1)(k−2)(k−1)(k−2)k(k−1)термин в связанном анализе представляет собой нотационную разницу (я бы суммировал в другом диапазоне, учитывая мое определение чем они сделали). Однако, по крайней мере, он должен иллюстрировать сложность квадратичного порядка этого термина.k
Как интересно - я только что закончил кодировать этот точный алгоритм на C ++ несколько минут назад. (Так что простите касательную из чистой теории в небольшое практическое обсуждение. :))
Это стоит времени и пространства - по крайней мере, в моей реализации. Тем не менее, с практической точки зрения, когда ваши потребности в пространстве растут так быстро, они становятся более болезненными, чем требования времени. Например, на моем ПК (с 4 ГБ ОЗУ) я могу решать экземпляры с количеством городов до 24 - даже больше, и мне не хватает памяти.O(2nn2)O(2nn)
Конечно, я мог быть просто плохим программистом, и вы могли бы добиться большего успеха, чем я на практике. :)
Изменить: немного больше деталей по одной детали вашего вопроса: термин происходит от того факта, что в худшем случае вы должны рассчитать частичное, оптимальное расстояние от предыдущих подмножеств (их максимум из них; обратите внимание, что суммируется по в анализе, который вы связали) с текущим. Это требует, опять же в худшем случае, сравнения с подмножествами размера для общего количества .k(k−1)nknO(k)k−1O(k2)
Кроме того, если мое объяснение не было достаточно ясным, вот несколько хороших конспектов Вазирани ( PDF ). Прокрутите вниз до P. 188 для обсуждения TSP, включая анализ Хельда-Карпа.
Основная нота
Важно отметить, что мы вычисляем и храним не
«расстояние оптимального пути для
combination of k cities
»,а
«расстояние оптимального пути для
combination of k cities
AND дляend-point city from this combination
».Понимание этого поможет понять значение первых двух множителей в следующей формуле.
Первая фаза
Число операций на первом этапе:Σk > = 2(n - 1к - 1)выберите комбинацию городаразмером = k - 1⋅( к - 1 )выберите город последнимиз к - 1 городав выбранной комбинации⋅( ( n - 1 ) - ( k - 1 ) )выбрать городэто не в выбранной комбинациидобавить к пути
Отсутствующий верхний индекс в сумме означаетk = n - 1
(n - 1п - 2) ⋅(n-2)⋅1 n - 1
for all k>=2 that is valid for binomial coefficient
. Таким образом, последний действительный ненулевой член суммы будет для Это означает, что наша сумма не захватывает последние выборы города, чтобы соединиться с первым городом. Есть городов для подключения к первому городу. Итак, наконец, мы добавим этот термин к сумме.Позвольте преобразовать формулу в форму, которую вы предоставляете, которая также находится на странице Википедии Held-Karp .
Второй этап
Второй этап - восстановление оптимального пути по меткам, которые мы сделали на первом этапе, одновременно с вычислением расстояний.
Для каждого оптимального пути «для
combination of k cities
И дляend-point city from this combination
» мы сохранили второй по последнему слову город.Чтобы отследить оптимальный путь, нам нужно попросить некоторую структуру данных вернуть второй по величине город «для
Σk > = 2n - 1к =( n ) ( n - 1 )2- 1
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
чтобы идентифицировать комбинацию и индексировать нашу структуру данных. Это дает нам количество операций для второй фазы:источник