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)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)G=(V,E) com nn vértices e uma função de comprimento não negativo ℓ : E→ R+ℓ:E→R+ . Para quaisquer vértices ss e tt , e qualquer subconjunto XX de vértices que exclui ss e tt , deixe L ( s , X, t )eu(s,X,t) denotar o comprimento do caminho hamiltoniano mais curto de ss a ttno subgrafo induzido G [ X∪ { s , t } ]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 )minv ∈ X ( L(s,X∖ { v } , v ) + ℓ ( v , t ) )se X=∅otherwiseL(s,X,t)={ℓ(s,t)if X=∅minv∈X (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 nssL(s,V∖{s},s)L(s,V∖{s},s)ssΘ(2nn)Θ(2nn)nnO(2nn2)O(2nn2)
Ou faz ?!
O modelo padrão de RAM inteira permite a manipulação em tempo constante de números inteiros com O(logn)O(log⁡n) 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.XXX∖{v}X∖{v}vvnn
Então: qual é o tempo real de execução assintótica do algoritmo Bellman-Held-Karp?
Seu link "coisas estranhas" está quebrado.
Eu consertei o link.
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.log2Slog2⁡S
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.
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? nn
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.
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
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 ) ) ):WWf(n)=O∗(g(n))f(n)=O∗(g(n))f(n)=O(g(n)poly(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)O∗(2n)2nlogWnO(1)2nlog⁡WnO(1)2nlogWnO(1)∉O∗(2n)2nlog⁡WnO(1)∉O∗(2n)
Portanto, eles evitam o problema ocultando o fator polinomial. Eu quero saber qual é o fator polinomial!