Knuthsův algoritmus X - Knuths Algorithm X - Wikipedia

Algoritmus X je algoritmus pro řešení přesný obal problém. Je to přímočaré rekurzivní, nedeterministické, nejdříve do hloubky, ustoupit algoritmus používaný uživatelem Donald Knuth demonstrovat efektivní implementaci nazvanou DLX, která využívá taneční odkazy technika.^[1]

Přesný problém s krytem je v algoritmu X představován maticí A skládající se z 0 a 1 s. Cílem je vybrat podmnožinu řádků tak, aby se číslice 1 v každém sloupci objevila přesně jednou.

Algoritmus X funguje následovně:

Pokud je matice A nemá žádné sloupce, aktuální dílčí řešení je platným řešením; úspěšně ukončit.
Jinak vyberte sloupec C (deterministicky ).
Vyberte řádek r takhle A_{r, C} = 1 (nedeterministicky ).
Zahrnout řádek r v částečném řešení.
Pro každý sloupec j takhle A_{r, j} = 1,
pro každý řádek i takhle A_{i, j} = 1,
smazat řádek i z matice A.
smazat sloupec j z matice A.
Opakujte tento algoritmus rekurzivně na redukované matici A.

Nedeterministická volba r znamená, že se algoritmus opakuje přes nezávislé subalgoritmy; každý subalgoritmus dědí aktuální matici A, ale snižuje to s ohledem na jiný řádek r.Je-li sloupec C je zcela nula, neexistují žádné subalgoritmy a proces se neúspěšně ukončí.

Subalgoritmy tvoří a vyhledávací strom přirozeným způsobem, s původním problémem u kořene a na úrovni k obsahující každý subalgoritmus, který odpovídá k Backtracking je proces procházení stromu v předobjednávce, nejprve hloubka.

Jakékoli systematické pravidlo pro výběr sloupce C v tomto postupu najdete všechna řešení, ale některá pravidla fungují mnohem lépe než jiná. Chcete-li snížit počet iterací, Knuth navrhuje, aby algoritmus výběru sloupce vybral sloupec s nejmenším počtem 1 s.

Příklad

Zvažte například přesný problém s krytem specifikovaný vesmírem U = {1, 2, 3, 4, 5, 6, 7} a kolekce sad ${ displaystyle { mathcal {S}}}$ = {A, B, C, D, E, F}, kde:

A = {1, 4, 7};
B = {1, 4};
C = {4, 5, 7};
D = {3, 5, 6};
E = {2, 3, 6, 7}; a
F = {2, 7}.

Tento problém představuje matice:

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

Algoritmus X s Knuthovou heuristikou pro výběr sloupců řeší tento problém následovně:

Úroveň 0

Krok 1 - Matice není prázdná, takže algoritmus pokračuje.

Krok 2 - Nejnižší počet 1 s v libovolném sloupci jsou dva. Sloupec 1 je první sloupec se dvěma 1s a je tedy vybrán (deterministicky):

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

Krok 3 - Řádky A a B každý má ve sloupci 1 1, a proto jsou vybrány (nedeterministicky).

Algoritmus se přesune do první větve na úrovni 1…

Úroveň 1: Vyberte řádek A

Krok 4 - Řádek A je součástí dílčího řešení.

Krok 5 - Řádek A má 1 ve sloupcích 1, 4 a 7:

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

Sloupec 1 má 1 v řádcích A a B; sloupec 4 má 1 v řádcích A, B, a C; a sloupec 7 má 1 v řádcích A, C, E, a F. Tedy řádky A, B, C, E, a F budou odstraněny a sloupce 1, 4 a 7 budou odstraněny:

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

Řádek D pozůstatky a sloupce 2, 3, 5 a 6 zůstanou:

	2	3	5	6
D	0	1	1	1

Krok 1 - Matice není prázdná, takže algoritmus pokračuje.

Krok 2 - Nejnižší počet 1 s v libovolném sloupci je nula a sloupec 2 je první sloupec s nulou 1 s:

	2	3	5	6
D	0	1	1	1

Tato větev algoritmu tedy končí neúspěšně.

Algoritmus se přesune na další větev na úrovni 1…

Úroveň 1: Vyberte řádek B

Krok 4 - Řádek B je součástí dílčího řešení.

Řádek B má 1 ve sloupcích 1 a 4:

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

Sloupec 1 má 1 v řádcích A a B; a sloupec 4 má 1 v řádcích A, B, a C. Tedy řádky A, B, a C budou odstraněny a sloupce 1 a 4 budou odstraněny:

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

Řádky D, E, a F zůstávají a sloupce 2, 3, 5, 6 a 7 zůstávají:

	2	3	5	6	7
D	0	1	1	1	0
E	1	1	0	1	1
F	1	0	0	0	1

Krok 1 - Matice není prázdná, takže algoritmus pokračuje.

Krok 2 - Nejnižší počet 1 s v libovolném sloupci je jedna. Sloupec 5 je první sloupec s jednou 1 a je tedy vybrán (deterministicky):

	2	3	5	6	7
D	0	1	1	1	0
E	1	1	0	1	1
F	1	0	0	0	1

Krok 3 - Řádek D má 1 ve sloupci 5 a je tedy vybrán (nedeterministicky).

Algoritmus se přesune do první větve na úrovni 2…

Úroveň 2: Vyberte řádek D

Krok 4 - Řádek D je součástí dílčího řešení.

