Revenire pe urmele necronologice

În algoritmii de căutare și backtracking , revenirea pe pistă necronologică sau backjumping este o tehnică care reduce spațiul de căutare și, prin urmare, crește eficiența. În backtrack-ul obișnuit, un backtrack crește cu un nivel în arborele de căutare atunci când toate valorile unei variabile au fost testate. Întoarcerea necronologică face posibilă revenirea la mai multe niveluri datorită unei analize a motivelor care determină eșecul unei combinații de valori. În acest articol, se utilizează o ordine fixă ​​de evaluare a variabilelor, dar aceleași considerații se aplică unei ordine dinamice de evaluare.

• Un arbore de cercetare vizitat în mod regulat de flashback-uri

• Un backjump: nodul gri nu este vizitat

Definiție

Într-un algoritm de backtrack, dacă pentru un nod al arborelui de căutare, dacă toate valorile variabilei alese pentru acest nod duc la o contradicție sau dacă nicio valoare a acestei variabile nu duce la o soluție, algoritmul revine la valoarea a variabilei nodului părinte încercând o nouă valoare, apoi la valoarea variabilei anterioare dacă au fost încercate și toate valorile. Dacă este atribuirea parțială curentă a variabilelor și dacă toate valorile lui au fost încercate fără a găsi o soluție, algoritmul concluzionează că niciuna dintre valori nu există. Apoi algoritmul „se întoarce” și , dacă este posibil, alege o nouă valoare pentru care să fie atribuită sau se întoarce din nou dacă nu mai există valoare de încercat. X1=la1,...,Xk=lak{\ displaystyle x_ {1} = a_ {1}, \ ldots, x_ {k} = a_ {k}}Xk+1{\ displaystyle x_ {k + 1}}Xk+1{\ displaystyle x_ {k + 1}}Xk{\ displaystyle x_ {k}}Xk{\ displaystyle x_ {k}}

Toate valorile atribuirii parțiale nu sunt întotdeauna necesare pentru a demonstra că nicio valoare a nu conduce la o soluție. În special, un prefix de atribuire parțială poate avea aceeași proprietate, adică există un astfel de index care nu poate fi extins pentru a forma o soluție indiferent de valoarea lui . Dacă algoritmul poate dovedi acest fapt, putem lua în considerare direct o valoare diferită pentru, în loc să reconsiderăm așa cum ar fi în mod normal. Xk+1{\ displaystyle x_ {k + 1}}j<k{\ displaystyle j <k}X1,...,Xj=la1,...,laj{\ displaystyle x_ {1}, \ ldots, x_ {j} = a_ {1}, \ ldots, a_ {j}}Xk+1{\ displaystyle x_ {k + 1}}Xj{\ displaystyle x_ {j}}Xk{\ displaystyle x_ {k}}

Un exemplu în care atribuirea parțială curentă a a fost încercată fără succes pentru toate valorile posibile ale . Backtrack-ul revine , încercând să îi atribuiți o nouă valoare. X1X2X3X4{\ displaystyle x_ {1} x_ {2} x_ {3} x_ {4}}X5{\ displaystyle x_ {5}}X4{\ displaystyle x_ {4}}	În loc de a reveni la niveluri mai ridicate, algoritmul dezvoltat demonstrând că nu aveți teme , șiX1X2X5=211{\ displaystyle x_ {1} x_ {2} x_ {5} = 211}X1X2X5=212{\ displaystyle x_ {1} x_ {2} x_ {5} = 212}X1X2X5=213{\ displaystyle x_ {1} x_ {2} x_ {5} = 213}	Ca urmare, nici atribuirea nu duce niciodată la o soluție. Algoritmul revine apoi direct la încercarea de a-i atribui o nouă valoare. X1X2{\ displaystyle x_ {1} x_ {2}}X2{\ displaystyle x_ {2}}

