Backtracking haku , backtracking on yleinen menetelmä löytää ratkaisuja ongelmaan, joka vaatii täydellisen luettelon kaikista mahdollisista vaihtoehdoista tietyssä joukossa M. Yleensä sen avulla voit ratkaista ongelmia, joissa esitetään kysymyksiä, kuten: "Luettelo kaikki mahdolliset vaihtoehdot . .. , "Kuinka monta tapaa ...", "Onko tapa ...", "Onko esine olemassa ..." jne.
Termi backtracking loi vuonna 1950 amerikkalainen matemaatikko Derrick Henry Lehmer .
Pienet tiedonesitys- tai toteutusominaisuuksiin liittyvät backtracking-menetelmän muutokset ovat saaneet muita nimiä: haara ja sidottu menetelmä , syvällinen haku , yritys ja erehdys -menetelmä jne. Paluuhaun keksivät monet tutkijat lähes samanaikaisesti ja itsenäisesti ennen sen muodollista kuvausta.
Ongelman ratkaisu paluumenetelmällä rajoittuu osittaisen ratkaisun peräkkäiseen laajentamiseen. Jos seuraavassa vaiheessa tällainen laajennus epäonnistuu, palataan lyhyempään osaratkaisuun ja jatketaan etsintää. Tämän algoritmin avulla voit löytää kaikki ratkaisut ongelmaan, jos niitä on. Menetelmän nopeuttamiseksi laskelmat pyritään järjestämään siten, että ilmeisen sopimattomat vaihtoehdot löydetään mahdollisimman aikaisessa vaiheessa. Usein tämä voi merkittävästi lyhentää ratkaisun löytämiseen kuluvaa aikaa.
Klassinen esimerkki backtracking-algoritmin käytöstä on kahdeksan kuningattaren ongelma . Sen sanamuoto on seuraava: "Järjestä 8 kuningatarta tavalliselle 64-soluiselle shakkilaudalle niin, ettei kukaan heistä joudu toisen hyökkäyksen kohteeksi." Ensin yksi kuningatar asetetaan laudalle, ja sitten he yrittävät asettaa jokaisen seuraavan kuningattaren, jotta jo vakiintuneet kuningattaret eivät lyö sitä. Jos seuraavassa vaiheessa tällaista asetusta ei voida tehdä, he palaavat yhden askeleen taaksepäin ja yrittävät laittaa aiemmin asennettua kuningattaren toiseen paikkaan.
Lisäksi backtracking-menetelmän avulla voit ratkaista monia muita luettelointiongelmia. Esimerkiksi käyttämällä sitä voit saada tietyn joukon M kaikki osajoukot , sijoittelut , permutaatiot ja yhdistelmät.
Paluumenetelmä on yleinen. On melko helppoa suunnitella ja ohjelmoida algoritmeja ongelmien ratkaisemiseksi tällä menetelmällä. Aika ratkaisun löytämiseen voi kuitenkin olla hyvin pitkä ongelman pienilläkin ulottuvuuksilla (alkutietojen määrä) ja se on niin pitkä (voi olla vuosia tai jopa vuosisatoja), että käytännön soveltamisesta ei voi olla kysymys. . Siksi tällaisia algoritmeja suunniteltaessa on välttämätöntä arvioida teoreettisesti niiden työskentelyaika tietyillä tiedoilla. On myös valintaongelmia, joihin voit rakentaa ainutlaatuisia, "nopeita" algoritmeja, joiden avulla voit saada nopeasti ratkaisun myös suurilla ongelmamitoilla. Peruutusmenetelmä on tehoton tällaisissa ongelmissa.
| Kaavion hakualgoritmit | ||
|---|---|---|
| Tietämättömät menetelmät | ||
| Tietoon perustuvat menetelmät | ||
| Pikanäppäimet | ||
| Vähintään ulottuva puu | ||
| Muut | ||