14. óra
(Erben Péter, 2008. 01. 07.)
gráfalgoritmusok 4. - Mélységi és szélességi bejárás
Egy játék lehetséges állapotait és lépéseit gráffal ábrázolhatjuk.
Az állapotok a csúcsok, a lépések az (irányított) élek. Egyszemélyes játékok (pl 15-ös kirakós) esetén a játék állapotgráfján egy utat keresünk a kezdőállapotból valamelyik célállapotba.
A keresés legegyszerűbb módja a bejárás.
A keresés legegyszerűbb módja a bejárás.
Bejárások
- Mélységi bejárás
Ez közismertebb nevén a visszalépéses keresés. Ha egy csúcsból tovább tudunk lépni, akkor megyünk, ha elakadtunk, akkor visszalépünk addig a csúcsig, ahonnan másfele is lehet menni, és új lépést választunk ott. Megvalósítható rekurzióval, vagy tárolhatjuk az eddigi döntéseket egy globális tömbben. - Szélességi bejárás
Egy csúcsból az összes rákövetkezőt "meglátogatjuk" és egy sor adatszerkezetben tároljuk. Amíg a sor nem üres, kivesszük a legrégebben berakott csúcsot, és végiglátogatjuk az eddig még nem látott rákövetkezőit.