Играјуће везе

Из Википедије, слободне енциклопедије

У компјутерској науци, играјуће везе, познатије као DLX је техника која је препоручена од стране Доналда Кнута као ефикасан метод имплементације Kнутовог Алгоритма Икс.[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 у тим колонама.

Референце[уреди]

  1. ^ Knuth, Donald (2000). „Dancing links“. Millenial Perspectives in Computer Science. P159 187. arXiv:cs/0011047 Приступљено 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. 

Спољашње везе[уреди]