Visszalépéses keresés

A visszalépéses keresés (angolul: backtracking) egy általános algoritmus bizonyos számítási problémák, különösen a korlátkielégítési probléma (más néven kényszerkielégítési probléma) összes (vagy legalább néhány) megoldásának megtalálására. Az algoritmus fokozatosan felépíti a megoldás útját (részmegoldások), és elhagyja azokat az útvonalakat ("visszalépések"), amelyekről megállapítja, hogy nem adnak érvényes megoldást.^[1] ^[2]

A klasszikus tankönyvi példája a visszalépés algoritmus használatára a nyolckirálynő-probléma, amely lényege, hogy hogyan illetve hányféleképpen lehet 8 királynőt (vezért) úgy elhelyezni egy klasszikus sakktáblán, hogy azok ne üssék egymást. Az általános megközelítésben részmegoldások olyan elrendezések, ahol k számú királynőt a tábla első k sorába helyezünk úgy, hogy mindegyik királynő különböző sorba és oszlopba kerüljön. Bármely olyan részmegoldás, amely két egymást ütő királynőt tartalmaz, elhagyható.

A visszalépést csak olyan problémákra lehet alkalmazni, amelyek elfogadják a „részmegoldás” fogalmát, és viszonylag gyorsan ellenőrizhető, hogy létezik-e valós megoldása. Nincs előnye olyan esetekben, amikor egy adott értéket kell kikeresni egy rendezetlen táblázatban. Ugyanakkor, a visszalépéses keresés gyakran sokkal gyorsabb, mint az összes részmegoldásra alkalmazott kimerítő keresés (brute-force keresés), mivel egyetlen vizsgálattal sok részmegoldást ki tud zárni.

A visszalépéses keresés egy hatékony eszköz az olyan korlátkielégítési problémák^[3] megoldásában, mint a keresztrejtvények, alfametika, Szúdoku és számos egyéb feladvány. Ez sokszor a legkönnyebben alkalmazható (ha nem is a leghatékonyabb) eljárás az elemzésre, ^[4] a hátizsák problémára és más kombinatorikus optimalizálási problémák megoldására. Ez az alapja az úgynevezett logikai programozási nyelveknek is, mint például az Icon, a Planner és a Prolog.

A visszalépéses keresés a felhasználó által megadott „fekete doboz” eljárásokon alapszik, amelyek meghatározzák a megoldandó problémát, a részmegoldások jellegét és azt, hogy milyen módon válnak a részmegoldások teljes megoldásokká. Ezért inkább metaheurisztikus módszer, mint konkrét algoritmus - bár sok más metaheurisztikus módszerrel ellentétben garantált, hogy egy véges probléma összes megoldását korlátozott időn belül megtalálja.

Az angol "backtrack" kifejezést az 1950-es években D. H. Lehmer amerikai matematikus alkotta meg.^[5] Az akkor úttörő sztringkezelő nyelv, a SNOBOL (1962) volt valószínűleg az első, ami beépített, általános visszalépéses keresési lehetőséget nyújtott.

A módszer leírása

A visszalépés algoritmusa megadja a részmegoldások halmazát, amelyeket különféle módokon lehet kiegészíteni, hogy az adott problémára minden lehetséges megoldást meg lehessen adni. A megoldás fokozatosan történik, a részmegoldás lépésenkénti kiterjesztésének sorozatával.

Az elmélet alapján a részmegoldásokat egy faszerkezet csomópontjaiként, potenciális keresési faként ábrázolja. Minden részmegoldás leszármaztatható egy korábbi részmegoldásból (szülő), melytől csupán egy kiterjesztési lépéssel különbözik; azon részmegoldások, amiket nem lehet tovább származtatni alkotják a fa leveleit.