Eficiența unui astfel de algoritm depinde de înălțimea la care este capabil să urce necronologic. În mod ideal, algoritmul ar putea schimba de la la oricare dintre astfel încât repartizarea actuală a nu poate fi extinsă pentru a forma o soluție pentru orice valoare . Dacă da, se face un salt sigur . Xk+1{\ displaystyle x_ {k + 1}}Xj{\ displaystyle x_ {j}}X1,...,Xj{\ displaystyle x_ {1}, \ ldots, x_ {j}}Xk+1{\ displaystyle x_ {k + 1}}j{\ displaystyle j}

Stabilirea faptului dacă un salt este sigur nu este întotdeauna posibilă, deoarece, prin definiție, demonstrarea necesită cunoașterea setului de soluții, care este exact ceea ce este căutat de algoritm. În practică, algoritmii de back-jumping nu încearcă să găsească toate salturile sigure, ci folosesc tehnici pentru a demonstra rapid că un salt este sigur. Diferiti algoritmi folosesc metode diferite pentru a determina dacă un salt este sigur. Saltul realizat este cel mai mic indice, care poate fi demonstrat în mod eficient că este sigur. Există mai multe metode mai mult sau mai puțin complexe de a face acest lucru, dar costul celor mai scumpe, dacă găsesc un indice ridicat, ar putea fi compensat printr-o reducere semnificativă a dimensiunii arborelui de cercetare. Prin urmare, există un compromis de găsit.

Nod de frunze sărit înapoi

Cea mai simplă condiție în care backbumping-ul este posibil este atunci când s-a dovedit că toate valorile unei variabile sunt incompatibile într-un nod al arborelui de căutare și, prin urmare, nu mai este posibilă ramificarea de la acest nod. În satisfacția constrângerii , o atribuire parțială este consecventă dacă și numai dacă satisface toate constrângerile care implică variabilele atribuite și contradictorii în caz contrar. Este posibil ca o soluție parțială coerentă să nu poată fi extinsă la o soluție mai completă, deoarece atribuirea unor posibile valori unor variabile suplimentare duce în mod sistematic la generarea de evaluări contradictorii.

Starea în care toate valorile unei variabile date sunt incompatibile cu soluția parțială se numește frunză moartă . Această stare apare atunci când variabila este o frunză a arborelui de căutare (care corespund nodurilor care au drept copii doar o frunză a arborelui din figurile acestui articol.) Xk+1{\ displaystyle x_ {k + 1}}X1,...,Xk=la1,...,lak{\ displaystyle x_ {1}, \ ldots, x_ {k} = a_ {1}, \ ldots, a_ {k}}Xk+1{\ displaystyle x_ {k + 1}}

Saltul înapoi prin algoritmul Gaschnig efectuează doar un salt înapoi în frunzele moarte. Cu alte cuvinte, funcționează diferit de backtracking-ul clasic numai atunci când toate valorile posibile ale x_ {k + 1} au fost testate și au dus la o inconsecvență, fără a fi nevoie să ramificați arborele în continuare.

Un salt sigur poate fi găsit pur și simplu prin evaluarea, pentru fiecare valoare a celui mai scurt prefix sau incompatibil cu . Cu alte cuvinte, dacă este o valoare posibilă , algoritmul verifică consistența următoarelor evaluări: lak+1{\ displaystyle a_ {k + 1}}X1,...,Xk=la1,...,lak{\ displaystyle x_ {1}, \ ldots, x_ {k} = a_ {1}, \ ldots, a_ {k}}Xk+1=lak+1{\ displaystyle x_ {k + 1} = a_ {k + 1}}lak+1{\ displaystyle a_ {k + 1}}Xk+1{\ displaystyle x_ {k + 1}}

X1=la1{\ displaystyle x_ {1} = a_ {1}}	...	Xk-1=lak-1{\ displaystyle x_ {k-1} = a_ {k-1}}	Xk=lak{\ displaystyle x_ {k} = a_ {k}}	Xk+1=lak+1{\ displaystyle x_ {k + 1} = a_ {k + 1}}
X1=la1{\ displaystyle x_ {1} = a_ {1}}	...	Xk-1=lak-1{\ displaystyle x_ {k-1} = a_ {k-1}}	Xk+1=lak+1{\ displaystyle x_ {k + 1} = a_ {k + 1}}
...
X1=la1{\ displaystyle x_ {1} = a_ {1}}	Xk+1=lak+1{\ displaystyle x_ {k + 1} = a_ {k + 1}}

