Complexidade temporal do algoritmo Held-Karp para TSP

Quando examinei " Uma abordagem de programação dinâmica para problemas de seqüenciamento ", de Michael Held e Richard M. Karp, surgiu a seguinte pergunta: por que a complexidade de seu algoritmo para TSP é (p. 199), quero dizer aonde eles levam o fator ? Se entendi corretamente, significa o número de adições para cada subconjunto de cidades. Então, por que cada operação de adição é associada a operações desconhecidas para mim ? Suponho que esteja conectado de alguma forma a reduzir o mínimo, mas calcular o mínimo não parece exigir tantas operações. $(\sum_{k=2}^{n-1}k(k-1)\binom{n-1}{k})+(n-1)$ $k$ $k-1$ $k$

O algoritmo de programação dinâmica de Held e Karp e independentemente Bellman é executado da seguinte forma: para cada par $(S,c_i)$ , significando um caminho passando por $c_1$ , todos os elementos de $S$ e terminando na computação $c_i$

$OPT[S,c_i]=min\{OPT[S\setminus\{c_i\},c_j]+d(c_j,c_i):c_j\in S\setminus\{c_i\}\},$

onde $d(c_j,c_i)$ significa a distância entre as cidades $c_j$ e $c_i$ . Em seguida, na fórmula do papel $k$ significa o tamanho de $S$ .

ds.algorithms tsp exp-time-algorithms Oleksandr Bondarenko
fonte

Respostas:

Adendo abaixo, esclarecendo os termos : $k(k-1)$

Portanto, se você examinar os termos da expressão, poderá visualizar (como analogia) o termo é uma enumeração de todas as cadeias binárias que contêm 1 que possuem 1 na primeira posição. Em outras palavras, deixamos que cada posição na cadeia binária represente a escolha de se uma determinada cidades no problema está no subconjunto exato que estamos considerando no momento. Portanto, para 5 cidades, 10101 corresponde ao subconjunto {1,3,5}. $n-1 \choose k$ $k$ $n$

Assim, para calcular todos os subconjuntos de {1, ..., }, simplesmente contamos através de cada subconjunto binário (ou seja, contamos com cadeias binárias) de tamanho = 2 (ou seja, cadeias binárias de tamanho que contêm dois 1s), então size = 3, size = 4, ... size = n. (Observe que o subconjunto size = 1 deve conter apenas a primeira cidade e, portanto, é irrelevante calcular sua distância parcial, pois a distância de 1 -> todas as outras cidades do subconjunto -> 1 é exatamente 0.) $n$ $n$

Em cada subconjunto com cidades, temos que considerar até caminhos parciais ótimos para candidatos. Especificamente, o caminho ideal ideal total poderia atravessar o subconjunto especificado e terminar em qualquer uma das cidades , excluindo a primeira cidade. Em seguida, para cada subcaminho candidato, calculamos o passeio ideal até esse ponto como o mínimo de qualquer dos subcaminhos size = anteriores, mais a distância da cidade terminal desse subcaminho até o cidade terminal para o atual subcaminho candidato. Isso fornece as comparações que devemos fazer. A discrepância entre o meu termo e o $k$ $k-1$ $k-1$ $k-1$ $(k-1)(k-2)$ $(k-1)(k-2)$ $k(k-1)$ O termo na análise vinculada é uma diferença notacional (eu somaria em um intervalo diferente, dada minha definição de que eles). No mínimo, porém, deve ilustrar a complexidade de ordem quadrática desse termo. $k$

Que interessante - eu acabei de codificar esse algoritmo exato em C ++ há alguns minutos atrás. (Então, perdoe a tangente da teoria pura em uma pequena discussão prática. :))

Custa tempo e espaço - pelo menos na minha implementação. Na prática, porém, quando seus requisitos de espaço crescem tão rápido, eles se tornam muito mais dolorosos do que os requisitos de tempo. Por exemplo, no meu PC (com 4 GB de RAM), posso resolver instâncias com até 24 cidades - mais do que isso, e fico sem memória. $O(2^n n^2)$ $O(2^n n)$

É claro que eu poderia ser um péssimo programador e você poderá fazer melhor do que eu na prática. :)

Edit: Um pouco mais de detalhes sobre um detalhe da sua pergunta: O termo vem do fato de que, no pior caso, você deve calcular a distância parcial ideal dos subconjuntos anteriores (há no máximo deles; observe que é somado sobre na análise que você vinculou) à análise atual. Isso requer, novamente no pior caso, comparações com subconjuntos de tamanho para um total de . $k(k-1)$ $n$ $k$ $n$ $O(k)$ $k-1$ $O(k^2)$

Além disso, se minha explicação não foi clara o suficiente, aqui estão algumas notas de aula agradáveis de Vazirani ( PDF ). Role até a página 188 para uma discussão sobre TSP, incluindo uma análise de Held-Karp.

Daniel Apon
fonte

Ah, claro! Eu me sinto boba pensando nisso agora; Vou atualizar minha resposta. Na verdade, eu já tinha ouvido esse comentário exato antes e o repassado sem pensar nisso. E sim - gravar em um arquivo / ler um arquivo permitirá que você vá efetivamente subir arbitrariamente para o número de cidades. ... também é uma dor que não vale a pena se preocupar, a menos que você esteja tentando resolver instâncias de TSP com um propósito real. O meu não era decididamente para um propósito prático. ;)

Daniel Apon 6/12/10

Tempo para implementar o algoritmo Bjorklund :)

Suresh Venkat

@Suresh: Boa ideia!

Daniel Apon 6/12/10

@Daniel Apon Você poderia, por favor, precisar com precisão por que precisamos de comparações ao calcular "a distância parcial e ideal"?

