[segfault]

Ktoś potrafi rozwiązać szybciej niż w O(2^n*n^2)?
Dany jest DAG. Znajdź dwie ścieżki o największej sumie długości, zaczynające się w tym samym wierzchołku i nieposiadające poza nim żadnych innych wspólnych wierzchołków.
#algorytmy #naukaprogramowania

[wytrzzeszcz]

@segfault: a jaka zlozinosc ma A* do najkrotszej drogi?
nastepnie usun ta droge i policz kolejna

[wytrzzeszcz]

@segfault: co to DAG?

[segfault]

@wytrzzeszcz: acykliczny graf skierowany

[segfault]

@wytrzzeszcz: ale najdłuższa i najdłuższa w pozostałych wierzchołkach nie muszą być w sumie najdłuższe. tzn. może istnieć taka ścieżka która jest trochę krótsza od najdłuższej, ale pozwala zbudować znacznie dłuższą drugą ścieżkę niż ta najdłuższa i suma wychodzi lepsza.

[wytrzzeszcz]

@segfault: usun wieszcholki stopnia 1 i0 nastepnie idz przeciwnie do tego co mowi graf "w gore rzeki" to beda kandydaci i z nich idz w dol rzeki sumujac po drodze

[wytrzzeszcz]

@segfault: bo acykliczny to drzewo moze to jest protip

[segfault]

@wytrzzeszcz: ale to dalej jest wykładnicze, bo możliwych ścieżek "w górę" jest rzędu 2^n

[wytrzzeszcz]

@segfault: a jak szybko znalezc korzen to ogolnie logn

[wytrzzeszcz]

@segfault: #!$%@? st1 i st0

[wytrzzeszcz]

@segfault: i idz z dowolnego do gory bo jest jeden tylko korzen

[segfault]

@wytrzzeszcz: problem w tym mogę pójść do korzenia na O(2^n) różnych sposobów. Weź sobie na przykład taki graf złożony z n/2 warstw po dwa wierzchołki w warstwie, oba połączone z obydwoma z warstwy następnej. Na każdej warstwie wybierasz niezależnie którym wierzchołkiem pójdziesz w górę, czyli podejmujesz n/2 niezależnych decyzji co daje 2^(n/2) możliwych kombinacji.

[wytrzzeszcz]

@segfault: i z korzenia do kazdego liscia idz to juz n

[lol_nope]

@wytrzzeszcz: dag nie musi byc drzewem - moze miec wiecej niz 1 "korzen"

[wytrzzeszcz]

@lol_nope: tez tak patrze, a to nie dobrze