A visszalépéses keresés a keresési fát rekurzív módon járja be a gyökértől lefelé, a mélységi keresés sorrendjében. Minden egyes c csomópontban az algoritmus ellenőrzi, hogy c teljes megoldás lehet-e. Ha nem, akkor a c-ben gyökerező teljes részfa kihagyásra kerül. Egyébként az algoritmus ellenőrzi, hogy (1) c önmagában valós megoldás-e, és ha igen, jelentést tesz a felhasználónak; és (2) rekurzívan megadja a c összes részfáját. A két vizsgálatot és az egyes csomópontok gyermekeit a felhasználó által megadott eljárások határozzák meg.

Ezért az aktuális keresési fa, amelyet az algoritmus bejár, csak a potenciális fa részfája. Az algoritmus teljes költsége az aktuális fa csomópontjainak száma és az egyes csomópontok elérésének és feldolgozásának költségének szorzata. Ezt a tényt figyelembe kell venni a potenciális keresési fa kiválasztásakor és a metszésteszt végrehajtásakor.

Pszeudokód

Annak érdekében, hogy alkalmazható legyen a visszalépéses keresés egy adott problémaosztályra, meg kell adni a P adatot a megoldandó probléma adott példányára, amihez hat paraméteres függvényt kell megadni: gyökér, elutasítás, elfogadás, első, következő és kimenet. Ezeknek az eljárásoknak a P példány adatait kell paraméterként átadni, és az alábbiak szerint kell eljárniuk:

gyökér(P): visszatér fa gyökeréhez tartozó részmegoldással.
elutasít(P, c): igaz akkor, ha a c részmegoldást nem érdemes bejárni.
elfogad(P, c): igaz, ha c a P megoldása, egyébként hamis
első(P, c): létrehozza a c részmegoldás első kiterjesztését (leszármazottját).
következő(P, s): létrehozza c részmegoldás s után következő lehetséges kiterjesztését.
kimenet(P, c): alkalmazza c megoldását P-re, az alkalmazásnak megfelelően.

A visszalépéses keresési algoritmus lecsökkenti a megoldás keresését a vk(gyökér (P)) függvényhívásra, ahol vk a következő rekurzív eljárás:

 eljárás vk(c)
  ha elutasít(P, c), akkor térjen vissza
  ha elfogad(P, c), akkor kimenet(P, c)
  s ← első(P, c)
  amíg s ≠ NULL
    vk(s)
    s ← következő(P, s)

Használati szempontok

Az elutasít függvénynek logikai értékű függvénynek kell lennie, amely csak akkor tér vissza igazzal, ha biztos, hogy a c lehetséges kiterjesztése nem ad teljes megoldást a P-re vonatkozóan. Ha az eljárás nem hozott egyértelmű következtetést, akkor hamissal tér vissza. Fals igaz visszatérési érték miatt az eljárás kihagyhat néhány teljes megoldást. Az eljárás feltételezi, hogy az elutasít(P, t) hamis értékkel tér vissza minden t-re, amely őse c-nek a keresési fában.

Másrészt, a visszalépéses keresés algoritmus hatékonysága függ attól, hogy a részmegoldások elutasít eljárása a gyökérhez a lehető legközelebb térjenek vissza igaz értékkel. Ha az elutasít mindig hamissal tér vissza, az algoritmus továbbra is végigjárja az összes megoldást, ami egyenértékű a kimerítő kereséssel.

Az elfogad függvény igaz értéket ad vissza, ha c teljes és valós megoldása a probléma P példányának, minden más esetben hamis a visszatérési érték. Ilyenkor feltételezhetjük, hogy a c részmegoldás és az ősei a fában az elutasít függvényhívásra hamis értékkel tértek vissza.

A fenti általános pszeudokód nem feltételezi, hogy az érvényes megoldások minden estben levelek a keresési fában. Más szavakkal, elismeri annak a lehetőségét, hogy egy érvényes P megoldást tovább lehet bővíteni más érvényes megoldások előállítása céljából.

