İki düğüm arasındaki döngüsel bir grafikte en uzun yolu nasıl bulabilirim?

Question

Zaten here numaralı soruların çoğunu çözdüm, ancak en uzun yol olanı. Vikipedi makalesini en uzun yollarla okudum ve eğer grafik çevrimsel değilse, benimki kolay değil gibi görünüyor.

Sorunu nasıl çözerim o zaman? Tüm olası yolları kontrol ederek kaba kuvvet? Bunu yapmaya nasıl başlayabilirim?

~ 18000 ile bir Grafik üzerinde bir LOT alacağını biliyorum. Ama ben sadece bunu geliştirmek istiyorum, çünkü proje için gerekli ve ben sadece test edeceğim ve icra zamanının sadece bir veya iki olduğu küçük ölçekli bir grafikte eğitmene göstereceğim.

En azından tüm görevleri yerine getirdim ve çalıştığı bir kavram kanıtı var ancak döngüsel grafiklerde daha iyi bir yol yok. Ama tüm bu yolları kontrol etmeye başlamak için bir ipucu yok ...

Answer 1

Çözüm, kaba kuvvet uygulamaktır. Hızlandırmak için bazı optimizasyonlar yapabilirsiniz, bazıları önemsizdir, bazıları çok karmaşıktır. Masaüstü bilgisayarda 18 000 düğüm için yeterince hızlı çalışabileceğinden şüpheliyim ve nasıl bir fikrim olsa bile. Bununla birlikte bruteforce nasıl çalışır.

Not: Dijkstra ve diğer en kısa yol algoritmalarından herhangi biri, tam bir yanıtla ilgileniyorsanız, bu sorun için ÇALIŞMAZ. 1 - 2 (4), 1 - 3 (100), 2 - 3 (5), 3 - 5 (200), 3 - 4 (7), 4 - 5 (1000)

Let the root be 1. We call getLongestPath(1, 0); 
2 is marked as visited and getLongestPath(2, 4); is called 
D[2] = 0 < currSum = 4 so D[2] = 4. 
3 is marked as visited and getLongestPath(3, 4 + 5); is called 
D[3] = 0 < currSum = 9 so D[3] = 9. 
4 is marked as visited and getLongestPath(4, 9 + 7); is called 
D[4] = 0 < currSum = 16 so D[4] = 16. 
5 is marked as visited and getLongestPath(5, 16 + 1000); is called 
D[5] = 0 < currSum = 1016 so D[5] = 1016. 
getLongestPath(3, 1016 + 200); is called, but node 3 is marked as visited, so nothing happens. 
Node 5 has no more child nodes, so the function marks 5 as not visited and backtracks to 4. The backtracking will happen until node 1 is hit, which will end up setting D[3] = 100 and updating more nodes. 

İşte

o iteratif nasıl görüneceğini var (test edilmemiş, sadece temel bir fikirdir):

Start at a root node *root* 
Let D[i] = longest path from node *root* to node i. D[*root*] = 0, and the others are also 0. 

void getLongestPath(node, currSum) 
{ 
    if node is visited 
     return; 
    mark node as visited; 

    if D[node] < currSum 
     D[node] = currSum; 

    for each child i of node do 
     getLongestPath(i, currSum + EdgeWeight(i, node)); 

    mark node as not visited; 
} 

en bu grafik üzerinde elle baştan alalım

Let st be a stack, the rest remains unchanged; 
void getLongestPath(root) 
{ 
    st.push(pair(root, 0)); 

    while st is not empty 
    { 
     topStack = st.top(); 
     if topStack.node is visited 
      goto end; 
     mark topStack.node as visited; 

     if D[topStack.node] < topStack.sum 
      D[topStack.node = topStack.sum; 

     if topStack.node has a remaining child (*) 
      st.push(pair(nextchild of topStack.node, topStack.sum + edge cost of topStack.node - nextchild)) 

     end: 
     mark topStack.node as not visited 
     st.pop(); 
    } 
} 

(*) - Bu biraz sorun - her düğüm için bir sonraki çocuğa bir işaretçi tutmak zorundasınız, çünkü while döngüsünün farklı yinelemeleri arasında değişebilir ve hatta kendini sıfırlayabilirsiniz (işaretçiyi açtığınızda işaretçi kendini sıfırlar) e topStack.node düğümden ayrıldığından, sıfırladığınızdan emin olun). Bağlantılı listelerde bunu uygulamak en kolay yoldur, ancak int[] listelerini veya vector<int> listelerini kullanmalısınız, böylece işaretçiyi saklayabilmeniz ve rastgele erişebilmeniz için ihtiyacınız olacaktır. Örneğin, next[i] = next child of node i in its adjacency list'u koruyabilir ve buna göre güncelleyebilirsiniz. Bazı kenar durumlarınız olabilir ve farklı end: durumlarına gereksiniminiz olabilir: normal olarak, önceden ziyaret edilmiş bir düğümü ziyaret ettiğinizde gerçekleşen, bu durumda işaretçilerin sıfırlanması gerekmez. Bunu önlemek için yığında bir şey itmeye karar vermeden önce ziyaret edilen koşulu taşıyın.

Neden rahatsız olmadığınızı söylediğimi anladım?