Igrajuće veze

Izvor: Wikipedia

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.

Algoritam igrajućih veza rešava problem polikuba

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 - уреди]

  1. Knuth, Donald (2000). "Dancing links". Millenial Perspectives in Computer Science. P159 187. arXiv:cs/0011047. Retrieved 11. 7. 2006.. 
  2. 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 - уреди]