Oleksandr Bondarenko

@Oleksandr: Claro, vou adicioná-lo ao topo da minha resposta.

precisa saber é o seguinte

Nota principal

É importante observar que computamos e não armazenamos
"distância do caminho ideal para combination of k cities",
mas
"distância do caminho ideal para combination of k cities AND para end-point city from this combination".
Compreender isso ajudará no significado dos dois primeiros multiplicadores na fórmula a seguir.

Primeira fase

O número de operações na primeira fase é:

\sum_{k >= 2} \underset{\begin{matrix} choose city combination \\ of size = k - 1 \end{matrix}}{\underset{⏟}{(\binom{n - 1}{k - 1})}} \cdot \underset{\begin{matrix} choose city to be the last \\ from k - 1 cities \\ in chosen combination \end{matrix}}{\underset{⏟}{(k - 1)}} \cdot \underset{\begin{matrix} choose city \\ that is not in chosen combination \\ to add to path \end{matrix}}{\underset{⏟}{((n - 1) - (k - 1))}}

$\displaystyle \sum_{k>=2} \underbrace{ \binom{n-1}{k-1} }_{\substack{ \text{choose city combination} \\ \text{of size = $k-1$}}} \cdot \underbrace{ (k-1) }_{\substack{ \text{choose city to be the last} \\ \text{from $k-1$ cities} \\ \text{in chosen combination} } } \cdot \underbrace{ ((n-1)-(k-1)) }_{ \substack{ \text{choose city} \\ \text{that is not in chosen combination} \\ \text{to add to path} } }$

Sobrescrito ausente na soma significa for all k>=2 that is valid for binomial coefficient. Portanto, o último termo válido não nulo da soma será para Isso significa que nossa soma não captura as últimas opções da cidade para se conectar à primeira cidade. Existem cidades para se conectar à primeira cidade. Então, finalmente, adicionaremos esse termo à soma. $k=n-1$

(\binom{n - 1}{n - 2}) \cdot (n - 2) \cdot 1

$\binom{n-1}{n-2} \cdot (n-2) \cdot 1$

n - 1

$n-1$

Deixe transformar a fórmula para formar o que você fornece, que também está na página da Held-Karp Wikipedia .

\sum_{k >= 2} (\binom{n - 1}{k - 1}) \cdot (k - 1) \cdot ((n - 1) - (k - 1)) = \sum_{k >= 2} \frac{(n - 1)!}{(k - 1)! (n - k)!} \cdot (k - 1) \cdot (n - k) = \sum_{k >= 2} \frac{(n - 1)!}{k! (n - 1 - k)!} \cdot k \cdot (k - 1) = \sum_{k >= 2} (\binom{n - 1}{k}) \cdot k \cdot (k - 1)

$\displaystyle \sum_{k>=2} \binom{n-1}{k-1} \cdot (k-1) \cdot ((n-1)-(k-1))= \sum_{k>=2} \frac{(n-1)!}{(k-1)!(n-k)!} \cdot (k-1) \cdot (n-k)= \sum_{k>=2} \frac{(n-1)!}{k!(n-1-k)!} \cdot k \cdot (k-1)= \sum_{k>=2} \binom{n-1}{k} \cdot k \cdot (k-1)$ manipulação de coeficientes binomiais leva a: Portanto, o número de operações na primeira fase é

\sum_{k >= 2} (\binom{n - 1}{k}) \cdot k \cdot (k - 1) = \sum_{k >= 2} \frac{(n - 1)!}{k! (n - 1 - k)!} \cdot k \cdot (k - 1) = \sum_{k >= 2} \frac{(n - 3)!}{(k - 2)! (n - 3 - (k - 2))!} \cdot (n - 1) \cdot (n - 2) = (n - 1) \cdot (n - 2) \sum_{k >= 2} (\binom{n - 3}{k - 2}) = (n - 1) \cdot (n - 2) \cdot 2^{n - 3}

$\displaystyle \sum_{k>=2} \binom{n-1}{k} \cdot k \cdot (k-1) = \sum_{k>=2} \frac{(n-1)!}{k!(n-1-k)!} \cdot k \cdot (k-1) = \sum_{k>=2} \frac{(n-3)!}{(k-2)!(n-3-(k-2))!} \cdot (n-1) \cdot (n-2)= (n-1) \cdot (n-2)\sum_{k>=2} \binom{n-3}{k-2}=(n-1) \cdot (n-2) \cdot 2^{n-3}$

(n - 1) \cdot (n - 2) \cdot 2^{n - 3} + (n - 1)

$(n-1) \cdot (n-2) \cdot 2^{n-3}+(n-1)$

Segunda fase

A segunda fase é restaurar o caminho ideal por marcas que fizemos na primeira fase simultaneamente com as distâncias de computação.

Para cada caminho ideal "para combination of k cities E para end-point city from this combination", salvamos a penúltima cidade.

Para voltar ao caminho ideal, precisamos solicitar alguma estrutura de dados para retornar a penúltima cidade "para combination of k cities AND para end-point city from this combination". Portanto, essa estrutura de dados deve ser algo parecido
Map<combination of k cities, Map<last city, second-to-last city>>. Como índice de combination of k citiespodemos usar, por exemplo binary_string[city id]=1 if city id is in combination,. Portanto, precisamos examinar todos os elementos combination of k citiespara identificar combinações e indexar nossa estrutura de dados. Isso nos fornece o número de operações para a segunda fase:

\sum_{k >= 2}^{n - 1} k = \frac{(n) (n - 1)}{2} - 1

$\displaystyle \sum_{k>=2}^{n-1} k = \frac{(n)(n-1)}{2} - 1$

dimathe47
fonte