Stránka 1 z 1

Domaca uloha c.3

PoslaťNapísal: Pia Mar 20, 2009 3:00 pm
od opteron1441
Chcem sa opytat pri ulohe Total TopSort, mozem pouzit metodu na generovanie permutacii a nasledne overovanie ci ide o Topologicke usporiadanie? Lebo ked som nad tym rozmyslal tak BackTrack najde len jedno riesenie, ci nie?

PoslaťNapísal: Pia Mar 20, 2009 7:23 pm
od FeroG
Ak chces na Total TopSort pouzit generovanie permutacii kombinovane s testovanim, tak mozes. Cielom je napisat program, ktory splna zadanie. Ako, to uz je na riesitelovi. Ale bolo by lepsie, ak by ste sa zamysleli aj nad "efektivnejsimi" pristupmi.

BackTrack je nejake systematicke prehladavanie priestoru rieseni (do hlbky), pricom sa ocakava, ze nebude prilis navstevovat tie casti priestoru, ktore nevedu k rieseniu. Ak teda v BackTracku nedas podmienku, aby skoncil ked uz mas garantovane riesenie, tak bude v hladani pokracovat a najde vsetky riesenia.

Pri ulohe Totalny TopSort jeden z pristupov moze byt tento: Najprv si vytvorim mnozinu vsetkych vrcholov, ktore mozu byt na prvom mieste v topologickom usporiadani. Potom pre kazdy z vrcholov tejto mnoziny spravim nasledovne: dam ho na prve miesto postupnosti, "odstranim" ho docasne z grafu, skusim pre zvysok grafu dogenerovat vsetky topologicke usporiadania, "vratim" docasne odstraneny vrchol naspat do grafu.

PoslaťNapísal: Pia Mar 20, 2009 11:32 pm
od johny
FeroG píše:Ale bolo by lepsie, ak by ste sa zamysleli aj nad "efektivnejsimi" pristupmi.

Vygenerovať všetky topologické utriedenia grafu sa lepšie ako v O(N!) nedá.

PoslaťNapísal: Pia Mar 20, 2009 11:56 pm
od FeroG
johny píše:
FeroG píše:Ale bolo by lepsie, ak by ste sa zamysleli aj nad "efektivnejsimi" pristupmi.

Vygenerovať všetky topologické utriedenia grafu sa lepšie ako v O(N!) nedá.


Dakujem za komentar. Som rad, ze odbornym okom dohliadas na obsah tohto fora.

Samozrejme z worst-case (najhorsi pripad) pohladu je Omega(N!) dolna hranica. Staci si zobrat N-vrcholovy graf bez hran. V takomto grafe kazde usporiadanie vrcholov je topologickym usporiadanim. A pocet vsetkych usporiadani je N!. To len na doplnenie pre dalsich citatelov fora ...

Na druhej strane, graf kde hrany vytvaraju orientovanu cestu ma len jedno topologicke usporiadanie. Teda od hran v grafe velmi zavisi pocet vsetkych moznych topologickych usporiadani.

Pod pojmom "efektivnejsi" som myslel nieco, coho casova zlozitost je akosi proporcionalna k poctu vsetkych topologickych usporiadani daneho vstupneho grafu. Totiz strategia najprv nagenerovat vsetky permutacie, ktorych je N!, a potom z nich niektore zahodit nikdy pod O(N!) nepojde, ani ked ma graf na vstupe len jedno topologicke usporiadanie.