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

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

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

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

Или это ?!

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

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

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

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

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

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

$\mathcal{O}^{\ast}(2^n)$$2^n\log Wn^{\mathcal{O}(1)}$$2^n\log Wn^{\mathcal{O}(1)}\notin\mathcal{O}^{\ast}(2^n)$