1. Method for solving exact cover problem
- Author
-
Lakoš, Antonio and Nakić, Anamari
- Subjects
egzaktno prekrivanje ,DLX ,dizajn ,TEHNIČKE ZNANOSTI. Računarstvo ,design ,exact cover problem ,algoritam X ,Steinerov dizajn ,TECHNICAL SCIENCES. Computing ,algorithm x ,Steiner system ,exact cover ,problem egzaktnog prekrivanja ,dancing links ,cover ,pokrivač - Abstract
Problem potpunog prekrivanja razmatramo u kontekstu računalne konstrukcije (v, k, 1)-dizajna. Potrebno je pronaći k-člane blokove dizajna koji ujedno tvore egzaktno pokrivanje nad skupom parova svih točaka. Za traženje pokrivača koristimo algoritam X, algoritam kojeg je osmislio Donald Knuth. Knuthova implementacija oslanja se na metodu "dancing links". Program implementation of Donald Knuth's algorithm X is used to solve an exact cover problem for (v, k, 1)-designs. Algorithm finds k-sized subsets called blocks which cover a set of point pairs. Algorithm X is implemented using "dancing links" method.
- Published
- 2021