Backtracking - Backtracking

For line søk algoritmen som brukes i ubegrenset optimalisering , se backtracking linjen søk .
Graf og tre
søkealgoritmer
Oppføringer
relaterte temaer

Backtracking er en generell algoritme for å finne løsninger på noen beregningsproblemer , spesielt begrensningsproblemer , som trinnvis bygger kandidater til løsningene, og forlater en kandidat ("backtracks") så snart den bestemmer at kandidaten umulig kan fullføres til en gyldig løsning.

Den klassiske lærebok eksempel på bruk av backtracking er åtte dronninger puslespill , som ber for alle arrangementer av åtte sjakk dronninger på en standard sjakkbrett slik at ingen dronningen angrep noen andre. I den vanlige backtracking-tilnærmingen er delkandidatene arrangementer av k- dronninger i de første k- radene på brettet, alt i forskjellige rader og kolonner. Enhver delvis løsning som inneholder to dronninger som påvirker hverandre, kan forlates.

Backtracking kan bare brukes for problemer som innrømmer begrepet "delvis kandidatløsning" og en relativt rask test av om den muligens kan fullføres til en gyldig løsning. Det er for eksempel ubrukelig for å finne en gitt verdi i en uordnet tabell. Når det er aktuelt, er imidlertid backtracking ofte mye raskere enn opptelling av alle komplette kandidater, siden det kan eliminere mange kandidater med en enkelt test.

Backtracking er et viktig verktøy for å løse problemer med tilfredsstillelse av begrensninger , for eksempel kryssord , verbal aritmetikk , Sudoku og mange andre oppgaver. Det er ofte den mest praktiske teknikken for analyse , for ryggsekkproblemet og andre kombinatoriske optimaliseringsproblemer . Det er også grunnlaget for de såkalte logiske programmeringsspråkene som Icon , Planner og Prolog .

Backtracking avhenger av brukergitte " black box procedures " som definerer problemet som skal løses, arten til delkandidatene og hvordan de utvides til komplette kandidater. Det er derfor en metaheuristisk snarere enn en spesifikk algoritme - selv om det, i motsetning til mange andre metaheuristikker, garantert vil finne alle løsninger på et endelig problem i en avgrenset tid.

Begrepet "backtrack" ble laget av den amerikanske matematikeren DH Lehmer på 1950-tallet. Pionerens strengbehandlingsspråk SNOBOL (1962) kan ha vært den første til å tilby et innebygd generelt tilbakesporingsanlegg.

Beskrivelse av metoden

Backtracking-algoritmen oppregner et sett med delvise kandidater som i prinsippet kan fullføres på forskjellige måter for å gi alle mulige løsninger på det gitte problemet. Fullføringen gjøres trinnvis, ved en sekvens av trinn for utvidelse av kandidater.

Konseptuelt er partikandidatene representert som noder i en trestruktur , det potensielle søketreet. Hver delkandidat er overordnet til kandidatene som skiller seg fra den ved et enkelt utvidelsestrinn; bladene på treet er de delvise kandidatene som ikke kan forlenges lenger.

Backtracking-algoritmen krysser dette søketreet rekursivt , fra roten ned, i dybde-første rekkefølge . Ved hver node c sjekker algoritmen om c kan fullføres til en gyldig løsning. Hvis den ikke kan det, hoppes ( beskjæres ) hele undertreet forankret på c . Ellers sjekker algoritmen (1) om c i seg selv er en gyldig løsning, og rapporterer det i så fall til brukeren; og (2) rekursivt oppregner alle undertrær av c . De to testene og barna til hver node er definert av brukergitte prosedyrer.

Derfor er det faktiske søketreet som krysses av algoritmen bare en del av det potensielle treet. Den totale kostnaden for algoritmen er antall noder for det faktiske treet ganger kostnaden for å skaffe og behandle hver node. Dette faktum bør vurderes når du velger det potensielle søketreet og implementerer beskjæringstesten.

Pseudokode

For å kunne bruke backtracking til en bestemt klasse av problemer, må man oppgi data P for den spesielle forekomsten av problemet som skal løses, og seks prosedyreparametere , rot , avvis , godta , første , neste og utdata . Disse prosedyrene bør ta forekomstdata P som en parameter og skal gjøre følgende:

  1. rot ( P ): returnerer delkandidaten ved roten til søketreet.
  2. avvis ( P , c ): returner sant bare hvis delkandidaten c ikke er verdt å fullføre.
  3. godta ( P , c ): returner sann hvis c er en løsning av P , og ellers falsk .
  4. første ( P , c ): generer den første utvidelsen av kandidat c .
  5. neste ( P , s ): generer den neste alternative utvidelsen til en kandidat, etter utvidelsen s .
  6. output ( P , c ): bruk løsningen c av P , alt etter applikasjonen.

Backtracking-algoritmen reduserer problemet til call backtrack ( root ( P )), der backtrack er følgende rekursive prosedyre: 

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)

Hensyn til bruken

Den avvise prosedyren bør være en boolsk verdi-funksjon som returnerer sant bare hvis det er sikkert at ingen mulig forlengelse av c er en gyldig løsning for P . Hvis prosedyren ikke kan komme til en bestemt konklusjon, bør den returnere falsk . Et feil sant resultat kan føre til at bt- prosedyren går glipp av noen gyldige løsninger. Fremgangsmåten kan anta at avvisning ( P , t ) returnerte falsk for hver forfader t av c i søketreet.

På den annen side avhenger effektiviteten til backtracking-algoritmen av å avvise å returnere sant for kandidater som er så nær roten som mulig. Hvis avvisning alltid returnerer falsk , vil algoritmen fremdeles finne alle løsninger, men det vil tilsvare et søk etter brute-force.

