Visszalépés keresés , a visszalépés egy általános módszer egy olyan probléma megoldására, amely megköveteli az összes lehetséges opció teljes felsorolását egy bizonyos M halmazban . Általában lehetővé teszi olyan problémák megoldását, amelyek olyan kérdéseket tesznek fel, mint például: „Minden lehetséges opció felsorolása . .. , "Hányféleképpen ...", "Van-e mód ...", "Létezik-e egy tárgy ..." stb.
A visszalépés kifejezést 1950-ben Derrick Henry Lehmer amerikai matematikus alkotta meg .
A visszakövetési módszer adatábrázolási vagy megvalósítási jellemzőihez kapcsolódó kisebb módosításainak más neve is van: elágazás és kötött módszer , mélységi keresés , próba és hiba módszer stb. A visszakereső keresést sok kutató találta fel szinte egyidejűleg és egymástól függetlenül a formális leírása előtt.
A probléma visszalépés módszerével történő megoldása egy részmegoldás egymást követő kiterjesztésére redukálódik. Ha a következő lépésben egy ilyen bővítés nem sikerül, akkor visszatérnek egy rövidebb részmegoldáshoz, és folytatják a keresést. Ez az algoritmus lehetővé teszi, hogy megtalálja a probléma összes megoldását, ha létezik. A módszer felgyorsítása érdekében a számításokat úgy próbálják megszervezni, hogy a nyilvánvalóan alkalmatlan lehetőségeket minél előbb azonosítsák. Ez gyakran jelentősen csökkentheti a megoldás megtalálásának idejét.
A visszalépési algoritmus használatának klasszikus példája a nyolc királynő probléma . A szövege a következő: "Egy szabványos, 64 cellás sakktáblán helyezzen el 8 királynőt úgy, hogy egyiküket se támadja meg a másik." Először egy királynő kerül a táblára, majd minden következő dámát igyekeznek úgy letenni, hogy a már kialakult királynők ne verjék meg. Ha a következő lépésben nem lehet ilyen beállítást elvégezni, akkor visszalépnek egy lépést, és megpróbálják egy másik helyre tenni a korábban telepített királynőt.
Ezen túlmenően a backtracking módszer számos egyéb felsorolási probléma megoldását is lehetővé teszi. Használatával például megkaphatja egy adott M halmaz összes részhalmazát , elhelyezését , permutációját , kombinációját .
A visszalépési módszer általános. Ezzel a módszerrel meglehetősen könnyű megtervezni és programozni a problémák megoldására szolgáló algoritmusokat. A megoldás megtalálásának ideje azonban a probléma kis dimenziói (a kezdeti adatok mennyisége) mellett is nagyon hosszú lehet, és olyan hosszú (ez lehet évek vagy akár évszázadok is), hogy szó sem lehet gyakorlati alkalmazásról. . Ezért az ilyen algoritmusok megtervezésekor elméletileg meg kell becsülni a konkrét adatokon végzett munkájuk idejét. Vannak kiválasztási problémák is, amelyekre egyedi, „gyors” algoritmusokat építhetünk, amelyek segítségével nagy problémadimenziók esetén is gyorsan megoldást kaphatunk. A visszalépés módszere nem hatékony ilyen problémák esetén.
| Grafikon keresési algoritmusok | ||
|---|---|---|
| Tájékozatlan módszerek | ||
| Tájékozott módszerek | ||
| Parancsikonok | ||
| Minimálisan átívelő fa | ||
| Egyéb | ||