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. 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.

Algoritam igrajućih veza rešava problem polikuba

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.

Spoljašnje veze

• 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.