Az első és a következő függvényeket az algoritmus a fa c csomópontjának utódjainak meghatározására használja, azaz azokat a részmegoldásokat határozza meg, amelyek egyetlen kiterjesztési lépéssel különböznek a c- től. Az első(P, c) függvény c első utódját adja vissza valamely irányban; a következő(P, s) függvény pedig visszaadja az s csomópont következő testvérét, az előbbivel megegyező irányban. Mindkét funkció "NULL" megkülönböztetett értékkel tér vissza, ha a keresett utódok nem léteznek.

A gyökér, az első és a következő függvények együttesen határozzák meg a részmegoldások halmazát és a potenciális keresési fát. Olyan módon kell ezeket megválasztani, hogy P minden megoldása a fában fellelhető legyen, és egyetlen részmegoldás se forduljon elő egynél többször. Ezen felül, egy hatékony és eredményes elutasít predikátumot is szükséges definiálni.

Korai megállásos variációk

A fenti pszeudokód meghívja a kimenetet minden megoldást esetében, ami érvényes az adott P példányra. Az algoritmus módosítható úgy, hogy megálljon az első vagy meghatározott számú megoldás megtalálása után; meghatározott számú részmegoldás vizsgálata után, meghatározott CPU idő eltelte után.

Példák

Példák, amelyekben a visszalépéses keresés rejtvények vagy problémák megoldására használható:

Rejtvények, például nyolckirálynő-probléma, keresztrejtvények, alfametika, Sudoku és Peg pasziánsz.
Kombinatorikai optimalizálási problémák, például elemzés és hátizsákprobléma.
Az olyan logikai programozási nyelvek, mint például az Icon, a Planner és a Prolog, amelyek visszalépéses keresést használnak a válaszok generálására.

Az alábbiakban bemutatunk egy példát, ahol a visszalépéses keresést alkalmazzuk a korlátkielégítési probléma megoldására:

Korlátkielégítési probléma

Az általános korlátkielégítési probléma azon egész számok listájának megtalálása x = (x[1], x[2], …, x[n]) , ahol x[n] ∈ {1, 2, …, m } , amelyek kielégítik tetszőleges F (logikai függvény) kényszert.

A problémák ezen osztályánál a P példányadatok m és n egész számok, és F a predikátum. A probléma tipikus visszalépéses megoldásában egy részmegoldást definiálunk, egész számok listájaként c = (c[1], c[2], …, c[k]) , ahol k értéke 0 és n közötti, amelyekhez kell hozzárendelni az x[1], x[2], …, x[k] -kat. A gyökér esetében ez üres lista () lenne. Az első és a következő függvény a következő:

 függvény első(P, c)
  k ← hossz(c)
  ha k = n, akkor
    vissza NULL
  egyébként
    vissza (c[1], c[2],…, c[k], 1)

 funkció a következő(P, s)
  k ← hossz(s)
  ha s[k] = m, akkor
    vissza NULL
  egyébként
    vissza (s[1], s[2],…, s[k - 1], 1 + s[k])

Ahol a hossz(c) a c lista elemeinek a száma.

Az elutasít(P, c) igaz értékkel tér vissza, ha a F kényszert nem lehet kielégíteni bármely n egész szám listájával, ami c k-adik elemével kezdődik. Ahhoz, hogy a visszalépés hatékonyan működjön, az elutasít függvénynek legalább néhány c részmegoldásra igazzal kellene visszatérnie, hogy az algoritmus ne menjen végig az összes m ^{n - k} n hosszúságú sorozaton.

Például, ha F több logikai predikátum konjunkciója, F = F[1] ∧ F[2] ∧ … ∧ F[p], és minden F[i] csak a változók kis részhalmazától függ x[1], …, x[n], akkor az elutasítás függvény egyszerűen ellenőrizheti az F[i] kifejezéseket, amelyek csak az x[1], …, x[k] változóktól függnek, és igazzal tér vissza, ha a kifejezések valamelyike hamis. Valójában a elutasítás függvénynek csak azokat a kifejezéseket kell ellenőriznie, amelyek ténylegesen az x[k] -tól függnek, mivel azokat a kifejezéseket, amelyek az x[1], …, x[k − 1]-től függnek, a későbbiekben vizsgálja a bejárás során.

