Pretraga sa nehronološkim vraćanjem

Pretraga sa nehronološkim vraćanjem (engl. Backjumping) je tehnika koja povećava efikasnost bektreking algoritama. Bektreking uvek ide jedan nivo unatrag u stablu pretrage kada su testirane sve vrednosti za promenljivu, dok se pretragom sa nehronološkim vraćanjem može ići više nivoa unatrag. U ovom članku se koristi statički poredak promenljivih $x_{1},\ldots ,x_{n}$, ali se ista pravila odnose i na dinamički.

• 
  Stablo pretrage posećeno regularnim bektrekingom
• 
  Skok unatrag: sivi čvor nije posećen

Definicija

Kad god su bektrekingom isprobane sve vrednosti za promenljivu bez pronalaska rešenja, preispituje se poslednja od ranije dodeljenih promenljivih, menja joj se vrednost ili se nastavlja bektreking ako nema drugih vrednosti za dodelu. Ako je $x_{1}=a_{1},\ldots ,x_{k}=a_{k}$ trenutna delimična dodela i sve vrednosti za $x_{k+1}$ su isprobane bez pronalaska rešenja, zaključuje se da rešenje sa $x_{1}=a_{1},\ldots ,x_{k}=a_{k}$ ne postoji. Algoritam potom "ide gore" na $x_{k}$ i menja joj vrednost ako je moguće, u suprotnom ponovo vrši bektreking.

Nije uvek neophodna cela delimična dodela da bi se dokazalo da nijedna vrednost $x_{k+1}$ ne vodi do rešenja. Prefiks delimične dodele može imati iste osobine, to jest, postoji indeks $j<k$ tako da $x_{1},\ldots ,x_{j}=a_{1},\ldots ,a_{j}$ ni sa jednom vrednošću $x_{k+1}$ ne vodi do rešenja. Ako algoritam to može dokazati, onda će odmah razmatrati druge vrednosti za $x_{j}$ umesto razmatranja $x_{k}$.

Primer u kome dodavanje na $x_{1}x_{2}x_{3}x_{4}$ nije bilo uspešno ni sa jednom mogućom vrednošću za $x_{5}$. Bektreking se vraća na $x_{4}$, i pokušava da joj promeni vrednost.	Umesto bektrekinga, algoritam vrši dalju razradu, dokazujući da $x_{1}x_{2}x_{5}=211$, $x_{1}x_{5}=22$, i $x_{1}x_{2}x_{5}=213$ nisu delovi nijednog rešenja.	Kao rezultat, trenutna evaluacija $x_{1}x_{2}$ nije deo nijednog rešenja, pa algoritam može direktno da se vrati na $x_{2}$ i pokuša da joj dodeli drugu vrednost.

Efikasnost algoritma pretrage sa nehronološkim vraćanjem zavisi od toga koliko daleko se može vraćati. U idealnom slučaju, algoritam bi mogao da se vrati iz $x_{k+1}$ do bilo koje promenljive $x_{j}$ takve da $x_{1},\ldots ,x_{j}$ ne formira rešenje ni sa jednom vrednošću $x_{k+1}$. Ako je to slučaj, $j$ se zove siguran skok.

Nije uvek moguće utvrditi da li je skok siguran, jer su sigurni skokovi definisani u smislu skupa rešenja, a to je ono što algoritam pokušava da pronađe. U praksi, algoritmi pretrage sa nehronološkim vraćanjem koriste najniži indeks za koji mogu efikasno dokazati da je siguran skok. Različiti algoritmi koriste različite metode za utvrđivanje da li je skok sigran. Oni imaju različite troškove, ali se velika cena pronalaženja većeg sigurnog skoka može smanjiti redukovanom pretragom usled preskakanja delova stabla pretrage.

Pretraga sa nehronološkim vraćanjem na listovima

Najjednostavnije stanje u kome je moguća pretraga sa nehronološkim vraćanjem je kada je za sve vrednosti promenljive dokazano da su nekonzistentne bez daljeg grananja. Delimična evaluacija je konzistentna ako i samo ako zadovoljava sva ograničenja dodeljenih promenljivih, a u suprotnom je nekonzistentna. To može biti slučaj kada se konzistentno delimično rešenje ne može proširiti do konzistentnog kompletnog rešenja jer neke od nedodeljenih promenljivih ne mogu biti dodeljene bez narušavanja drugih ograničenja.

