Кіріспе
Нақты қаптама мәселесінің алгоритмі
X алгоритмі – нақты қаптама мәселесін шешуге арналған алгоритм. Бұл тікелей рекурсивті, нондетерминистік, тереңдікке басты, кері іздеу алгоритмі, оны Дональд Кнут DLX деп аталатын тиімді іске асыруды көрсету үшін қолданды, ол байланысты тізбектер техникасын пайдаланады. Нақты қаптама мәселесі X алгоритмінде 0 және 1-ден тұратын A матрицасымен бейнеленеді. Мақсат – әр бағанда 1 саны дәл бір рет кездесетін қатарлардың ішкі жиынын таңдау. X алгоритмі келесідей жұмыс істейді: r-дың нондетерминистік таңдауы алгоритмнің тәуелсіз субальгоритмдерге рекурсия жасауын білдіреді; әрбір субальгоритм ағымдағы матрицаны мұралайды, бірақ оны басқа r қатарына қатысты қысқартады. Егер c бағаны толығымен нөлдерден тұрса, онда субальгоритмдер жоқ және процесс сәтсіз аяқталады. Субальгоритмдер табиғи түрде іздеу ағашын құрайды, бастапқы мәселе түбінде, ал k деңгейі k таңдалған қатарларға сәйкес келетін әрбір субальгоритмді қамтиды. Кері іздеу – бұл ағашты алдын ала ретпен, тереңдікке басты өту процесі. Осы процедурада c бағанын таңдаудың кез келген жүйелі ережесі барлық шешімдерді табады, бірақ кейбір ережелер басқаларына қарағанда тиімдірек жұмыс істейді. Итерациялар санын азайту үшін Кнут бағанды таңдау алгоритмінің 1 санының ең аз саны бар бағанды таңдауын ұсынады.
Algorithm X is an algorithm for solving the exact cover problem. It is a straightforward recursive, nondeterministic, depth first, backtracking algorithm used by Donald Knuth to demonstrate an efficient implementation called DLX, which uses the dancing links technique. The exact cover problem is represented in Algorithm X by a matrix A consisting of 0s and 1s. The goal is to select a subset of the rows such that the digit 1 appears in each column exactly once. Algorithm X works as follows:
The nondeterministic choice of r means that the algorithm recurses over independent subalgorithms; each subalgorithm inherits the current matrix A, but reduces it with respect to a different row r.
If column c is entirely zero, there are no subalgorithms and the process terminates unsuccessfully. The subalgorithms form a search tree in a natural way, with the original problem at the root and with level k containing each subalgorithm that corresponds to k chosen rows. Backtracking is the process of traversing the tree in preorder, depth first. Any systematic rule for choosing column c in this procedure will find all solutions, but some rules work much better than others. To reduce the number of iterations, Knuth suggests that the column choosing algorithm select a column with the smallest number of 1s in it.
Қолданылу
Кнуттың X алгоритмін сипаттаудағы басты мақсаты – билеуші сілтемелердің тиімділігін көрсету болды. Кнут X алгоритмін компьютерде "DLX" деп аталатын процесте билеуші сілтемелерді пайдалану арқылы тиімді жүзеге асыруға болатынын көрсетті. DLX нақты жабу мәселесінің матрицалық бейнелеуін қолданады, ол матрицаның 1-дерінің екі жақты тізімдері ретінде іске асырылған: әрбір 1 элемент жоғарыда, төменде, солда және оңдағы келесі 1 элементке сілтеме береді. (Техникалық тұрғыдан алғанда, тізімдер циклдық болғандықтан, бұл тор құрайды). Нақты жабу мәселелері көбінесе сиректетілгендіктен, бұл бейнелеу көбінесе өлшем және өңдеу уақыты тұрғысынан әлдеқайда тиімді болады. DLX содан кейін қатарлардың мүмкін болатын шешімдер ретіндегі пермутацияларын жылдам таңдау және қате болжамдарды тиімді түрде кері қайтару (қайтару) үшін билеуші сілтемелерді пайдаланады.