1. óra
Címkék > Óra

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

Dominófedés