Mostrar código-fonte de Problema do caminho mais longo

Em [[teoria dos grafos]] e [[ciência da computação teórica]], o '''problema do caminho mais longo''' é encontrar um [[Caminho (teoria dos grafos)|caminho]] simples de comprimento máximo num dado grafo. Um caminho é chamado simples se não tem nenhum vértice repetido; O comprimento de um caminho pode ser medido tanto pelo seu número de arestas, ou (em [[Lista de termos técnicos relacionados à teoria dos grafos|grafos ponderados]]) pela soma dos pesos das suas bordas. Em contraste com o [[Problema do caminho mínimo|problema do caminho mais curto]], que pode ser resolvido em tempo polinomial em gráficos sem ciclos de peso negativo, o problema do caminho mais longo é [[NP-difícil]], o que significa que ele não pode ser resolvido em tempo polinomial para grafos arbitrários a menos que [[P versus NP|P = NP]]. Fortes resultados difíceis são também conhecidos por mostrar que é difícil [[Algoritmo de aproximação|aproximar]]. No entanto, ele tem uma solução em tempo linear para [[Grafos acíclicos dirigidos|grafos acíclicos direcionados]], que tem importantes aplicações em encontrar o [[caminho crítico]] em problemas de agendamento.

== NP-dificuldade ==
A NP-dificuldade do problema do caminho mais longo sem peso pode ser demonstrado por meio de uma redução do problema do [[Problema do caminho hamiltoniano|caminho Hamiltoniano]]: um grafo ''G'' tem um caminho hamiltoniano se e somente se o seu caminho mais longo tem um comprimento ''n'' - 1, onde ''n'' é o número de vértices em ''G''. Em razão do fato de que o problema caminho hamiltoniano é NP-completo, esta redução mostra que a versão de decisão do problema do caminho mais longo é também NP-completo. Na decisão, a entrada deste problema é um grafo ''G'' e um número ''k;'' a saída desejada é "sim" se ''G'' contém um caminho de ''k'' ou mais arestas, e ''não'' de outra maneira.<ref>{{citation|title = Combinatorial Optimization: Polyhedra and Efficiency, Volume 1|volume = 24|series = Algorithms and Combinatorics|first = Alexander|last = Schrijver|authorlink = Alexander Schrijver|publisher = Springer|year = 2003|isbn = 9783540443896|page = 114|url = http://books.google.com/books?id=mqGeSQ6dJycC&pg=PA114}}.</ref>

Se o problema do caminho mais longo pode ser resolvido em tempo polinomial, que pode ser utilizado para resolver este problema de decisão, por descoberta de um caminho mais longo e, em seguida, comparando a sua extensão para o número ''k''. Portanto, o problema do caminho mais longo é NP-difícil. Não é NP-completo, uma vez que não é um problema de decisão. <ref>{{citation|title = Introduction To Algorithms|first1 = Thomas H.|last1 = Cormen|author1-link = Thomas H. Cormen|first2 = Charles E.|last2 = Leiserson|author2-link = Charles E. Leiserson|first3 = Ronald L.|last3 = Rivest|author3-link = Ron Rivest|first4 = Clifford|last4 = Stein|author4-link = Clifford Stein|edition = 2nd|publisher = MIT Press|year = 2001|isbn = 9780262032933|url = http://books.google.com/books?id=NLngYyWFl_YC&pg=PA978|page = 978}}.</ref>

Em [[Grafo completo|grafos completos]] com pesos das arestas não-negativos, o problema do caminho mais longo com peso é o mesmo que o [[Problema do caixeiro-viajante|problema do caminho do caixeiro viajante]], porque o caminho mais longo sempre inclui todos os vértices.<ref>{{citation|title = Combinatorial Optimization: Networks and Matroids|first = Eugene L.|last = Lawler|authorlink = Eugene Lawler|publisher = Courier Dover Publications|year = 2001|isbn = 9780486414539|page = 64|url = http://books.google.com/books?id=m4MvtFenVjEC&pg=PA64}}.</ref>

== Gráficos acíclicos e caminhos críticos ==
Um caminho mais longo entre dois vértices dado ''s'' e ''t'' em um grafo ponderado ''G'' é a mesma coisa que um caminho mais curto em um gráfico ''-G'' derivada de ''G'', alterando todo o peso de sua negação. Portanto, se os caminhos mais curtos podem ser encontrados em ''-G'', em seguida, caminhos mais longos podem também ser encontrados em ''G.''<ref name=":0">{{citation|title = Algorithms|first1 = Robert|last1 = Sedgewick|author1-link = Robert Sedgewick (computer scientist)|first2 = Kevin Daniel|last2 = Wayne|edition = 4th|publisher = Addison-Wesley Professional|year = 2011|isbn = 9780321573513|pages = 661–666|url = http://books.google.com/books?id=idUdqdDXqnAC&pg=PA661}}.</ref>

Para a maioria dos gráficos, esta transformação não é útil porque cria ciclos de comprimento negativo em ''-G''. Mas, se ''G'' é um [[Grafos acíclicos dirigidos|gráfico acíclico dirigido]], então ciclos negativos não podem ser criados, e um caminho mais longo em ''G'' pode ser encontrado no [[tempo linear]] através da aplicação de um algoritmo de tempo linear para os caminhos mais curtos em ''-G'', que também é um gráfico acíclico dirigido.<ref name=":0" /> Por exemplo, para cada vértice v em um determinado DAG, o comprimento do caminho mais longo terminando em v pode ser obtido pelos seguintes passos:
# Encontre uma [[ordenação topológica]] do dado DAG.
# Para cada vértice ''v'' do DAG, na ordenação topológica, calcular o comprimento do caminho mais longo terminando em ''v'', olhando para os seus vizinhos de entrada e adicionando um ao comprimento máximo gravado para os vizinhos. Se ''v'' não tem vizinhos de entrada, definir o comprimento do caminho mais longo terminando no ''v'' para zero. Em ambos os casos, registrar este número para que passos posteriores do algoritmo possa acessá-lo.
Uma vez que isto tenha sido feito, o caminho mais longo em todo o DAG pode ser obtido começando pelo vértice v com o valor maior registrado, então repetidamente andando para trás para a sua vizinha de entrada com o maior valor registrado, e invertendo a sequência de vértices encontrados desta maneira.

O método do [[caminho crítico]] para programar um conjunto de atividades envolve a construção de um gráfico acíclico dirigido em que os vértices representam marcos do projeto e as arestas representam as atividades que devem ser executadas após um marco e antes de outro; cada aresta é ponderada por uma estimativa de quantidade de tempo que a atividade correspondente levará para ser concluída. Em tal gráfico, o caminho mais longo a partir do primeiro marco para o último é o caminho crítico, que descreve o tempo total para a conclusão do projeto.<ref name=":0" />

Caminhos mais longos de gráficos acíclicos dirigidos também podem ser aplicados no desenho gráfico em camadas: atribuir cada vértice v de um gráfico acíclico dirigido G para a camada cujo número é o comprimento do caminho mais longo terminando em resultados v numa atribuição de camada para G com o mínimo número possível de camadas.<ref>{{citation
 |last1 = Di Battista|first1 = Giuseppe|last2 = Eades|first2 = Peter|author2-link = Peter Eades|last3 = Tamassia|first3 = Roberto|author3-link = Roberto Tamassia|last4 = Tollis|first4 = Ioannis G.|contribution = Layered Drawings of Digraphs|isbn = 978-0-13-301615-4|pages = 265–302|publisher = [[Prentice Hall]]|title = Graph Drawing: Algorithms for the Visualization of Graphs|year = 1998}}.</ref>

== Aproximação ==
Björklund, Husfeldt & Khanna (2004) escrevem que o problema do caminho mais longo em gráficos sem direções não ponderadas "é notório para a dificuldade de entender a sua difícil aproximação". <ref name=":1">{{citation
 |last1 = Björklund|first1 = Andreas|last2 = Husfeldt|first2 = Thore|last3 = Khanna|first3 = Sanjeev|contribution = Approximating longest directed paths and cycles|location = Berlin|mr = 2160935|pages = 222–233|publisher = Springer-Verlag|series = [[Lecture Notes in Computer Science]]|title = Proc. Int. Coll. Automata, Languages and Programming (ICALP 2004)|volume = 3142|year = 2004}}.</ref> O melhor algoritmo de aproximação de tempo polinomial conhecido para este caso alcança apenas uma relação de aproximação muito fraca, <math>n/\exp(\Omega(\sqrt{\log n}))</math>.<ref>{{citation
 |last1 = Gabow|first1 = Harold N.|last2 = Nie|first2 = Shuxin|contribution = Finding long paths, cycles and circuits|doi = 10.1007/978-3-540-92182-0_66|location = Berlin|mr = 2539968|pages = 752–763|publisher = Springer|series = Lecture Notes in Computer Science|title = International Symposium on Algorithms and Computation|volume = 5369|year = 2008}}. For earlier work with even weaker approximation bounds, see {{citation
 |last = Gabow|first = Harold N.|doi = 10.1137/S0097539704445366|issue = 6|journal = SIAM Journal on Computing|mr = 2299418|pages = 1648–1671|title = Finding paths and cycles of superpolylogarithmic length|url = http://www.cs.colorado.edu/~hal/u.pdf|volume = 36|year = 2007}} and {{citation
 |last1 = Björklund|first1 = Andreas|last2 = Husfeldt|first2 = Thore|doi = 10.1137/S0097539702416761|issue = 6|journal = [[SIAM Journal on Computing]]|mr = 2034242|pages = 1395–1402|title = Finding a path of superlogarithmic length|volume = 32|year = 2003}}.</ref> Para todo<math>\epsilon>0</math>, não é possível aproximar o caminho mais longo para dentro de um fator de <math>2^{(\log n)^{1-\epsilon}}</math> a menos que NP esteja contido dentro de quasi-tempo polinomial determinístico; no entanto, há uma grande diferença entre este resultado contável e os algoritmos de aproximação conhecidos para este problema.<ref>{{citation
 |last1 = Karger|first1 = David|author1-link = David Karger|last2 = Motwani|first2 = Rajeev|author2-link = Rajeev Motwani|last3 = Ramkumar|first3 = G. D. S.|doi = 10.1007/BF02523689|issue = 1|journal = [[Algorithmica]]|mr = 1432030|pages = 82–98|title = On approximating the longest path in a graph|volume = 18|year = 1997}}.</ref>

No caso de gráficos não ponderados, mas dirigidos, fortes resultados contáveis são conhecidos. Para cada <math>\epsilon>0</math> o problema não pode ser aproximado dentro de um fator de <math>n^{1-\epsilon}</math> a menos que P = NP, e com pressupostas complexidade teórica mais fortes que não pode ser aproximado dentro de um fator de <math>n/\log^{2+\epsilon} n</math>.<ref name=":1" /> A técnica de codificação de cor pode ser usada para encontrar caminhos de comprimentos logarítmicos, se é que existem, mas o que dá uma relação de aproximação de apenas <math>O(n/\log n)</math>.<ref name=":2">{{citation
 |last1 = Alon|first1 = Noga|author1-link = Noga Alon|last2 = Yuster|first2 = Raphael|last3 = Zwick|first3 = Uri|doi = 10.1145/210332.210337|issue = 4|journal = [[Journal of the ACM]]|mr = 1411787|pages = 844–856|title = Color-coding|volume = 42|year = 1995}}.</ref>

== Complexidade parametrizada ==
O problema do caminho mais longo é [[Complexidade parametrizada|parâmetro-fixo tratável]] quando parametrizado pelo comprimento do caminho. Por exemplo, ele pode ser resolvido no tempo linear no tamanho do grafo de entrada (mas exponencial do comprimento do percurso), por um algoritmo que realiza as seguintes etapas:
# Realize uma [[busca em profundidade]] do grafo. Seja <math>d</math>  a profundidade da árvore de busca em profundidade resultante.
# Use a sequência de caminho raiz-a-folha da árvore de busca em profundidade, na ordem em que foram atravessados pela pesquisa, para a construção de uma decomposição do caminho do gráfico, com largura de caminho <math>d</math>. 
# Aplicar [[programação dinâmica]] a esta decomposição de caminho para encontrar um caminho mais longo no tempo <math>O(d!2^dn)</math>, onde <math>n</math> é o número de vértices do grafo.
Uma vez que a passagem de saída tem um comprimento pelo menos tão grande como <math>d</math>, o tempo de execução também é delimitada por <math>O(\ell!2^\ell n)</math>, onde <math>\ell</math> é o comprimento do caminho mais longo.<ref>{{citation
 |last = Bodlaender|first = Hans L.|authorlink = Hans L. Bodlaender|doi = 10.1006/jagm.1993.1001|issue = 1|journal = Journal of Algorithms|mr = 1199244|pages = 1–23|title = On linear time minor tests with depth-first search|volume = 14|year = 1993}}. For an earlier FPT algorithm with slightly better dependence on the path length, but worse dependence on the size of the graph, see {{citation
 |last = Monien|first = B.|contribution = How to find long paths efficiently|doi = 10.1016/S0304-0208(08)73110-4|location = Amsterdam|mr = 808004|pages = 239–254|publisher = North-Holland|series = North-Holland Math. Stud.|title = Analysis and design of algorithms for combinatorial problems (Udine, 1982)|volume = 109|year = 1985}}.</ref> Utilizando um código de cores, a dependência do comprimento do percurso pode ser reduzida para exponencial isoladamente.<ref name=":2" /><ref>{{citation
 |last1 = Chen|first1 = Jianer|last2 = Lu|first2 = Songjian|last3 = Sze|first3 = Sing-Hoi|last4 = Zhang|first4 = Fenghui|contribution = Improved algorithms for path, matching, and packing problems|pages = 298–307|title = Proc. 18th ACM-SIAM Symposium on Discrete algorithms (SODA '07)|url = http://faculty.cse.tamu.edu/shsze/papers/kpath.pdf|year = 2007}}.</ref><ref>{{citation
 |last = Koutis|first = Ioannis|contribution = Faster algebraic algorithms for path and packing problems|url = http://ccom.uprrp.edu/~ikoutis/papers/MultilinearDetection.pdf|doi = 10.1007/978-3-540-70575-8_47|location = Berlin|mr = 2500302|pages = 575–586|publisher = Springer|series = Lecture Notes in Computer Science|title = International Colloquium on Automata, Languages and Programming|volume = 5125|year = 2008}}.</ref><ref>{{citation
 |last = Williams|first = Ryan|authorlink = Ryan Williams (computer scientist)|arxiv = 0807.3026|doi = 10.1016/j.ipl.2008.11.004|issue = 6|journal = Information Processing Letters|mr = 2493730|pages = 315–318|title = Finding paths of length ''k'' in ''O''*(2<sup>''k''</sup>) time|volume = 109|year = 2009}}.</ref> A técnica de programação dinâmica similar mostra que o problema do caminho mais longo também é parâmetro – fixo tratável quando parametrizado pelo terceiro caminho do grafo.

Para os grafos de largura camarilha limitada, o caminho mais longo também pode ser resolvido através de um algoritmo de programação dinâmica em tempo polinomial. No entanto, o expoente do polinômio depende da camarilha de largura do grafo, por isso este algoritmo não é parâmetro – fixo tratável. O problema do caminho mais longo, parametrizado por camarilha de largura, é difícil para a classe de [[complexidade parametrizada]] <math>W[1]</math> mostrando que um algoritmo de parâmetro – fixo tratável é improvável de existir.<ref>
{{citation|last1 = Fomin|first1 = Fedor V.|last2 = Golovach|first2 = Petr A.|last3 = Lokshtanov|first3 = Daniel|last4 = Saurabh|first4 = Saket|contribution = Clique-width: on the price of generality|pages = 825–834|title = Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09)|url = https://www.siam.org/proceedings/soda/2009/SODA09_090_fominf.pdf|year = 2009|access-date = 2015-11-30|archiveurl = https://web.archive.org/web/20121018164522/http://siam.org/proceedings/soda/2009/SODA09_090_fominf.pdf}}.
</ref>

== Classes especiais de grafos ==
O problema do caminho mais longo pode ser resolvido em tempo polinomial sobre os [[Grafo complementar|complementos]] de grafos de comparabilidade.<ref>{{citation
 |last1 = Ioannidou|first1 = Kyriaki|last2 = Nikolopoulos|first2 = Stavros D.|doi = 10.1007/s00453-011-9583-5|journal = Algorithmica|title = The longest path problem is polynomial on cocomparability graphs|url = http://www.cs.uoi.gr/~stavros/J-Papers/J-2012-ALGO.pdf|year = 2011}}.<!-- as of 2012-12-01, online at Algorithmica but not yet assigned a volume/issue/page numbers--> For earlier work on more restrictive subclasses of co-comparability graphs, see {{citation
 |last1 = Ioannidou|first1 = Kyriaki|last2 = Mertzios|first2 = George B.|last3 = Nikolopoulos|first3 = Stavros D.|doi = 10.1007/s00453-010-9411-3|issue = 2|journal = [[Algorithmica]]|mr = 2822187|pages = 320–341|title = The longest path problem has a polynomial solution on interval graphs|url = http://dro.dur.ac.uk/9047/1/9047.pdf|volume = 61|year = 2011}} and {{citation
 |last1 = Uehara|first1 = Ryuhei|last2 = Valiente|first2 = Gabriel|doi = 10.1016/j.ipl.2007.02.010|issue = 2|journal = Information Processing Letters|mr = 2322071|pages = 71–77|title = Linear structure of bipartite permutation graphs and the longest path problem|volume = 103|year = 2007}}.</ref> Ele também pode ser resolvido em tempo polinomial em qualquer classe de grafos com três larguras limitadas ou de largura pequena associação limitada, tais como os grafos de distância hereditária. No entanto, é NP-difícil, mesmo quando restrito a dividir gráficos, gráficos de círculo  ou grafos planares.<ref>{{harvtxt|Ioannidou|Mertzios|Nikolopoulos|2011}}.</ref>

{{referencias|col=2}}

== Ligação externa ==
* "[http://valis.cs.uiuc.edu/~sariel/misc/funny/longestpath.mp3 Find the Longest Path]", música de [[:en:Daniel_J._Barrett|Dan Barrett]]

[[Categoria:Algoritmos de grafos]]