Играјуће везе
У компјутерској науци, играјуће везе, познатије као DLX је техника која је препоручена од стране Доналда Кнута као ефикасан метод имплементације Кнутовог алгоритма Икс.[1] Алгоритам Икс је рекурзиван, недетерминистички, дубински, бек-трекинг алгоритам који проналази сва решења за проблем тачног омотача. Неки од познатијих проблема те врсте су проблем теселације, проблем n дама и судоку.
Техника је добила име играјуће везе због начина на који тај алгоритам функционише, због тога што везе "играју" са суседним везама у веома добро кореографисаном плесу. Име су осмислили јапански информатичари Хироши Хитотумату и Кохеи Ношита 1979. године,[2] али је Кнут популаризовао овај назив.
Имплементација
[уреди | уреди извор]Идеја DLX се заснива на томе да у дупло повезаној кружној листи
x.levo.desno ← x.desno;
x.desno.levo ← x.levo;
избацује чвор x из листе, а
x.levo.desno ← x;
x.desno.levo ← x;
враћа x у листу.
Ово важи чак иако је број чворова у листи једнак 1.
У наивној имплементацији алгоритма икс, превише времена се троши на тражењу јединица у матрици, јер када изаберемо једну колону, јединице се траже у целој матрици, када се бира ред, јединице се траже у целој колони, а пошто изаберемо ред, у том реду и у више колона тражимо јединице.
Да би се сложеност ове претраге смањио од О(н) на О(1), Кнут је имплементирао ретку матрицу, то јест матрицу у којој су само 1 и 0.
Свака јединица у тој матрици садржи показивач на јединице лево и десно од себе, и изнад и испод себе и на заглавље колоне. Тако се матрица састоји од кружно повезаних листа које чине редове и колоне.
Колоне
[уреди | уреди извор]Свака колона у DLX има своје заглавље која заједно чине први ред матрице. Свако заглавље колоне може да чува број елемената у својој колони тако да налажење колоне са најмање елемената буде сложености О(n) уместо О(n*m) где је n број колона, а m број редова матрице.
У Алгоритму Икс, редови и колоне се стално уклањају и поново уписују у матрицу. Ако се изабере колона која нема редове у себи, проблем је нерешив и морамо бек-трековати. У елиминисаном реду, свака колона која је имала 1 у том реду се брише заједно са свим редовима који имају 1 у тим колонама.
Референце
[уреди | уреди извор]- ^ Knuth, Donald (2000). „Dancing links”. Millenial Perspectives in Computer Science. P159. 187. arXiv:cs/0011047
. Архивирано из оригинала 21. 04. 2017. г. Приступљено 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.
Спољашње везе
[уреди | уреди извор]
- A distributed Dancing Links implementation as a Hadoop MapReduce example