Cel mai mic indice (cel mai mic din listă) pentru care evaluările sunt inconsistente ar fi un salt sigur în cazul în care ar fi fost singura valoare posibilă . Ca regulă generală, nu există o singură atribuire posibilă pentru o variabilă, indicele maxim dat prin efectuarea acestei căutări este, prin urmare, un salt sigur și tocmai la nodul corespunzător saltează algoritmul (Gaschnig). Xk+1=lak+1{\ displaystyle x_ {k + 1} = a_ {k + 1}}Xk+1{\ displaystyle x_ {k + 1}}

Salt la nodurile interne

Algoritmul anterior sare doar necronologic atunci când o soluție parțială poate fi dovedită a fi inconsistentă fără ramificații suplimentare. Cu alte cuvinte, permite doar un backjump să frunze nodurile arborelui de căutare.

Un nod intern al arborelui de căutare reprezintă o atribuire a unei variabile care este în concordanță cu cele anterioare. Dacă nicio soluție nu extinde această atribuire, algoritmul anterior sare întotdeauna la nodul părinte și niciodată nu cronologic.

Un salt necronologic către un nod intern poate fi efectuat numai dintr-o frunză. Într-adevăr, dacă anumite evaluări necesită ramificații, aceasta se datorează faptului că sunt compatibile cu misiunea curentă. Ca urmare, căutarea unui prefix care să contrazică aceste valori potențiale ale ultimei variabile va eșua. Xk+1{\ displaystyle x_ {k + 1}}

Într-un astfel de caz, ceea ce a făcut posibilă demonstrarea faptului că o misiune nu poate face parte dintr-o soluție compatibilă cu misiunea parțială este căutarea recursivă . În special, algoritmul „știe” că nu poate fi găsită nicio soluție din acest moment deoarece s-a întors la acest nod fără să fi găsit o soluție la unul dintre copiii săi. Xk+1=lak+1{\ displaystyle x_ {k + 1} = a_ {k + 1}}X1,...,Xk{\ displaystyle x_ {1}, \ ldots, x_ {k}}

Acest feedback este cauzat de o serie de impasuri , puncte în care algoritmul a arătat că o anumită atribuire parțială este inconsistentă. Pentru a sari mai sus, algoritmul trebuie să țină cont de faptul că imposibilitatea de a găsi soluții este cauzată de aceste impasuri. În special, salturile sigure sunt indicii prefixelor care păstrează faptul că atribuțiile parțiale ale acestor fundaturi sunt, de asemenea, atribuții parțiale inconsistente.

În acest exemplu, algoritmul revine la , după testarea tuturor valorilor posibile. Într-adevăr, toate punctele pe care le-a trecut erau inconsistente. Xk+1{\ displaystyle x_ {k + 1}}	Al doilea punct rămâne inconsecvent atunci când valorile pentru și sunt eliminate din atribuirea parțială (rețineți că valorile unei variabile sunt în copiii nodului său) Xk+1{\ displaystyle x_ {k + 1}}Xk{\ displaystyle x_ {k}}	Alte evaluări inconsecvente , de asemenea , rămân stocari , șiXk-2{\ displaystyle x_ {k-2}}Xk-1{\ displaystyle x_ {k-1}}Xk{\ displaystyle x_ {k}}	Algoritmul poate sări pentru că este cea mai mică variabilă din arborele care păstrează toate inconsecvențele. Se va încerca o nouă valoare a . Xk-2{\ displaystyle x_ {k-2}}Xk-2{\ displaystyle x_ {k-2}}

