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, ali je Knut popularizovao ovaj naziv.[2]
Implementacija
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
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
- ↑ Knuth, Donald (2000). „Dancing links”. Millenial Perspectives in Computer Science. P159 187. arXiv:cs/0011047. Arhivirano iz originala na datum 2017-04-21. Pristupljeno 2006-07-11.
- ↑ 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
Portal Informatika |
- A distributed Dancing Links Arhivirano 2010-12-06 na Wayback Machine-u implementation as a Hadoop MapReduce example
- C# implementation of an Exact Cover solver Arhivirano 2012-03-23 na Wayback Machine-u - uses Algorithm X and the Dancing Links trick.