Den godtar Fremgangsmåten skal returnere sann dersom c er en komplett og gyldig løsning på problemet eksempel P , og falsk ellers. Det kan anta at delkandidaten c og alle dens forfedre i treet har bestått avslagstesten .

Den generelle pseudokoden ovenfor antar ikke at de gyldige løsningene alltid er blader av det potensielle søketreet. Med andre ord innrømmer det muligheten for at en gyldig løsning for P kan utvides ytterligere for å gi andre gyldige løsninger.

De første og neste prosedyrene brukes av backtracking-algoritmen for å telle barna til en node c i treet, det vil si kandidatene som skiller seg fra c ved et enkelt utvidelsestrinn. Samtalen først ( P , c ) skal gi det første barnet til c , i en eller annen rekkefølge; og samtalen neste ( P , s ) skal returnere neste søsken til node s , i den rekkefølgen. Begge funksjonene skal returnere en særegen "NULL" -kandidat, hvis det etterspurte barnet ikke eksisterer.

Sammen definerer rot- , første- og neste- funksjonene settet med delvise kandidater og det potensielle søketreet. De bør velges slik at hver løsning av P forekommer et sted i treet, og ingen delkandidater forekommer mer enn en gang. Videre bør de innrømme et effektivt og effektivt avvise predikat.

Tidlige stoppvarianter

Den pseudo-kode ovenfor vil kalle utgang for alle kandidater som er en løsning på det gitt tilfelle P . Algoritmen kan modifiseres for å stoppe etter å ha funnet den første løsningen, eller et spesifisert antall løsninger; eller etter å ha testet et spesifisert antall delkandidater, eller etter å ha brukt en gitt mengde CPU- tid.

Eksempler

En Sudoku løst ved backtracking.

Eksempler der backtracking kan brukes til å løse gåter eller problemer inkluderer:

Følgende er et eksempel der backtracking brukes for problemet med tilfredshet av begrensning :

Begrensningstilfredshet

Problemet med generell begrensningstilfredshet består i å finne en liste over heltall x = ( x [1], x [2],…, x [ n ]) , hver i et område {1, 2,…, m }, som tilfredsstiller noen vilkårlig begrensning (boolske funksjon) F .

For denne klasse av problemer, kan forekomsten av dataene P ville være heltallene m og n , og den predikat F . I en typisk tilbakesporingsløsning på dette problemet, kan man definere en delvis kandidat som en liste over heltall c = ( c [1], c [2],…, c [k]) , for hvilken som helst k mellom 0 og n , som skal tilordnes de første k- variablene x [1], x [2],…, x [ k ] . Rotkandidaten vil da være den tomme listen (). Den første og neste prosedyren vil da være 

function first(P, c) is
    k ← length(c)
    if k = n then
        return NULL
    else
        return (c[1], c[2], …, c[k], 1)

function next(P, s) is
    k ← length(s)
    if s[k] = m then
        return NULL
    else
        return (s[1], s[2], …, s[k − 1], 1 + s[k])

Her er lengde ( c ) antall elementer i listen c .

Anropet avvise ( P , c ) skal returnere sann dersom begrensningen F ikke kan tilfredsstilles ved en hvilken som helst liste med n hele tall som begynner med de k elementer av c . For at backtracking skal være effektiv, må det være en måte å oppdage denne situasjonen, i det minste for noen kandidater c , uten å telle opp alle disse m n - k n - tuplene.

For eksempel, hvis F er en forbindelse av flere boolske predikater, er F = F [1] ∧ F [2] ∧… ∧ F [ p ] , og hver F [ i ] avhenger bare av en liten delmengde av variablene x [1 ],…, X [ n ] , så kunne avvisningsprosedyren ganske enkelt sjekke begrepene F [ i ] som bare avhenger av variablene x [1],…, x [ k ] , og returnere sann hvis noen av disse begrepene returnerer falske . Faktisk må avvisning bare sjekke de begrepene som avhenger av x [ k ], siden begrepene som bare avhenger av x [1],…, x [ k - 1] vil ha blitt testet lenger opp i søketreet.

Forutsatt at avvisning er implementert som ovenfor, må akseptere ( P , c ) bare sjekke om c er komplett, det vil si om den har n elementer.

Det er generelt bedre å ordne listen over variabler slik at den begynner med de mest kritiske (dvs. de med færrest verdialternativer, eller som har større innvirkning på påfølgende valg).

Man kan også la den neste funksjonen velge hvilken variabel som skal tildeles når en delvis kandidat utvides, basert på verdiene til variablene som allerede er tildelt av den. Ytterligere forbedringer kan oppnås ved teknikken for begrensning forplantning .

I tillegg til å beholde minimale gjenopprettingsverdier som brukes i sikkerhetskopiering, holder backtracking-implementeringer ofte en variabel sti for å registrere endringshistorikk for verdi. En effektiv implementering vil unngå å skape en variabel stiinngang mellom to påfølgende endringer når det ikke er noe valgpunkt, da tilbakesporingen vil slette alle endringene som en enkelt operasjon.

Et alternativ til den variable stien er å holde et tidsstempel på når den siste endringen ble gjort i variabelen. Tidsstempelet sammenlignes med tidsstemplet til et valgpunkt. Hvis valgpunktet har en tilknyttet tid senere enn variabelen, er det unødvendig å tilbakestille variabelen når valgpunktet blir sporet tilbake, ettersom det ble endret før valgpunktet skjedde.

Se også

Merknader

Referanser

Videre lesning

Eksterne linker