takaisinvetoalgoritmi luettelee joukon osittaisia ehdokkaita, jotka periaatteessa voitaisiin suorittaa eri tavoin, jotta annettuun ongelmaan saataisiin kaikki mahdolliset ratkaisut. Loppuunsaattaminen tapahtuu vähitellen, jono ehdokkaan jatkovaiheita.
käsitteellisesti osittaisehdokkaat esitetään puurakenteen solmuina, potentiaalisena hakupuuna. Jokainen osaehdokas on niistä ehdokkaista vanhempi, jotka eroavat siitä yhdellä jatkovaiheella; puun lehdet ovat osaehdokkaita, joita ei voi enää pidentää.
taustahakualgoritmi kulkee tämän hakupuun läpi rekursiivisesti, juuresta alaspäin, syvyyssuunnassa-ensimmäisessä järjestyksessä. Jokaisessa solmussa C algoritmi tarkistaa, voidaanko C täydentää kelvolliseen ratkaisuun. Jos se ei pysty, koko C-Juurinen alapuu ohitetaan (karsitaan). Muussa tapauksessa algoritmi (1) tarkistaa, onko c itsessään kelvollinen ratkaisu, ja jos näin on, ilmoittaa sen käyttäjälle; ja (2) luetteloi rekursiivisesti kaikki C: n osapuut. kaksi testiä ja kunkin solmun lapset määritellään käyttäjän antamien menettelyjen mukaan.
näin ollen algoritmin läpikäymä varsinainen hakupuu on vain osa potentiaalista puuta. Algoritmin kokonaiskustannus on todellisen puun solmujen lukumäärä kertaa kunkin solmun saamisen ja käsittelyn kustannukset. Tämä seikka on otettava huomioon mahdollisen hakupuun valinnassa ja karsintatestin toteuttamisessa.
Pseudokoodeedit
jotta voidaan soveltaa takaisinvetoa tiettyyn ongelmaluokkaan, on annettava tiedot P ratkaistavan ongelman yksittäisestä esiintymästä sekä kuusi prosessiparametria, root, reject, accept, first, next ja output. Näissä menettelyissä olisi otettava esimerkiksi data P parametrina ja olisi tehtävä seuraavat:
- juuri (P): palautetaan osittainen ehdokas hakupuun juureen.
- hylkää(P,c): palauta tosi vain, jos osaehdokasta c ei kannata täyttää.
- accept (P, c): palauta true jos c on P: n ratkaisu ja false muuten.
- ensimmäinen(P,c): luo ehdokkaan C ensimmäinen laajennus.
- seuraava(P,s): luo ehdokkaan seuraava vaihtoehtoinen laajennus laajennuksen s jälkeen.
- tuotos(P, c): käytä P: n liuosta c hakemuksen mukaan.
takaisinvetoalgoritmi pelkistää ongelman call backtrackiin (root (P)), jossa takaisinveto on seuraava rekursiivinen menettely:
procedure backtrack(c) is if reject(P, c) then return if accept(P, c) then output(P, c) s ← first(P, c) while s ≠ NULL do backtrack(s) s ← next(P, s)
Usage considerationsEdit
hylkäysmenettelyn tulee olla boolean-arvoinen funktio, joka palauttaa true-arvon vain, jos on varmaa, ettei mikään mahdollinen C: n laajennus ole kelvollinen ratkaisu P: lle.jos menettelyllä ei voida saavuttaa varmaa johtopäätöstä, palautetaan false. Virheellinen todellinen tulos voi aiheuttaa sen, että bt-menettelystä puuttuu joitakin päteviä ratkaisuja. Menettely voi olettaa, että reject (P,t) palautetaan false jokaisen esi-T C hakupuussa.
toisaalta takaisinvetoalgoritmin tehokkuus riippuu siitä, palautuuko hylkäys true ehdokkaille, jotka ovat mahdollisimman lähellä juurta. Jos reject palauttaa aina epätosi, algoritmi löytää silti kaikki ratkaisut, mutta se vastaa raakaa voimahakua.
hyväksymismenettelyn tulee palauttaa true, jos C on täydellinen ja pätevä ratkaisu ongelmailmaisuun P, ja false muuten. Se voi olettaa, että osittainen ehdokas c ja kaikki sen esi-isät puussa ovat läpäisseet hylkäyskokeen.
yllä oleva yleinen pseudokoodi ei oleta, että kelvolliset ratkaisut olisivat aina mahdollisen hakupuun lehtiä. Toisin sanoen, se myöntää mahdollisuuden, että pätevä ratkaisu P voidaan edelleen laajentaa tuottaa muita päteviä ratkaisuja.
ensimmäisen ja seuraavan menetelmän avulla voidaan takaisinkytkentäalgoritmin avulla laskea puun solmun c lapset, eli ehdokkaat, jotka eroavat c: stä yhdellä laajennusvaiheella. Puhelun ensimmäinen (P, c) pitäisi tuottaa ensimmäinen lapsi c, jossain järjestyksessä; ja puhelun seuraava (P, s) pitäisi palauttaa seuraava sisarus solmu S, tässä järjestyksessä. Molemmat toiminnot olisi palautettava erottuva ”NULL” ehdokas, jos pyydettyä lasta ei ole olemassa.
yhdessä juuri -, ensimmäinen-ja next-funktiot määrittelevät osittaisehdokkaiden joukon ja mahdollisen hakupuun. Ne tulisi valita niin, että jokainen P: n ratkaisu esiintyy jossain puussa, eikä osittaista ehdokasta esiinny useammin kuin kerran. Lisäksi heidän pitäisi hyväksyä tehokas ja tehokas hylkäyspääte.
early Stop variantsEdit
yllä oleva pseudokoodi kutsuu tulosteen kaikille ehdokkaille, jotka ovat ratkaisu annettuun instanssiin P. algoritmia voidaan muokata pysähtymään löydettyään ensimmäisen ratkaisun tai määrätyn määrän ratkaisuja; tai testattuaan tietyn määrän osittaisia ehdokkaita tai käytettyään tietyn määrän suoritinaikaa.