Cu alte cuvinte, când toate valorile lui au fost testate, algoritmul poate sări la o variabilă anterioară din momentul respectiv sau la valoarea de adevăr a evaluării parțiale a nodurilor frunze descendente ale . este fals. Xk+1{\ displaystyle x_ {k + 1}}Xeu{\ displaystyle x_ {i}}X1,...,Xeu{\ displaystyle x_ {1}, \ ldots, x_ {i}} Xk+1,Xk+2,...{\ displaystyle x_ {k + 1}, x_ {k + 2}, ...}Xk+1{\ displaystyle x_ {k + 1}}

Simplificări

Datorită numărului potențial mare de noduri din subarborele din , informațiile necesare pentru a sări în siguranță necronologic de la sunt colectate în timpul explorării subarborilor săi. Există două moduri de a optimiza căutarea unui salt sigur. Primul este că algoritmul funcționează pentru orice salt sigur, prin urmare nu este necesar să se găsească cel mai înalt salt posibil. Xk+1{\ displaystyle x_ {k + 1}}Xk+1{\ displaystyle x_ {k + 1}}

Al doilea este că nodurile subarborelui evitat în timpul unui salt pot fi ignorate atunci când se caută un salt pentru . Mai precis, toate nodurile evitate în timpul unei sărituri de la un nod la un nod sunt irelevante pentru subarborele înrădăcinat în , precum și pentru subarborii lor. Xl{\ displaystyle x_ {l}}Xl{\ displaystyle x_ {l}}Xm{\ displaystyle x_ {m}}Xl{\ displaystyle x_ {l}}Xm{\ displaystyle x_ {m}}

Într-adevăr, dacă un nod coboară dintr-un nod x_ {l} printr-o cale și un salt necronologic are loc în timpul revenirii la x_l, ar fi fost posibil să se scurteze această cale și să se meargă direct de la și să obțină același lucru rezultat. Saltul ne spune că atribuțiile nodurilor dintre și sunt irelevante pentru subarborele înrădăcinat în . Cu alte cuvinte, un salt non-cronologic indică faptul că vizitarea unei regiuni a arborelui de cercetare a fost o greșeală. Prin urmare, această parte poate fi ignorată atunci când se evaluează oportunitatea unui salt necronologic de la sau de la unul dintre strămoșii săi. Xm{\ displaystyle x_ {m}}Xl{\ displaystyle x_ {l}}Xm{\ displaystyle x_ {m}}Xl{\ displaystyle x_ {l}}Xm{\ displaystyle x_ {m}}Xm{\ displaystyle x_ {m}}Xl{\ displaystyle x_ {l}}

Acest fapt poate fi exploatat prin colectarea în fiecare nod a unui set de variabile atribuite anterior a căror evaluare este suficientă pentru a arăta că nu există nicio soluție în subarborele înrădăcinat la acel nod. Acest set este construit în timpul executării algoritmului. În timpul unui salt dintr-un nod, variabila acestui nod este eliminată și adăugată la setul asociat cu destinația saltului. Deoarece nu sărim niciodată dintr-un nod evitat de un salt necronologic, seturile lor sunt ignorate automat.

Găsiți salturi cu grafice

Găsirea salturilor necronologice folosind graficul a fost introdusă deoarece un salt sigur poate fi găsit verificând variabilele care apar într-o constrângere care conține variabile care sunt instanțiate în nodurile frunzei. Pentru fiecare nod frunză și fiecare variabilă de index instanțiată la acel nod, indicii mai mici sau egali cu a căror variabilă se află într-o constrângere pot fi folosiți pentru a găsi salturi sigure. În special, când s- au încercat toate valorile pentru , acest set conține indicii variabilelor ale căror evaluări fac posibilă demonstrarea faptului că nu se va găsi nicio soluție vizitând subarborele înrădăcinat la nod . Ca urmare, algoritmul poate sări la cel mai mare indice din această serie. X1,...,Xk{\ displaystyle x_ {1}, \ ldots, x_ {k}}Xk+1,Xk+2,...{\ displaystyle x_ {k + 1}, x_ {k + 2}, ...}Xeu{\ displaystyle x_ {i}}eu>k{\ displaystyle i> k}k{\ displaystyle k}Xeu{\ displaystyle x_ {i}}Xk+1{\ displaystyle x_ {k + 1}}Xk+1{\ displaystyle x_ {k + 1}}