Stanje u kome su sve vrednosti date promenljive $x_{k+1}$ nekonzistentne sa trenutnim delimičnim rešenjem $x_{1},\ldots ,x_{k}=a_{1},\ldots ,a_{k}$ se zove list ćorsokak. To se dešava upravo kada je promenljiva $x_{k+1}$ list stabla pretrage.

Gaschnig-ov algoritam pretrage sa nehronološkim vraćanjem vrši skok unatrag samo u listu ćorsokaku. Drugim rečima, radi drugačije od bektrekinga samo kada su sve moguće vrednosti $x_{k+1}$ testirane i nekonzistentne bez potrebe za grananjem u drugu promenljivu.

Siguran skok se može naći jednostavno, za svaku vrednost $a_{k+1}$, traži se najkraći prefiks od $x_{1},\ldots ,x_{k}=a_{1},\ldots ,a_{k}$ nekonzistentan sa $x_{k+1}=a_{k+1}$. Drugim rečima, ako je $a_{k+1}$ moguća vrednost za $x_{k+1}$, algoritam proverava konzistentnost sledećih evaluacija:

$x_{1}=a_{1}$	...	$x_{k-1}=a_{k-1}$	$x_{k}=a_{k}$	$x_{k+1}=a_{k+1}$
$x_{1}=a_{1}$	...	$x_{k-1}=a_{k-1}$		$x_{k+1}=a_{k+1}$
...
$x_{1}=a_{1}$				$x_{k+1}=a_{k+1}$

Najmanji indeks (najniži unos) za koji su evaluacije nekonzistentne bi bio siguran skok da su $x_{k+1}=a_{k+1}$ jedine moguće vrednosti za $x_{k+1}$. Pošto svaka promenljiva obično može imati više od jedne vrednosti, maksimalan indeks koji je dobijen proverom za svaku vrednost je siguran skok, i to je tačka u koju skače Gaschnig-ov algoritam.

U praksi, algoritam može da ispita evaluacije iznad dok proverava konzistentnost $x_{k+1}=a_{k+1}$.

Pretraga sa nehronološkim vraćanjem na unutrašnjim čvorovima

Prethodni algoritam vrši nehronološko vraćanje samo kada se vrednosti promenljive mogu pokazati nekonzistentne sa trenutnim delimičnim rešenjem bez daljeg grananja. Drugim rečima, dozvoljava se nehronološko vraćanje samo na listovima u stablu pretrage.

Unutrašnji čvor stabla pretrage predstavlja dodeljenu promenljivu koja je konzistentna sa prethodnim. Ako ta dodela ne daje nijedno rešenje, prethodni algoritam uvek vrši bektreking: nijedno nehronološko vraćanje neće biti izvršeno u tom slučaju.

Pretraga sa nehronološkim vraćanjem na unutrašnjim čvorovima ne može da se izvrši kao na listovima. Zaista, ako neke evaluacije od $x_{k+1}$ zahtevaju grananje, to je zato što su konzistentne sa trenutnom dodelom. Kao rezultat, potraga za prefiksom koji je nekonzistentan sa ovim vrednostima poslednje promenljive nije uspešna.

U takvim slučajevima, ono što dokazuje da $x_{k+1}=a_{k+1}$ neće biti deo rešenja sa trenutnom delimičnom evaluacijom $x_{1},\ldots ,x_{k}$ je rekurzivna pretraga. Posebno, algoritam "zna" da nijedno rešenje ne postoji od tog trenutka zato što se vraća u taj čvor umesto da se zaustavi nakon što je pronašao rešenje.

Ovaj povratak je izazvan velikim brojem ćorsokaka, i ukazuje gde je algoritam dokazao da je delimično rešenje nekonzistentno. Da bi nastavio nehronočoško vraćanje, algoritam mora imati u vidu da rešenja nije moguće naći zbog tih ćorsokaka. Posebno, sigurni skokovi su indeksi prefiksa koji i dalje čine ćorsokake nekonzistentnim delimičnim rešenjima.

