Tilbakesporing

Backtracking (på italiensk kan det defineres "backward monitoring") er en teknikk for å finne løsninger på problemer der begrensninger må tilfredsstilles. Denne teknikken oppregner alle mulige løsninger og forkaster de som ikke tilfredsstiller begrensningene.

En klassisk teknikk er å utforske trestrukturer og holde styr på alle tidligere besøkte noder og grener, slik at du kan gå tilbake til nærmeste node som inneholdt en ennå uutforsket sti i tilfelle søket i gjeldende gren ikke lyktes. Noder med lik dybde representerer de mulige verdiene til en variabel.

En anvendelse av backtracking er i sjakkprogrammer , som genererer alle mulige trekk for en dybde på N trekk fra det gjeldende og deretter går tilbake til de forskjellige alternativene, og velger det beste på slutten.

Tilbakesporing har eksponentiell kompleksitet , så det er ineffektivt til å takle ikke -NP-komplette problemer . Generelt sett integrerer imidlertid algoritmen heuristikk som gjør det mulig å redusere kompleksiteten.

Denne teknikken er grunnlaget for programmeringsspråket Prolog .

Typer tilbakesporing

De mulige typene tilbakesporing er mange, med ulik funksjon, ulike egenskaper og ulike fordeler. De mest kjente er:

De fire første algoritmene er definert som grunnleggende algoritmer, da de representerer forskjellige grunnleggende "filosofier" og forskjellige metoder for å sette tilbake sporing i praksis; mens sistnevnte i stedet er et velkjent eksempel på en hybridalgoritme, det vil si en algoritme som kan betraktes som en variant av de grunnleggende algoritmene, men som, nettopp på grunn av sin forskjell fra algoritmene den stammer fra, kan gi mange fordeler .

Eksempler

Et problem som kan løses med denne metoden er den boolske tilfredsstillelsen til en førsteordens proposisjon i logikk ( K-SAT ). Algoritmen fortsetter ved å sette verdien til hver variabel, til formelen er tilfredsstilt (vi antar at den er tilfredsstilt).

For enkelhets skyld tar vi formelen , teknikken fortsetter som følger:

x y Ri
Falsk Falsk Falsk tilbakespor av y
Falsk Sant Falsk tilbakesporing av x
Sant Falsk Falsk tilbakespor av y
Sant Sant Sant Løsning

Eksemplet i form av Python -kode (koden stopper ikke når den finner resultatet):

def prop ( x , y ): returner "JA" hvis x og y ellers "NEI" vals = [ False , True ] print ( " x \ t y " ) for x in vals : for y in vals : print ( " % s \ t % s \ t % s " % ( x , y , prop ( x , y )))

Den produserer som et resultat:

xy Falsk Falsk NEI Usant Sant NEI Sant usant NEI Sant Sant JA

Relaterte elementer

Andre prosjekter