Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2011-2012‎ > ‎

3. óra

2011.10.03.

A mai feladat már úgy van méretezve, hogy nem közömbös sem az algoritmus hatékonysága, sem az implementáció részletei.

Feladat

Visszalépéses keresés ("backtrack")

A visszalépéses keresés egy gyakran használható algoritmus, ami lényegében az összes eset rendszerezett végignézését jelenti. Ha a keresést gráfbejárásként képzeljük el, akkor a backtrack a mélységi keresésnek felel meg. Az alábbiakban megadjuk a visszalépéses keresés kódját, lehetőleg általánosan megfogalmazva.

keres(állapot, eddigi_lépések)
    Ha állapot = cél
        akkor találat kezelése
        különben
            Ciklus minden lehetséges L lépésre:
                új_állapot := L alkalmazva állapotra
                keres(új_állapot, eddigi_lépések+{L})
            Ciklus vége
    Elágazás vége
Eljárás vége


A keresést a keres(kezdő_állapot, {}) hívással indíthatjuk.

Megjegyzések

  • A rekurzív hívásnál vagy érték szerinti paraméterátadást kell alkalmaznunk, tehát a rekurzió mélyebb szintjén nem változtatjuk meg a külső eljárás által használt állapotot. Ha mégis globális változóban akarjuk követni a keresést, akkor gondoskodnunk kell róla, hogy a rekurzió egy szintjéről visszatérve vissza tudjuk állítani az eljárás változóit.
  • Az eddigi_lépések paraméterre csak akkor van szükség, ha a találathoz vezető lépés-sorozatot is meg kell adnunk. Ha csak az érdekel minket, hogy elérhető-e a célállapot, vagy az, hogy melyik célállapot érhető el, akkor ez a paraméter elhagyható.