U ovom primeru, algoritam se vraća na $x_{k+1}$, nakon isprobavanja svih mogućih vrednosti, zbog tri crossed nekonzistentne tačke.	Druga tačka ostaje nekonzistentna čak i kada su vrednosti $x_{k+1}$ i $x_{k}$ uklonjene iz delimične evaluacije (uočiti da su vrednosti promenljive u deci)	Druge nekonzistentne evaluacije ostaju čak i bez $x_{k-2}$, $x_{k-1}$, i $x_{k}$	Algoritam može da se vrati na $x_{k-2}$ jer je to najmanja promenljiva koja održava sve nekonzistentnosti. Nova vrednost za $x_{k-2}$ će biti isprobana.

Drugim rečima, kada su sve vrednosti $x_{k+1}$ isprobane, algoritam može da se vrati na $x_{i}$ pod uslovom da je trenutna istinita evaluacija od $x_{1},\ldots ,x_{i}$ nekonzistentna sa svim istinitim evaluacijama od $x_{k+1},x_{k+2},...$ u listovima koji su potomci čvora $x_{k+1}$.

Pojednostavljenja

Dok tražimo mogući nehronološki skok za $x_{k+1}$ ili jednog od njegovih predaka, svi čvorovi u osenčenom području mogu biti zanemareni.

Zbog potencijalno velikog broja čvorova koji su u podstablu od $x_{k+1}$, informacija koja je neophodna da bi se bezbedno nehronološki vratilo od $x_{k+1}$, se prikuplja za vreme prolaska kroz njegovo podstablo. Pronalaženje sigurnog skoka može biti pojednostavljeno pomoću dva razmatranja. Prvo je da je algoritmu potreban siguran skok, ali i dalje može da radi sa skokom koji nije najviši mogući siguran skok.

Drugo je to da čvorovi u podstablu $x_{l}$, koji su bili preskočeni nehronološkim vraćanjem, mogu biti zanemareni za vreme traženja nehronološkog vraćanja za $x_{l}$. Preciznije, svi čvorovi preskočeni nehronološkim vraćanjem od čvora $x_{m}$ do čvora $x_{l}$ mogu biti zamenareni u odnosu na podstablo čiji je koren u $x_{m}$, kao i njihova ostala podstabla.

Zaista, ako se algoritam spusti od čvora $x_{l}$ do $x_{m}$ ali se nehronološki vrati do samog početka, onda bi umesto toga mogao da prođe direktno od $x_{l}$ do $x_{m}$. Zaista, nehronološko vraćanje ukazuje na to da su čvorovi između $x_{l}$ i $x_{m}$ stvarno od manje važnosti podstablu čiji je koren u $x_{m}$. Drugim rečima, nehronološko vraćanje ukazuje na to da je posećivanje oblasti stabla pretrage bila greška. Ovaj deo stabla pretrage može biti zanemaren uzimajući u obzir moguće nehronološko vraćanje od $x_{l}$ ili jednog od njegovih predaka.

Promenljive čije su vrednosti dovoljne da dokažu nepravilnost u podstablu čiji se koren nalazi u čvoru bivaju pokupljene u čvoru i poslate, pri povlačenju, (nakon brisanja promenljivih u čvoru) čvoru iznad.

Ova činjenica može biti iskorišćena prikuljanjem, u svakom čvoru, skupa od prethodno dodeljenih promenljivih čija evaluacija ne može da dokaže da ne postoji rešenje u podstablu čiji je koren u čvoru. Ovaj skup se pravi za vreme rada algoritma. Pri povlačenju iz čvora, ovaj skup se briše zajedno sa promenljivom čvora i prikuplja se u skupu odredišta bektrekinga ili nehronološkog vraćanja. Pošto se čvorovi koji su preskočeni nehronološkim vraćanjem ne mogu povući, njihovi skupovi se automatski ignorišu.

Grafovski zasnovano nehronološko vraćanje

Obrazloženje grafovski zasnovanog nehronološkog vraćanja je u tome da siguran skok može biti pronađen proverom da li su promenljive $x_{1},\ldots ,x_{k}$ konzistentne sa promenljivama $x_{k+1},x_{k+2},...$ koje su instancirane u listovima. Za svaki levi list i svaku promenljivu $x_{i}$ za indeks $i>k$ koji je instanciran, indeksi manji ili jednaki $k$ čija je promenljiva konzistentna sa $x_{i}$, mogu biti korišćeni za pronalaženje sigurnog skoka. Naročito, kada su sve vrednosti za $x_{k+1}$ isprobane, ovaj skup sadrži indekse svih promenljivih čije evaluacije uspevaju da dokažu da ne postoji rešenje koje može biti pronađeno posećivanjem podstabla čiji je koren u $x_{k+1}$. Kao rezultat, algoritam se može nehronološki vratiti u najveći indeks u skupu.

