Domaca uloha c.3

Moderátor: FeroG

<<

opteron1441

Príspevky: 2

Registrovaný: Uto Feb 17, 2009 4:54 pm

Poslať Pia Mar 20, 2009 3:00 pm

Domaca uloha c.3

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?
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Pia Mar 20, 2009 7:23 pm

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.
<<

johny

Príspevky: 132

Registrovaný: Pia Feb 22, 2008 6:37 pm

Bydlisko: Košice

Poslať Pia Mar 20, 2009 11:32 pm

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á.
E-mail/Jabber: jan[zavináč]jergus.eu
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Pia Mar 20, 2009 11:56 pm

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.

Späť na PAZ1b

Kto je on-line

Užívatelia prezerajúci fórum: Žiadny registrovaný užívateľ nie je prítomný a 2 hostia

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software.
Slovenský preklad.