Krok 5 - Řádek D má 1 ve sloupcích 3, 5 a 6:

	2	3	5	6	7
D	0	1	1	1	0
E	1	1	0	1	1
F	1	0	0	0	1

Sloupec 3 má 1 v řádcích D a E; sloupec 5 má 1 v řádku D; a sloupec 6 má 1 v řádcích D a E. Tedy řádky D a E budou odstraněny a sloupce 3, 5 a 6 budou odstraněny:

	2	3	5	6	7
D	0	1	1	1	0
E	1	1	0	1	1
F	1	0	0	0	1

Řádek F pozůstatky a sloupce 2 a 7 zůstanou:

	2	7
F	1	1

Krok 1 - Matice není prázdná, takže algoritmus pokračuje.

Krok 2 - Nejnižší počet 1 s v libovolném sloupci je jedna. Sloupec 2 je první sloupec s jednou 1 a je tedy vybrán (deterministicky).

Řádek F má 1 ve sloupci 2 a je tedy vybrán (nedeterministicky).

Algoritmus se přesune do první větve na úrovni 3…

Úroveň 3: Vyberte řádek F

Krok 4 - Řádek F je součástí dílčího řešení.

Řádek F má 1 ve sloupcích 2 a 7:

	2	7
F	1	1

Sloupec 2 má 1 v řadě F; a sloupec 7 má 1 v řádku F. Tak řádek F bude odstraněn a sloupce 2 a 7 budou odstraněny:

	2	7
F	1	1

Krok 1 - Matice je prázdná, takže tato větev algoritmu úspěšně končí.

Jako řádky B, D, a F jsou vybrány, konečné řešení je:

	1	2	3	4	5	6	7
B	1	0	0	1	0	0	0
D	0	0	1	0	1	1	0
F	0	1	0	0	0	0	1

Jinými slovy, podkolekce {B, D, F} je přesný obal, protože každý prvek je obsažen přesně v jedné ze sad B = {1, 4}, D = {3, 5, 6} nebo F = {2, 7}.

Na úrovni 3 již nejsou žádné vybrané řádky, takže se algoritmus přesune do další větve na úrovni 2…

Na úrovni 2 již nejsou žádné vybrané řádky, takže se algoritmus přesune do další větve na úrovni 1…

Na úrovni 1 již nejsou vybrány žádné řádky, takže se algoritmus přesune do další větve na úrovni 0…

Na úrovni 0 nejsou žádné větve, proto se algoritmus ukončí.

Stručně řečeno, algoritmus určuje, že existuje pouze jeden přesný obal: ${ displaystyle { mathcal {S}} ^ {*}}$ = {B, D, F}.

Implementace

Donald Knuth Hlavním účelem popisu Algoritmu X bylo demonstrovat užitečnost taneční odkazy. Knuth ukázal, že Algoritmus X lze efektivně implementovat na počítači pomocí tanečních odkazů v procesu, který Knuth volá "DLX". DLX používá maticovou reprezentaci přesný obal problém, implementován jako dvojnásobně propojené seznamy z 1 matice: každý 1 prvek má odkaz na další 1 nahoře, dole, nalevo a napravo od sebe. (Technicky, protože seznamy jsou kruhové, tvoří to a torus ). Protože problémy s přesným krytím bývají řídké, je toto znázornění obvykle mnohem efektivnější jak z hlediska velikosti, tak z hlediska doby zpracování. DLX poté používá taneční odkazy k rychlému výběru permutací řádků jako možných řešení a k efektivnímu zpětnému odhadu (zpět) chybných odhadů.^[1]

Viz také

Reference

^ ^A ^b Knuth, Donald (2000). "Taneční odkazy". arXiv:cs / 0011047.

Knuth, Donald E. (2000), „Dancing links“, Davies, Jim; Roscoe, Bill; Woodcock, Jim (eds.), Millennial Perspectives in Computer Science: Proceedings of the Oxford-Microsoft Symposium 1999 in Honor of Sir Tony Hoare, Palgrave, s. 187–214, arXiv:cs / 0011047, Bibcode:2000 ks ....... 11047 tis, ISBN 978-0-333-92230-9.

externí odkazy

Knuthův papír - soubor PDF (také arXiv:cs / 0011047 )
Knuthova práce popisující optimalizaci Dancing Links - Postscriptový soubor Gzip'd.

[knuth-1] A ^b Knuth, Donald (2000). "Taneční odkazy". arXiv:cs / 0011047.

[1]

Donald Knuth
Publikace	Umění počítačového programování "Složitost písní " Počítače a sazba Konkrétní matematika Neskutečná čísla Věci, o kterých počítačový vědec zřídka mluví Vybrané série příspěvků
Software	TeX Metafont MIXÁLNÍ (SMĚS MMIX GNU MDK )
Písma	AMS Euler Počítač moderní Beton Roman
Literární programování	WEB CWEB
Algoritmy	Knuthův algoritmus X Algoritmus dokončení Knuth – Bendix Algoritmus Knuth – Morris – Pratt Knuth shuffle Korespondence Robinson – Schensted – Knuth Algoritmus Trabb Pardo – Knuth Zobecnění Dijkstrův algoritmus Knuthův algoritmus Simpath
jiný	Taneční odkazy Knuth odměna Knuth Prize Muž nebo chlapec test Čtvrtletně imaginární základna -yllion Potrzebie systém vah a měr