Knutov algoritam Iks

S Vikipedije, slobodne enciklopedije

Donald Knutov Algoritam Iks je rekurzivan, nedeterministički, dubinski, bek-treking algoritam koji nalazi sva rešenja problema tačnog omotača koji se predstavlja pomoću matrice A, koja se sastoji iz nula i jedinica. Algoritam radi tako što se odabire podskup redova u matrici A tako da se broj 1 pojavi u svakoj koloni podskupa tačno jednom.

Performanse[uredi | uredi izvor]

Najmanja granica performanse ovog algoritma je zavisno od maksimalnog broja tačnih omotača neke instance. Na primer, slučaj tačnog omotača formiranog od kocke 2x2 sa k čvornih kopija daje 7k različitih rešenja, formiranih od n=8k skupova, pa kao funkcija f(n), gde je n broj podskupova u početnoj familiji, broj tačnih omotača je 7n/8, što je približno 1.275n[1].

Gornje granice performansi se dostižu kada imamo tri rekurzivna poziva veličine n-3 što je O(3n/3).

Opis algoritma[uredi | uredi izvor]

1. korak:

Ako je matrica A prazna, to je ujedno i kraj problema i algoritam se završava uspešno. Ako nije, prelazimo na korak 2.

2. korak:

Biramo kolonu c.

3. korak:

Biramo red r tako da je Ar,c=1.

4. korak:

Red r unosimo u parcijalno rešenje.

5. korak:

Za svaku kolonu j takvu da je Ar, j=1 gledamo da li postoji red i takav da je Ar, j=1. Ako je odgovor potvrdan, brišemo taj red i prelazimo na sledeći red koliko ih ima. Pošto smo prošli kroz sve redove, brišemo kolonu j i ponavljamo korak 5 sve dok ne iscrpimo sve kolone matrice A.

6. korak:

Rekurzivno ponavljamo ove korake na novoj, smanjenoj matrici A.

Podalgoritmi[uredi | uredi izvor]

Odabir reda r u trećem koraku je nedeterministički problem, što znači da će biti pozvan podalgoritam odabira reda koji kao argument dobija prosleđenu matricu A iz koje izdvaja jedan red r. Problem nalaženja kolone c je deterministički, ali ako je nađena kolona c popunjena cela nulama, algoritam će se neuspešno završiti.

Ovi podalgoritmi formiraju binarno stablo pretrage sa prvobitnim problemom kao korenom, a gde k-ti nivo stabla odgovara k izabranih redova. Bektrekujemo kroz algoritam tako što obilazimo stablo dubinski u preorder-u.

Implementacija[uredi | uredi izvor]

Igrajuće veze, poznatije kao DLX su tehnika implementiranja Algoritma Iks koju je Knut sam razvio. Tom tehnikom se kreira matrica uz pomoć dvostruko povezane liste svih polja koja sadrže 1. Postoji odvojena lista za jedinice u svakom redu i koloni, a svaka jedinica u matrici je povezana sa sledećom jedinicom gore, levo, desno i dole od nje.