Введение
Алгоритм для решения задачи точного покрытия. Алгоритм X — это алгоритм для решения задачи точного покрытия. Это прямой рекурсивный, недетерминированный, с поиском в глубину, алгоритм с возвратом, используемый Дональдом Кнутом для демонстрации эффективной реализации под названием DLX, которая использует технику «танцующих связей». Задача точного покрытия в алгоритме X представлена матрицей A, состоящей из 0 и 1. Цель состоит в том, чтобы выбрать подмножество строк таким образом, чтобы цифра 1 встречалась в каждом столбце ровно один раз. Алгоритм X работает следующим образом: недетерминированный выбор строки r означает, что алгоритм рекурсивно перебирает независимые подзадачи; каждая подзадача наследует текущую матрицу A, но уменьшает её относительно другой строки r. Если столбец c полностью состоит из нулей, подзадач нет, и процесс завершается неудачно. Подзадачи образуют дерево поиска естественным образом, с исходной задачей в корне и уровнем k, содержащим каждую подзадачу, соответствующую k выбранным строкам. Возврат — это процесс обхода дерева в порядке предварительного просмотра, с поиском в глубину. Любое систематическое правило выбора столбца c в этой процедуре найдёт все решения, но некоторые правила работают значительно лучше других. Чтобы уменьшить количество итераций, Кнут предлагает, чтобы алгоритм выбора столбца выбирал столбец с наименьшим количеством единиц в нём.
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, имеет связь со следующей единицей выше, ниже, слева и справа от себя. (Строго говоря, поскольку списки замкнуты, это образует тор). Поскольку задачи точного покрытия обычно разрежены, такое представление обычно гораздо эффективнее как по объему, так и по времени обработки. Затем DLX использует "танцующие связи" для быстрого выбора перестановок строк в качестве возможных решений и эффективного возврата (отмены) ошибочных предположений.