Algorytm - wysokość drzewa rozpinającego

[Platyna]

Witam

 

Macie może jakiś pomysł jak znaleźć maksymalną wysokość drzewa rozpinającego? Czyli po prostu najdłuższą możliwą ścieżkę w danym drzewie.

Przykładowo dla takiego grafu wynik powinien być 4 (na przykład: od 6 do 7):

 

Próbowałem to zrobić przepuszczając graf przez dwa DFSy

Najpierw od dowolnego wierzchołka

Potem od wierzchołka który był najgłębiej idąc od tego pierwszego.

I największa głębokość na jaką się zapuści drugi DFS to rozwiązanie.

 

Rozwiązanie wydaje mi się że jest dobre jednak za wolne. Sprawdzarka wywala mi przekroczenie czasu.

 

Graf reprezentowałem jako tablicę par wierzchołków (tablica krawędzi).

W sumie trochę bez sensu ale wydawało mi się najlepsze, bo macierz sąsiedztwa nie może być bo maksymalna ilość wierzchołków to 500.000 czyli przy macierzy trza by było stworzyć 250.000.000.000 boolów (krawędzie bez wag) czyli stanowczo za dużo tak mi się wydaje...

 

Macie pomysł na lepsze rozwiązanie?

[Will]

Po pierwsze chodzi o wymyślenie rozwiązania samemu. Po drugie zależy jak bardzo przekraczasz czas. Jeśli nie wiele wystarczy optymalizacja. Zwykły gotowy algorytm przechodzenia po grafach to nie bardzo dobre rozwiązanie, pokombinuj coś bo na tym to właśnie polega. Taka wskazówka (wymyślona na szybko)na pewno słyszałeś o algorytmach wyszukiwania najkrótszej drogi choćby i Dijkstry a czemu akurat najkrótszej?

[Tymon]

Mam tylko jedno pytanie, dopuszczalne jest połączenie 4-3

?

Pewnie nie, ale dla pewności pytam. :)

 

EDIT

Dobra, na Twoim przykładzie + kilka dodatkowych punków napisałem coś takiego ( oczywiście PHP + GD ):

Z punktu 6

Z punktu 1

Z punktu 2

Zwraca drogę i długość drogi, a wybrać najdłuższą to nie problem.

Oczywiście można zrobić by przeleciał po wszystkich punktach lub tylko tych skrajnych.

 

Jest ok?

[Platyna]

Tymon, a zastanowiłeś się przez chwilę jaka będzie złożoność pamięciowa twojego rozwiązania?

Sprawdzanie wszystkich możliwych dróg? Bez żartów...

To jest po prostu wywołanie DFSa dla każdego punktu czyli nie ma szans by przeszło.

A 4 i 3 jak połączysz to to już nie będzie drzewo rozpinające.

 

Will:

Hmm... o Dijkstrze myślałem ale ten algorytm działa tylko dla wyszukiwania najkrótszych dróg do wszystkich wierzchołków i nie idzie go przerobić by szukał najdłuższych (próbowałem kiedyś przy innym zadaniu) jednak zapomniałem o fakcie że to jest drzewo rozpinające. Nie ma cykli więc do każdego prowadzi tylko jedna droga będąca tą najdłuższą i najkrótszą zarazem. Więc zamiast dwóch DFSów przepuściłem graf przez dwie Dijkstry (z kopcem jak kolejką priorytetową) ale wciąż mam przekroczenie czasu.

Nie jestem pewny ale wydaje mi się, że to tylko kwestia jakiejś optymalizacji.

Pogłówkuję trochę nad tym jeszcze.

[Tymon]

Nie wiem po co Ci to tak czy inaczej przy kilku MB pamięci bym się martwił, przy kilku GB nie widzę sensu tym bardziej, że nie wspominałeś o ograniczeniach. No nie do końca robię tak jak myślisz, pojedyncze odcinki bez rozgałęzień traktuję jako całość ( 2-3-7-8-9-10 czy 2-3-7 u Ciebie ) i korzystam tylko z ich długości, to już oszczędność.

 

Algorytm Dijkstry da się przerobić tak by wybierał najdłuższą drogę. Wybieraj wierzchołek w największej odległości.

[Platyna]

Ach sory miałem na myśli złożoność czasową a nie pamięciową. "Przejęzyczenie" :P

 

I nie skumałem na początku do końca co masz na myśli.

[Tymon]

A, no to rzeczywiście napisałem niepotrzebnie. :P

Masz jakiś konkretny limit?

[Platyna]

Mam konkretny limit ale nie jest mi znany.

 

To zadanko z kółka przygotowującego do OI.

Kombinuje nad tym od jakiegoś czasu a przeróżne sposoby i nie mogę.

 

Może kolejkę priorytetową w Dijkstrze trza zrobić kopcem Fibonacciego (czy jak mu tam) a nie zwykłym ale nie mogę jakoś ogarnąć tego, ani w necie dobrego artykułu o tym znaleźć.

A może w ogóle moje rozwiązanie jest nie takie jak trzeba i idzie to zrobić przepuszczając graf przez Dijkstrę tylko raz...

Nie wiem... :/

[Will]

kopce fibonacciego były bodajże w Cormenie rozdział gdzieś 20-21.A może najpierw wyliczyć ilość przejść pomiędzy większymi węzłami a następnie po odrzuceniu tych najgorszych liczyć już tradycyjną metodą?tzn stworzyć coś w stylu subtree z jakąś ustaloną głębokością.

[Platyna]

Algorytm Dijkstry da się przerobić tak by wybierał najdłuższą drogę. Wybieraj wierzchołek w największej odległości.

Tak? Nie wydaje mi się.

Chociażby dla takiego prostego grafu:

 

1->3 = 3

1->2 = 5

3->2 = 4

3->5 = 6

2->5 = 3

5->4 = 7

 

Jadąc od wierzchołka 1:

Ustawi:

1: 0

3: 3

2: 5

 

2 jest najdalej więc jego zaznaczy

Ustawi:

5: 8

 

5 jest najdalej

4: 15

 

3 zostało na koniec:

2: 7

5: 9

 

Jak widzimy źle zadziała bo odległość wierzchołka 4 ustawi dla piątki wyliczonej z dwójki podczas gdy dalej by było od trójki.

Jak niby może Dijkstre poprawić by wyliczał największe odległości?

Poza tym dla grafu nieskierowanego będą sytuacje że od jedynki ustawimy odległość dwójki po czym od dwójki odległość jedynki. Chociaż akurat temu łatwiej zapobiec.

 

 

EDIT:

Ech Will, podrzuciłeś mi mylny trop.

Co to za pomysł żeby robić Dijkstrą. DFS ma mniejszą złożoność czasową nawet jeśli przy dijkstrze kopca używam.

 

Wszystko miałem dobrze tylko po prostu źle graf reprezentowałem. Tak niewydajnie :P