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. FeladatVisszalé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ó.
|