| dbo:abstract
|
- A visszalépéses keresés (angolul: backtracking) egy általános algoritmus bizonyos , különösen a (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. 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 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, 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. 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. (hu)
- A visszalépéses keresés (angolul: backtracking) egy általános algoritmus bizonyos , különösen a (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. 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 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, 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. 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. (hu)
|