Feltételezve, hogy az elutasít függvényt a fentiek szerint hajtjuk végre, akkor az elfogad(P, c) függvénynek csak azt kell ellenőrizni, hogy c teljes-e, vagyis n eleme van-e.

Általánosan jobb megoldás a változók listáját úgy rendezni, hogy azok a legkritikusabbakkal kezdődjenek (azaz azokkal, amelyek a legkevesebb értékopciókkal rendelkeznek, vagy amelyek nagyobb hatással vannak a további választásokra).

Megengedhető az is, hogy a következő függvény kiválassza, hogy melyik változót hívja meg a részmegoldás kiterjesztésekor, az általa már korábban meghívott változók értékei alapján. További javulások érhetők el lokális következetesség alkalmazásakor.

Minimális helyreállítási értékek megőrzésén túl az implementációk nyomon követik és megőrzik a változókban végbement változásokat. Hatékonyabb megoldás, amikor ha nincs választási pont, az algoritmus nem hoz létre nyomon követési pontot, és az algoritmus az összes változást egyetlen műveletben törli.

A változók nyomon követésének egy alternatívája, amikor az utolsó változtatás időbélyegzőjét mentjük el. Ezt az időbélyeget hasonlítja össze a választási pont időbélyegével. Ha a választási ponthoz társított időbélyeg későbbi, mint a változóé, akkor a változót nem kell visszaállítani, a választási pontról történő visszalépéskor, mivel az a választás előtt változott meg.

Jegyzetek

↑ Donald E. Knuth. The Art of Computer Programming. Addison-Wesley (1968)
↑ Gurari: CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms, 1999. [2007. március 17-i dátummal az eredetiből archiválva].
↑ A. Biere. Handbook of Satisfiability. IOS Press (2009. január 29.). ISBN 978-1-60750-376-7
↑ Des Watson. A Practical Approach to Compiler Construction. Springer (2017. március 22.). ISBN 978-3-319-52789-5
↑ Rossi, Francesca. Constraint Satisfaction: An Emerging Paradigm, Handbook of Constraint Programming, Foundations of Artificial Intelligence. Amsterdam: Elsevier, 14. o. (2006. augusztus 1.). ISBN 978-0-444-52726-4. Hozzáférés ideje: 2008. december 30. „Bitner and Reingold credit Lehmer with first using the term 'backtrack' in the 1950s.”

Irodalom

Gilles Brassard, Paul Bratley. Fundamentals of Algorithmics. Prentice-Hall (1995)

Fordítás

Ez a szócikk részben vagy egészben a Backtracking című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

HBmeyer.de, egy backtracking algoritmus interaktív animációja
Solving Combinatorial Problems with STL and Backtracking cikk C++ forráskódokkal a backtracking általános megvalósításához

[1] Donald E. Knuth. The Art of Computer Programming. Addison-Wesley (1968)

[2] Gurari: CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms, 1999. [2007. március 17-i dátummal az eredetiből archiválva].

[BiereHeule2009-3] A. Biere. Handbook of Satisfiability. IOS Press (2009. január 29.). ISBN 978-1-60750-376-7

[Watson2017-4] Des Watson. A Practical Approach to Compiler Construction. Springer (2017. március 22.). ISBN 978-3-319-52789-5

[5] Rossi, Francesca. Constraint Satisfaction: An Emerging Paradigm, Handbook of Constraint Programming, Foundations of Artificial Intelligence. Amsterdam: Elsevier, 14. o. (2006. augusztus 1.). ISBN 978-0-444-52726-4. Hozzáférés ideje: 2008. december 30. „Bitner and Reingold credit Lehmer with first using the term 'backtrack' in the 1950s.”

[1]

[2]

[3]

[4]

[5]