1. óra
(Erben Péter, 2006.09.18.)
Bemelegítés
Első alkalommal a "nyers erő" (brute force) módszerét elevenítjük fel / tanuljuk meg.
A módszer lényege, hogy ha nincs jobb ötletünk, akkor megpróbáljuk (szisztematikusan) végigpróbálni az összes lehetséges esetet. Ez általában exponenciális algoritmushoz vezet (ami nem jó), de néha nincs jobb.
Az összes eset végigpróbálásának egyik gyakori módja a visszalépéses keresés (backtrack). Ennek egy rekurzív és egy nem rekurzív változatát is megadjuk.
Visszalépéses keresés rekurzióval
A következő algoritmus váz abban az esetben használható, ha tudjuk, hogy van legalább egy megoldás, és elég az első megoldást megtalálnunk. Szépséghibája, hogy a megoldás megtalálásakor a rekurzió "legmélyén" vagyunk, és ekkor meg kell szakítanunk a rekurzió futását, hogy a megtalált megoldást ne "bontsák le" a visszalépések.
rek_backtrack:
Ha nincs kész
akkor
Ciklus a lehetséges lépéseken
megcsinál( lehetségesLépés )
rek_backtrack
visszacsinál( lehetséges lépés)
Ciklus vége
különben
megoldás feldolgozása
keresés vége
Elágazás vége
Visszalépéses keresés ciklussal
A rekurzió kiküszöbölhető, ha a valamilyen adatszerkezetben tároljuk eddigi döntéseinket.
A döntés[i] tömbeleme azt tárolja, hogy az i. lépésben "merre mentünk".
A vanjóeset() függvény egyesével végigpróbálja a lehetséges döntéseket, és ha igaz értékkel tér vissza, akkor be is állítja a döntés[i] értéket.
cikl_backtrack:
döntés[1..n] := 0; i := 1
Ciklus amíg i > 0 és i < N + 1
Ha vanjóeset(i)
akkor
i := i + 1
különben
visszacsinál( i )
i := i - 1
Elágazás vége
Ciklus vége
VAN := (i > N)
Feladat
