No więc ma ktoś pomysł jak to ugryźć. dokładnie chodzi o to by znaleźć taką drogę ( niekoniecznie najdłuższą ) by suma wag była największa. Oczywiście jak mamy N wierzchołków to musimy zapodać metodę dla N wierzchołków. Jakieś pomysły jak to ugryźć. Rekurencja oczywiście wysiada gdy dużo wierzchołków ma dużo połączeń :) Grafy miałem już dawno więc może jakieś algorytmy mi umknęły. Nie wiem, Dijkstra coś to da?
0
0
Chcesz poszukać najdroższej drogi przechodzącej przez wszystkie wierzchołki? A to nie jest po prostu komiwojażer? Z tą różnicą że komiwojażer to szukanie minimalnej drogi w pełnym grafie ważonym, a ty chcesz szukać maksymalnej w niekoniecznie pełnym, ale różnica niewielka, chyba ze masz na ten graf jakieś mocne ograniczenia.
0
To chyba nie jest takie trudne. Przyjmuję takie załozenia:
-idziemy z wierzchołka A do B.
-musimy po drodze odwiedzić wszystkie inne wierzchołki.
-możemy odwiedzać wielokrotnie te same wierzchołki.
Jeśli dobrze zrozumiełem zadanie to ja bym to zrobił tak:
if (w grafie istnieje ścieżka Eulera z punktu A do B)
{
if (graf zawiera cykle)
{
Wystarczy się zapętlić w jakimkolwiek cyklu i możemy osiągać dowolnie długie drogi.
}
else
{
Szukamy dowolnej drogi z A do B. Wszytkie i tak są takiej samej długości. //tak mi się przynajmniej wydaje;)
}
}
else
{
Wymagana droga nie istnieje w tym grafie.
}
0
Wielokrotnie nie możemy, jak już byliśmy w A to nie możemy do niego iść znowu. Graf skierowany. Hmm .. co tu jeszcze .. No musimy zapodać algorytm na wszystkich wierzchołkach bo nie wiemy który jest startowy, maksymalna droga wagowa to nie musi być najdłuższa ani najkrótsza.
0
Jeśli jeden wierzchołek musimy odwiedzić dokładnie raz (dobrze rozumiem?), to nawet znalezienie jakiejkolwiek drogi jest już problemem NP-zupełnym (ścieżka Hamiltona). Jeśli graf ma bardzo mało wierzchołków (max kilkanaście), to możesz spróbować testować wszystkie kombinacje wierzchołków po kolei i sprawdzać, która jest najlepsza. Jeśli graf ma więcej wierzchołków, to musisz szukać jakiś algorytmów aproksymacyjnych.
0
@_nowy_ czekaj, ale czy ja dobrze rozumiem:
Do każdego wierzchołka możemy wejść raz, ale nie musimy?
To tak czy siak mi wygląda na jakieś wariacje komiwojażera. Jesteś pewien ze dobrze zinterpretowałeś zadanie? A może masz tutaj jakiś heurystyczny algorytm zastosować?
0
Jeden wierzchołek możemy tylko raz odwiedzić, ale nie musimy, bo np. wychodząc z pkt. A ni jak nie dojdziemy do B.
0
Graf skierowany. - a cykliczny czy może acykliczny?
0
@nowy: Sprecyzuj dokładnie problem, bo póki co sprawiasz wrażenie jakbyś sam nie wiedział czego chcesz. Z tego co napisałeś wynika, że szukasz najcięższej ścieżki prostej w grafie prostym skierowanym. Jeśli jest acykiczny to można to rozwiązać w czasie liniowym wykorzystując sortowanie topologiczne. Jeśli nie jest to mamy problem, bo nie ma algorytmu wielomianowego. Tu masz wszystko napisane: http://en.wikipedia.org/wiki/Longest_path_problem
PS. Popraw ten błąd ortograficzny w tytule.