Igrajuće veze
U kompjuterskoj nauci, igrajuće veze, poznatije kao DLX je tehnika koja je preporučena od strane Donalda Knuta kao efikasan metod implementacije Knutovog algoritma Iks.[1] Algoritam Iks je rekurzivan, nedeterministički, dubinski, bek-treking algoritam koji pronalazi sva rešenja za problem tačnog omotača. Neki od poznatijih problema te vrste su problem teselacije, problem n dama i sudoku.
Tehnika je dobila ime igrajuće veze zbog načina na koji taj algoritam funkcioniše, zbog toga što veze "igraju" sa susednim vezama u veoma dobro koreografisanom plesu. Ime su osmislili japanski informatičari Hiroši Hitotumatu i Kohei Nošita 1979. godine,[2] ali je Knut popularizovao ovaj naziv.
Implementacija uredi
Ideja DLX se zasniva na tome da u duplo povezanoj kružnoj listi
x.levo.desno ← x.desno;
x.desno.levo ← x.levo;
izbacuje čvor x iz liste, a
x.levo.desno ← x;
x.desno.levo ← x;
vraća x u listu.
Ovo važi čak iako je broj čvorova u listi jednak 1.
U naivnoj implementaciji algoritma iks, previše vremena se troši na traženju jedinica u matrici, jer kada izaberemo jednu kolonu, jedinice se traže u celoj matrici, kada se bira red, jedinice se traže u celoj koloni, a pošto izaberemo red, u tom redu i u više kolona tražimo jedinice.
Da bi se složenost ove pretrage smanjio od O(n) na O(1), Knut je implementirao retku matricu, to jest matricu u kojoj su samo 1 i 0.
Svaka jedinica u toj matrici sadrži pokazivač na jedinice levo i desno od sebe, i iznad i ispod sebe i na zaglavlje kolone. Tako se matrica sastoji od kružno povezanih lista koje čine redove i kolone.
Kolone uredi
Svaka kolona u DLX ima svoje zaglavlje koja zajedno čine prvi red matrice. Svako zaglavlje kolone može da čuva broj elemenata u svojoj koloni tako da nalaženje kolone sa najmanje elemenata bude složenosti O(n) umesto O(n*m) gde je n broj kolona, a m broj redova matrice.
U Algoritmu Iks, redovi i kolone se stalno uklanjaju i ponovo upisuju u matricu. Ako se izabere kolona koja nema redove u sebi, problem je nerešiv i moramo bek-trekovati. U eliminisanom redu, svaka kolona koja je imala 1 u tom redu se briše zajedno sa svim redovima koji imaju 1 u tim kolonama.
Reference uredi
- ^ Knuth, Donald (2000). „Dancing links”. Millenial Perspectives in Computer Science. P159. 187. arXiv:cs/0011047 . Arhivirano iz originala 21. 04. 2017. g. Pristupljeno 11. 7. 2006.
- ^ Hitotumatu, Hirosi; Noshita, Kohei (1979). „A Technique for Implementing Backtrack Algorithms and its Application”. Information Processing Letters. 8 (4): 174—175. doi:10.1016/0020-0190(79)90016-4.
Spoljašnje veze uredi
- A distributed Dancing Links implementation as a Hadoop MapReduce example