Faptul că nodurile ignorate de salt non-cronologic pot fi ignorate în timpul căutării ulterioare pentru un alt salt poate fi utilizat prin exploatarea următorului algoritm. Când se retrage dintr-un nod frunză, un set de variabile care se află într-o constrângere a variabilei sale este creat și „returnat” tatălui sau strămoșului în cazul unui salt necronologic. Un set de variabile este menținut în fiecare nod intern. Ori de câte ori se primește un set de variabile de la unul dintre copiii sau descendenții săi, variabilele lor sunt adăugate la setul acestui nod. În timpul unei sărituri de la acest nod, setul său, din care a fost eliminată variabila de nod, este trimis la nodul de destinație. Acest algoritm funcționează deoarece setul ținut într-un nod colectează toate variabilele care sunt relevante pentru a dovedi inconsecvența frunzelor care coboară din acesta. Aceste seturi de variabile fiind transmise numai în timpul unui salt dintr-un nod, seturile colectate la nivelul nodurilor evitate în timpul unui salt sunt ignorate automat.

Salturi conduse de conflicte

Un algoritm de saltare necronologic și mai rafinat, uneori capabil să evite explorarea mai multor noduri, se bazează pe analiza constrângerii care a cauzat inconsecvența și nu mai este doar pe prezența a două variabile în aceeași constrângere. În special, acest algoritm colectează una dintre constrângerile încălcate în fiecare frunză. La fiecare nod, cel mai mare indice dintre variabilele care apar într-o constrângere colectată în foi este un salt sigur.

Indiferent de constrângerea încălcată aleasă în fiecare foaie, saltul este sigur. Prin alegerea constrângerilor cu cei mai mari indici, înălțimea saltului este, prin urmare, maximizată. Din acest motiv, algoritmii de salt direcționați spre conflict ordonează constrângerile astfel încât constrângerile cu variabile cu indici mici sunt preferate în fața constrângerilor cu variabile cu indici mai mari.

În mod formal, o constrângere este preferată față de alta dacă cel mai mare indice al unei variabile în dar nu în este mai mic decât cel mai mare indice al unei variabile în dar nu în . Cu alte cuvinte, excluzând variabilele comune, este preferată constrângerea care are cele mai mici variabile de index. VS{\ displaystyle C}D{\ displaystyle D}VS{\ displaystyle C}D{\ displaystyle D}D{\ displaystyle D}VS{\ displaystyle C}

Într-un nod frunză, algoritmul alege cel mai mic indice astfel încât rezultă o inconsecvență cu atribuirea variabilei frunze. Dintre constrângerile care sunt încălcate de această atribuire, aceasta alege una în funcție de euristica care tocmai a fost descrisă și colectează indicii variabilelor sale mai puțin de . În acest fel, când algoritmul revine la variabilă, cel mai mic indice colectat denotă un salt sigur. eu{\ displaystyle i}X1,...,Xeu{\ displaystyle x_ {1}, \ ldots, x_ {i}}k+1{\ displaystyle k + 1}Xk+1{\ displaystyle x_ {k + 1}}

În practică, acest algoritm este simplificat prin colectarea tuturor indicilor într-un singur set, în loc de crearea unui set pentru fiecare valoare a . În special, algoritmul colectează, în fiecare nod, toate seturile care revin de la descendenții săi, care nu au fost ignorate de saltul necronologic. La întoarcerea de la acest nod, setul său scăzut din variabila sa este adăugat la setul nodului de destinație returnat. k{\ displaystyle k}

Vezi și tu

• Înapoi pe drumul cel bun
• Constrângeri de învățare  (în)

Referințe

• Rina Dechter , Constraint Processing , Morgan Kaufmann,2003, 481  pag. ( ISBN  1-55860-890-7 , citit online )
• Patrick Prosser , „  Algoritmi hibrizi pentru problema de satisfacție a constrângerilor  ”, Inteligența computațională ,1993( citește online )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">