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 . 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 com vértices e uma função de comprimento não negativo . Para quaisquer vértices e , e qualquer subconjunto de vértices que exclui e , deixe denotar o comprimento do caminho hamiltoniano mais curto de a no subgrafo induzido . 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"):
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 n
Ou faz ?!
O modelo padrão de RAM inteira permite a manipulação em tempo constante de números inteiros com 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.
Então: qual é o tempo real de execução assintótica do algoritmo Bellman-Held-Karp?
Respostas:
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.
fonte
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 ) ) ):W f(n)=O∗(g(n)) f(n)=O(g(n)poly(n))
fonte