Algoritmo de tempo linear para encontrar

Definição. Dado um gráfico e dois vértices e , o problema -shortest-caminhos é encontrar o caminhos mais curtos simples entre e em .$G=(V,E)$$s$$t$$k$$k$$s$$t$$G$

Observe que o comprimento desses caminhos não é necessariamente igual e os vértices e estão necessariamente conectados em . Eu queria saber se há um tempo linear (em termos de e ) algoritmo para este problema.$s$$t$$k$$n$$m$

Analisei alguns artigos na literatura, como " Uma nova implementação do algoritmo de caminhos sem loop de classificação do iene ", mas a complexidade do tempo é realmente alta . Além disso, o outro artigo de Epstein " Encontrar os k caminhos mais curtos " apresenta um algoritmo que encontra os$O(Kn(m+nlogn))$$k$ caminhos mais curtos que não são necessariamente caminhos simples com tempo de execução $O(n+m+k)$.

Existe um algoritmo de tempo linear para o $k$problema de caminhos mais curtos?

Antes de tudo, a resposta que se aplica aqui já foi dada por Raphael nos comentários à pergunta: " Como nem sabemos como encontrar um caminho mais curto e simples no tempo linear, duvido. " A seguir, portanto, assumirei que você está interessado em conhecer os melhores algoritmos disponíveis no estado da arte atual. A seguir, descrevo o melhor limite do pior caso (até onde sei), mas também um algoritmo que pode ser executado em tempo linear em alguns casos específicos.

Mas antes de descrever os últimos desenvolvimentos no estado da arte, eu queria enfatizar a importância de caminhos simples nesse problema específico. De fato, muitas pessoas ignoram a importância desse requisito e algumas nem mesmo o entendem à primeira vista.

Ao calcular o caminho mais curto de um vértice inicial para um vértice de meta, o caminho ideal é necessariamente simples , ou seja, não repete nenhum vértice. No entanto, ao calcular$k$caminhos ideais, o segundo, terceiro, ... os melhores caminhos podem não ser simples. Para provar isso, forneço aqui um exemplo que foi ligeiramente adaptado de Hershberger, Maxel & Suri, 2007:

A Figura mostra um dígrafo cuja solução ideal (do vértice de origem $s$ para o vértice da meta $t$) é o caminho $\pi_1 : \langle s, A, B, C, D, t\rangle$ com um custo igual a 5. Se os caminhos não precisam ser simples, então o segundo e o terceiro caminhos ótimos são $\pi_2 : \langle s, A, B, C, D, C, D, t\rangle$ e $\pi_3 : \langle s, A, B, A, B, C, D, t\rangle$ ambos com um custo igual a 7. No entanto, se for necessário que os caminhos sejam simples, o segundo e o terceiro caminhos ótimos serão $\pi_2 : \langle s, F, t\rangle$ e $\pi_3 : \langle s, G, t\rangle$ com custos 10 e 11, respectivamente.

Dado um gráfico $G(V, E)$ Onde $V$ é o conjunto de vértices e $\langle u, v\rangle\in E, u, v\in V$ se houver uma aresta entre os vértices $u$ e $v$, o estado atual da arte para esse problema da melhor forma possível é descrito abaixo:

A primeira melhoria significativa para resolver o $k$ O problema dos caminhos ótimos é o algoritmo de Eppstein (Eppstein, 1998), executado em $O(|E|+|V|\log |V|+k)$. No entanto, esse algoritmo exige que o gráfico seja fornecido explicitamente.$K^*$alivia esse requisito, mantendo a baixa complexidade (Aljazzar & Leue, 2011) e, além disso, permite a aplicação de heurísticas admissíveis. Nos dois casos, a saída calculada por esses algoritmos não é necessariamente um caminho simples.

Caso seja necessário que os caminhos sejam simples, os melhores resultados são devidos a Yen (Yen, 1971, 1972), generalizado posteriormente por Lawler (Lawler, 1972), que usando estruturas de dados modernas pode ser implementado em $O(k|V|(|E|+|V|\log |V|))$pior das hipóteses. No caso de gráficos não direcionados, Katoh, Ibaraki e Mine (Katoh, Ibaraki & Mine, 1982) aprimoram o algoritmo de Yen para$O(k(|E|+|V|\log |V|))$Tempo. Enquanto o pior caso assintótico de Yen deve enumerar$k$ Como os caminhos mais curtos e simples de um gráfico direcionado permanecem invictos (novamente, até onde eu sei!), várias tentativas foram feitas para superá-lo na prática.

Um desses trabalhos é devido a John Hershberger et al., Que introduziu um algoritmo de caminhos de substituição que é conhecido por falhar pouco. Como resultado, seu algoritmo fornece uma aceleração que cresce linearmente com o número médio de arestas no$k$ caminhos mais curtos, mas, em alguns casos (como gráficos aleatórios), essa aceleração é minimizada.

Espero que isto ajude,

Bibliografia

Aljazzar, H. & Leue, S. (2011). $K^*$: Um algoritmo de pesquisa heurística para encontrar o $k$caminhos mais curtos. Inteligência Artificial, 175 (18), 2129-2154.

Eppstein, D. (1998). Encontrando o$k$caminhos mais curtos. Jornal SIAM sobre Computação, 28 (2), 652-673.

Hershberger, J., Maxel, M. & Suri, S. (2007). Encontrando o$k$caminhos simples mais curtos: Um novo algoritmo e sua implementação. Transações ACM em algoritmos, 3 (4), 45-46

Katoh, N., Ibaraki, T. & Mine, H. (1982). Um algoritmo eficiente para$k$caminhos simples mais curtos. Networks, 12, 411-427.

Lawler, EL (1972). Um procedimento para calcular o$k$melhores soluções para problemas discretos de otimização e sua aplicação ao problema de caminho mais curto. Management Science, 18, 401-405.

Yen, JY (1971). Encontrando o$k$caminhos sem loop mais curtos de uma rede. Management Sciences, 17, 712-716.

Yen, JY (1972). Outro algoritmo para encontrar o$k$caminhos de rede sem loop mais curtos. Proceedings of 41st Management Operations Research Society of America, 20.