A complexidade temporal do algoritmo Bellman-Held-Karp para TSP, leva 2

16

Uma pergunta recente discutiu o agora clássico algoritmo de programação dinâmica para TSP, devido independentemente a Bellman e Held-Karp . O algoritmo é universalmente relatado para ser executado no tempo O(2nn2) . No entanto, como um dos meus alunos apontou recentemente, esse tempo de execução pode exigir um modelo de computação irracionalmente poderoso.

Aqui está uma breve descrição do algoritmo. A entrada consiste em um gráfico direcionado G=(V,E) com n vértices e uma função de comprimento não negativo :ER+ . Para quaisquer vértices s e t , e qualquer subconjunto X de vértices que exclui s e t , deixe eu(s,X,t) denotar o comprimento do caminho hamiltoniano mais curto de s a tno subgrafo induzido G[X{s,t}] . O algoritmo Bellman-Held-Karp é baseado na seguinte recorrência (ou como economistas e teóricos do controle gostam de chamá-lo de "equação de Bellman"):

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

Para qualquer vértice , a duração do passeio ideal para o vendedor viajante é . Como o primeiro parâmetro s é constante em todas as chamadas recursivas, existem \ Theta (2 ^ nn) subproblemas diferentes e cada subproblema depende de no máximo n outros. Assim, o algoritmo de programação dinâmica é executado no tempo O (2 ^ nn ^ 2) .L ( s , V { s } , s ) s Θ ( 2 n n ) n O ( 2 nsL(s,V{s},s)sΘ(2nn)nO(2nn2)

Ou faz ?!

O modelo padrão de RAM inteira permite a manipulação em tempo constante de números inteiros com O(logn) bits, mas pelo menos para operações aritméticas e lógicas , números inteiros maiores devem ser divididos em blocos do tamanho de palavras. (Caso contrário, coisas estranhas podem acontecer.) Isso também não se aplica ao acesso a endereços de memória mais longos? Se um algoritmo usa espaço superpolinomial, é razoável supor que o acesso à memória exija apenas tempo constante?

Para o algoritmo Bellman-Held-Karp, em particular, o algoritmo deve transformar a descrição do subconjunto na descrição do subconjunto , para cada , para acessar a tabela de memorização. Se os subconjuntos são representados por números inteiros, esses números inteiros requerem bits e, portanto, não podem ser manipulados em tempo constante; se eles não são representados por números inteiros, sua representação não pode ser usada diretamente como um índice na tabela de memorização.XX{v}vn

Então: qual é o tempo real de execução assintótica do algoritmo Bellman-Held-Karp?

Jeffε
fonte
Seu link "coisas estranhas" está quebrado.
Tyson Williams
Eu consertei o link.
Jeffε

Respostas:

12

Isso é menos uma resposta matemática do que uma filosófica, mas eu prefiro pensar em um modelo de RAM que permita a manipulação em tempo constante de números inteiros com algum número B de bits que é desconhecido, mas pelo menos tão grande quanto o , onde S é a quantidade de espaço que o algoritmo requer. Porque, se os números inteiros não fossem tão grandes, como você poderia endereçar sua memória? Para algoritmos polinomiais de tempo e espaço, é o mesmo que O (log n) bits, mas para algoritmos de espaço exponencial, evita o problema.log2S

Obviamente, se S exceder a quantidade de memória que você realmente possui, seu algoritmo não funcionará. Ou, ele será executado paginando as informações para dentro e para fora da memória e você deverá usar um modelo de hierarquia de memória em vez do modelo de RAM.

David Eppstein
fonte
Estou acostumado com a ideia de que o modelo da máquina deve depender do tamanho da entrada , mas há algo um pouco complicado em deixar o modelo da máquina depender do algoritmo. Deseja realmente deixar sua máquina resolver qualquer problema no PSPACE em tempo constante, desde que você já esteja usando espaço exponencial? n
Jeffε
3
Para mim, é menos uma questão de fazer o modelo variar dependendo do algoritmo, e mais uma questão de ter um modelo que seja fixo, mas não capaz de executar todos os algoritmos (porque fica sem espaço). Isso não parece tão diferente dos computadores reais, para mim.
David Eppstein
11
Não estou convencido pela resposta de David. Há duas questões aqui. Um é teórico, o outro prático. No cenário teórico, é mais natural ser preciso sobre o modelo e analisar o tempo de execução adequadamente. No cenário prático, não é fácil saber se alguém realmente ficaria sem memória em uma instância específica, devido às várias otimizações que se pode fazer (e fazer memoização parcial, etc.); no entanto, ao implementar o algoritmo, teremos que lidar com como armazenamos os conjuntos e indexamos neles. O modelo acima não ajuda nesse sentido.
Chandra Chekuri 13/09/11
8

Há uma discussão sobre essa questão no livro recente de Fedor V. Fomin e Dieter Kratsch " Algoritmos exponenciais exatos ", onde eles especificam o tempo de execução no modelo de RAM de custo unitário e no modelo de RAM de custo de log ( - a distância máxima entre as cidades e f ( n ) = S * ( g ( n ) ) , se f ( n ) = o ( g ( n ) p o l y ( n ) ) ):Wf(n)=O(g(n))f(n)=O(g(n)poly(n))

e 2 n logW n O ( 1 ) (observe, 2 n logW n O ( 1 ) O ( 2 n )), respectivamente.O(2n)2nlogWnO(1)2nlogWnO(1)O(2n)

Oleksandr Bondarenko
fonte
11
Portanto, eles evitam o problema ocultando o fator polinomial. Eu quero saber qual é o fator polinomial!
Jeffε
3
Eles assumem que o fator polinomial é (veja o link no meu comentário). n2
Oleksandr Bondarenko