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

16

В недавнем вопросе обсуждался теперь классический алгоритм динамического программирования для TSP, независимо от Беллмана и Хельда-Карпа . Алгоритм повсеместно сообщается работать в O(2nn2) времени. Однако, как недавно заметил один из моих учеников, это время выполнения может потребовать неоправданно мощной модели вычислений.

Вот краткое описание алгоритма. Вход состоит из ориентированного графа G=(V,E) с n вершинами и неотрицательной функцией длины :ER+ . Для любых вершин s и t и любого подмножества X вершин, исключающих s и t , пусть L(s,X,t) обозначает длину кратчайшего гамильтонова пути от s до tв индуцированном подграфе . Алгоритм Беллмана-Хелда-Карпа основан на следующем повторении (или, как любят его называть экономисты и теоретики управления, «уравнение Беллмана»):G[X{s,t}]

L(s,X,t)={(s,t)if X=minvX (L(s,X{v},v)+(v,t))otherwise

Для любой вершины длина оптимального тура коммивояжера составляет L ( s , V { s } , s ) . Поскольку первый параметр s является постоянным во всех рекурсивных вызовах, существует Θ ( 2 n n ) различных подзадач, и каждая подзадача зависит не более чем от n других. Таким образом, алгоритм динамического программирования выполняется за O ( 2 n n 2 ) времени.sL(s,V{s},s)sΘ(2nn)nO(2nn2)

Или это ?!

Стандартная целочисленная модель ОЗУ допускает манипулирование целыми числами с битами в постоянное время, но по крайней мере для арифметических и логических операций большие целые числа должны быть разбиты на куски размером в слово. (В противном случае могут происходить странные вещи .) Разве это также не относится к доступу к более длинным адресам памяти? Если алгоритм использует суперполиномиальное пространство, разумно ли предполагать, что доступ к памяти требует только постоянного времени?O(logn)

В частности, для алгоритма Беллмана-Хелда-Карпа алгоритм должен преобразовать описание подмножества в описание подмножества X { v } для каждого v , чтобы получить доступ к таблице памятки. Если подмножества представлены целыми числами, эти целые числа требуют n битов и поэтому не могут управляться в постоянное время; если они не представлены целыми числами, их представление нельзя использовать непосредственно в качестве индекса в таблице памятки.XX{v}vn

Итак: Каково фактическое время асимптотики алгоритма Беллмана-Хелда-Карпа?

Jeffε
источник
Ваша ссылка "странные вещи" не работает.
Тайсон Уильямс
Я исправил ссылку.
Джефф

Ответы:

12

Это менее математический ответ, чем философский, но я предпочитаю думать о модели ОЗУ, которая позволяет манипулировать целыми числами в постоянном времени с некоторым количеством битов B, которое неизвестно, но по крайней мере так же велико, как , где S это количество места, которое требует алгоритм. Потому что, если целые числа не были такими большими, как ты вообще мог бы обращаться к своей памяти? Для полиномиальных алгоритмов времени и пространства это то же самое, что и биты O (log n), но для алгоритмов экспоненциального пространства это позволяет избежать проблемы.log2S

Конечно, если S превышает объем памяти, который у вас есть, ваш алгоритм не будет работать вообще. Либо он будет выполняться путем подкачки информации в память и из нее, и вам следует использовать модель иерархии памяти вместо модели ОЗУ.

Дэвид Эппштейн
источник
Я привык к мысли, что модель машины должна зависеть от размера ввода , но есть кое-что странное в том, чтобы позволить модели машины зависеть от алгоритма. Вы действительно хотите, чтобы ваша машина решала любую проблему в PSPACE в постоянном времени, если вы уже используете экспоненциальное пространство? n
Джефф
3
Для меня это не вопрос изменения модели в зависимости от алгоритма, а вопрос наличия модели, которая является фиксированной, но не способной выполнять все алгоритмы (поскольку в ней не хватает места). Для меня это не так уж и отличается от настоящих компьютеров.
Дэвид Эппштейн
1
Я не убежден ответом Дэвида. Здесь есть два вопроса. Один теоретический, другой практический. В теоретическом плане более естественно быть точным относительно модели и соответствующим образом анализировать время работы. В практических условиях нелегко узнать, будет ли на самом деле нехватка памяти в каком-либо конкретном случае из-за различных оптимизаций, которые можно выполнить (и выполнить частичное запоминание и т. Д.), Однако при реализации алгоритма нам придется иметь дело с как мы храним наборы и индексируем их. Вышеуказанная модель не помогает в этом отношении.
Чандра Чекури
8

Эта проблема обсуждается в недавней книге Федора В. Фомина и Дитера Крача « Точные экспоненциальные алгоритмы », где они задают время работы в модели ОЗУ с единичной стоимостью и моделью ОЗУ с логарифмической стоимостью ( - максимальное расстояние между городами и f ( n ) = O ( g ( n ) ), если f ( n ) = O ( g ( n ) p o l y ( n ) ) ):Wf(n)=O(g(n))f(n)=O(g(n)poly(n))

O(2n)2nlogWnO(1)2nlogWnO(1)O(2n)

Александр бондаренко
источник
1
Таким образом, они уклоняются от вопроса, скрывая полиномиальный фактор. Я хочу знать, что такое полиномиальный фактор!
Джеффс
3
Они предполагают, что полиномиальный фактор N2(см. ссылку в моем комментарии).
Александр Бондаренко