Činjenica je da čvorovi preskočeni nehronološkim vraćanjem mogu biti zanemareni uzimajući u obzir da dalje nehronološko vraćanje može biti eksploatisano navedenim algoritmom. Pri povlačenju iz lista, skup promenljivih koje ograničene sa njim biva kreiran i "poslat nazad" do njegovog roditelja, ili pretka u slučaju nehronološkog vraćanja. Skup promenljivih se održava na svakom unutrašnjem čvoru. Svaki put kada se skup promenljivih dobije od deteta ili potomka, njihove vrednosti se dodaju u održavani skup. Pri daljem bektrekingu ili nehronološkom vraćanju od čvora, promenljiva čvora se uklanja iz skupa, i skup se šalje do čvora odredišta bektrekinga ili nehronološkog vraćanja. Ovaj algoritam radi jer održavani skup u čvoru skuplja sve promenljive bitne za dokazivanje nepravilnosti u listovama koji su potomci čvora. Pošto se skupovi promenljivih šalju samo za vreme povlačenja iz čvorova, skupovi sakupljeni na čvorovima preskočenim nehronološkim vraćanjem bivaju zanemareni.

Nehronološko vraćanje zasnovano na sukobima

Prerađeni algoritam sa nehronološkim vraćanjem, koji može da postigne veće nehronološko vraćanje, je baziran ne samo na proveravanju prisustva dve promenljive u istom ograničenju već i na proveravanju da li je ograničenje izazvalo nekonzistentnost. Naročito, ovaj algoritam prikuplja jedno od narušenih ograničenja u svakom listu. U svakom čvoru najveći indeks promenljive koji je u jednom od ograničenja, prikupljen na listovima, predstavlja siguran skok.

Narušeno ograničenje odabrano u svakom listu ne utiče na bezbednost rezultujućeg skoka. Biranje ograničenja najvećeg mogućeg indeksa povećava visinu skoka. Iz ovog razloga, nehronološko vraćanje zasnovano na sukobu numeriše ograničenja na takav način da su manji indeksi većeg prioriteta u odnosu na ograničenja većih indeksa.

Formalno, ograničenje $C$ je većeg prioriteta u odnosu na $D$ ako su najveći indeksi promenljive u $C$ manji u odnosu na najveće indekse promenljive u $D$. Drugim rečima, izuzimajući zajedničke promenljive, ograničenje koje ima sve manje indekse ima veći prioritet.

Na listu, algoritam bira najmanji indeks $i$ tako da su $x_{1},\ldots ,x_{i}$ nekonzistentni sa poslednjnom evaluiranom promenljivom na listu.

Među ograničenjima koja su narušena u evaluaciji, algoritam bira ono sa najvećim prioritetom, i prikuplja sve njegove indekse manje od $k+1$. Na ovaj način, kada se algoritam vrati do promenljive $x_{k+1}$, najmanji prikupljeni indeks predstavlja siguran skok.

U praksi, algoritam je pojednostavljen tako što prikuplja sve indekse u jednan skup, umesto kreiranja skupa za svaku vrednost $k$. Naročito, algoritam prikuplja, u svakom čvoru, sve skupove koji dolaze od njihovih potomaka koji nisu bili preskočeni nehronološkim vraćanjem. Pri povlačenju iz ovog čvora, skup zajedno sa promenljivom se briše iz čvora i prikuplja se u odredištu bektrekinga ili nehronolškog vraćanja.

Literatura

• Dechter, Rina (2003). Constraint Processing. Morgan Kaufmann. ISBN 978-1-55860-890-0. 
• Prosser, Patrick (1993). Hybrid Algorithms for the Constraint Satisfaction Problem (PDF). Computational Intelligence 9(3). Arhivirano iz originala (PDF) 06. 02. 2012. g. Pristupljeno 12. 05. 2016.