Hladovy algoritmus

ujec2
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 13. 2. 2006 13:35

Hladovy algoritmus

Příspěvek od ujec2 »

Zdar vsetci,
nemohol by niekto z vas postnut hladovy algoritmus pre vyhladavanie v grafe?
Napr. takato uloha:

Kód: Vybrat vše

Hladovým algoritmem sestrojte v daném grafu nezávislou množinu vrcholů, která nejde zvětšit přidáním vrcholu.
alebo s heuristikou:

Kód: Vybrat vše

Heuristickym hladovym algoritmem najdete nejake male vrcholove pokryti grafu, tj. takovou mnozinu P vrcholu, ze aspon jeden vrchol kazde hrany lezi v P. Graf je zadan ke kazdemu vrcholu seznamem sousedu.
Dikes, moc by ste mi pomohli aj s popisom principu.
Keby ste mali nejake priklady na assert atp.. Pomohlo by.
THX
Uživatelský avatar
nytram
Matfyz(ák|ačka) level II
Příspěvky: 68
Registrován: 4. 1. 2005 15:54
Typ studia: Informatika Bc.
Bydliště: da B-9'th floor
Kontaktovat uživatele:

Re: Hladovy algoritmus

Příspěvek od nytram »

Kód: Vybrat vše

Heuristickym hladovym algoritmem najdete nejake male vrcholove pokryti grafu, tj. takovou mnozinu P vrcholu, ze aspon jeden vrchol kazde hrany lezi v P. Graf je zadan ke kazdemu vrcholu seznamem sousedu.
Heuristika: do zoznamu_A si usporiadas vrcholy podla velkosti stupna.

Postupne odoberas vrcholy s najvacsim stupnom (a vkladas do zoznamu_B) a upravujes stupne ostatnych vrcholov v zozname_A, dokym ti v zozname_A neostanu vrcholy s nulovym stupnom,teda vrcholy bez hran.
V tom pripade je obsah zoznamu_A minimalnym vrcholovym pokrytim grafu.

Avsak najst minimalne vrcholove pokrytie grafu je NPC problem, teda toto je aprox. algoritmus. :)
Quod Erat Demonstrandum.
Odpovědět

Zpět na „2005“