Кнутов алгоритам Икс

Доналд Кнутов Алгоритам Икс је рекурзиван, недетерминистички, дубински, бек-трекинг алгоритам који налази сва решења проблема тачног омотача који се представља помоћу матрице А, која се састоји из нула и јединица. Алгоритам ради тако што се одабире подскуп редова у матрици А тако да се број 1 појави у свакој колони подскупа тачно једном.

Перформансе

Најмања граница перформансе овог алгоритма је зависно од максималног броја тачних омотача неке инстанце. На пример, случај тачног омотача формираног од коцке 2x2 са k чворних копија даје 7^k различитих решења, формираних од n=8k скупова, па као функција f(n), где је n број подскупова у почетној фамилији, број тачних омотача је 7^n/8, што је приближно 1.275ⁿ[1] Arhivirano 2013-07-13 na Wayback Machine-u.

Горње границе перформанси се достижу када имамо три рекурзивна позива величине n-3 што је O(3^n/3).

Опис алгоритма

1. корак:

Ако је матрица А празна, то је уједно и крај проблема и алгоритам се завршава успешно. Ако није, прелазимо на корак 2.

2. корак:

Бирамо колону c.

3. корак:

Бирамо ред r тако да је А_r,c=1.

4. корак:

Ред r уносимо у парцијално решење.

5. корак:

За сваку колону ј такву да је А_{r, ј}=1 гледамо да ли постоји ред i такав да је А_{r, ј}=1. Ако је одговор потврдан, бришемо тај ред и прелазимо на следећи ред колико их има. Пошто смо прошли кроз све редове, бришемо колону ј и понављамо корак 5 све док не исцрпимо све колоне матрице А.

6. корак:

Рекурзивно понављамо ове кораке на новој, смањеној матрици А.

Подалгоритми

Одабир реда r у трећем кораку је недетерминистички проблем, што значи да ће бити позван подалгоритам одабира реда који као аргумент добија прослеђену матрицу А из које издваја један ред r. Проблем налажења колоне c је детерминистички, али ако је нађена колона c попуњена цела нулама, алгоритам ће се неуспешно завршити.

Ови подалгоритми формирају бинарно стабло претраге са првобитним проблемом као кореном, а где к-ти ниво стабла одговара к изабраних редова. Бектрекујемо кроз алгоритам тако што обилазимо стабло дубински у preorder-у.

Имплементација

Играјуће везе, познатије као DLX су техника имплементирања Алгоритма Икс коју је Кнут сам развио. Том техником се креира матрица уз помоћ двоструко повезане листе свих поља која садрже 1. Постоји одвојена листа за јединице у сваком реду и колони, а свака јединица у матрици је повезана са следећом јединицом горе, лево, десно и доле од ње.