Алгоритм Кнута X - Knuths Algorithm X
Алгоритм X является алгоритм для решения точное покрытие проблема. Это простой рекурсивный, недетерминированный, в глубину, возврат алгоритм, используемый Дональд Кнут чтобы продемонстрировать эффективную реализацию под названием DLX, которая использует танцевальные ссылки техника.[1]
Задача точного покрытия представлена в алгоритме X матрицей А состоящий из нулей и единиц. Цель состоит в том, чтобы выбрать такое подмножество строк, чтобы цифра 1 появлялась в каждом столбце ровно один раз.
Алгоритм X работает следующим образом:
- Если матрица А не имеет столбцов, текущее частичное решение является допустимым решением; завершиться успешно.
- В противном случае выберите столбец c (детерминированно ).
- Выберите строку р такой, что Ар, c = 1 (недетерминированно ).
- Включить строку р в частичном растворе.
- Для каждого столбца j такой, что Ар, j = 1,
- для каждой строки я такой, что Ая, j = 1,
- удалить строку я из матрицы А.
- удалить столбец j из матрицы А.
- для каждой строки я такой, что Ая, j = 1,
- Рекурсивно повторить этот алгоритм на приведенной матрице А.
Недетерминированный выбор р означает, что алгоритм рекурсивен по независимым подалгоритмам; каждый подалгоритм наследует текущую матрицу А, но уменьшает его относительно другой строки р.Если столбец c полностью равен нулю, подалгоритмов нет и процесс завершается неудачно.
Подалгоритмы образуют дерево поиска естественным образом, с изначальной проблемой в корне и с уровнем k содержащий каждый подалгоритм, соответствующий k выбранные строки. Обратное отслеживание - это процесс обхода дерева в предварительном порядке, сначала в глубину.
Любое систематическое правило выбора столбца c в этой процедуре будут найдены все решения, но некоторые правила работают намного лучше, чем другие. Чтобы уменьшить количество итераций, Кнут предлагает, чтобы алгоритм выбора столбца выбирал столбец с наименьшим количеством единиц в нем.
Пример
Например, рассмотрим проблему точного покрытия, заданную вселенной. U = {1, 2, 3, 4, 5, 6, 7} и набор множеств = {А, B, C, D, E, F}, куда:
- А = {1, 4, 7};
- B = {1, 4};
- C = {4, 5, 7};
- D = {3, 5, 6};
- E = {2, 3, 6, 7}; и
- F = {2, 7}.
Эта проблема представлена матрицей:
1 2 3 4 5 6 7 А 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
Алгоритм X с предложенной Кнутом эвристикой для выбора столбцов решает эту проблему следующим образом:
Уровень 0
Шаг 1 - матрица не пуста, поэтому алгоритм продолжается.
Шаг 2. Наименьшее количество единиц в любом столбце - два. Столбец 1 является первым столбцом с двумя единицами и, таким образом, выбран (детерминированно):
1 2 3 4 5 6 7 А 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
Шаг 3. Ряды А и B каждый из них имеет 1 в столбце 1 и, следовательно, выбран (недетерминированно).
Алгоритм переходит к первой ветви на уровне 1…
- Уровень 1: выберите строку А
- Шаг 4 - ряд А входит в частичное решение.
- Шаг 5 - ряд А имеет 1 в столбцах 1, 4 и 7:
1 2 3 4 5 6 7 А 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
- Столбец 1 имеет 1 в строках А и B; столбец 4 имеет 1 в строках А, B, и C; а столбец 7 имеет 1 в строках А, C, E, и F. Таким образом, строки А, B, C, E, и F удаляются и столбцы 1, 4 и 7 удаляются:
1 2 3 4 5 6 7 А 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
- Ряд D остается и столбцы 2, 3, 5 и 6 остаются:
2 3 5 6 D 0 1 1 1
- Шаг 1 - матрица не пуста, поэтому алгоритм продолжается.
- Шаг 2. Наименьшее количество единиц в любом столбце равно нулю, а столбец 2 - это первый столбец с нулевыми единицами:
2 3 5 6 D 0 1 1 1
- Таким образом, эта ветвь алгоритма завершается неудачно.
- Алгоритм переходит к следующей ветви на уровне 1…
- Уровень 1: выберите строку B
- Шаг 4 - ряд B входит в частичное решение.
- Ряд B имеет 1 в столбцах 1 и 4:
1 2 3 4 5 6 7 А 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
- Столбец 1 имеет 1 в строках А и B; а столбец 4 имеет 1 в строках А, B, и C. Таким образом, строки А, B, и C удаляются и столбцы 1 и 4 удаляются:
1 2 3 4 5 6 7 А 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
- Рядов D, E, и F остаются, а столбцы 2, 3, 5, 6 и 7 остаются:
2 3 5 6 7 D 0 1 1 1 0 E 1 1 0 1 1 F 1 0 0 0 1
- Шаг 1 - матрица не пуста, поэтому алгоритм продолжается.
- Шаг 2 - Наименьшее количество единиц в любом столбце - единица. Столбец 5 является первым столбцом с единицей 1 и поэтому выбран (детерминированно):
2 3 5 6 7 D 0 1 1 1 0 E 1 1 0 1 1 F 1 0 0 0 1
- Шаг 3 - ряд D имеет 1 в столбце 5 и поэтому выбран (недетерминированно).
- Алгоритм переходит к первой ветви на уровне 2…
- Уровень 2: выберите строку D
- Шаг 4 - ряд D входит в частичное решение.
- Шаг 5 - ряд D имеет 1 в столбцах 3, 5 и 6:
2 3 5 6 7 D 0 1 1 1 0 E 1 1 0 1 1 F 1 0 0 0 1
- Столбец 3 имеет 1 в строках D и E; столбец 5 имеет 1 в строке D; а столбец 6 имеет 1 в строках D и E. Таким образом, строки D и E должны быть удалены и столбцы 3, 5 и 6 должны быть удалены:
2 3 5 6 7 D 0 1 1 1 0 E 1 1 0 1 1 F 1 0 0 0 1
- Ряд F остается и столбцы 2 и 7 остаются:
2 7 F 1 1
- Шаг 1 - матрица не пуста, поэтому алгоритм продолжается.
- Шаг 2 - Наименьшее количество единиц в любом столбце - единица. Столбец 2 является первым столбцом с единицей 1 и поэтому выбран (детерминированно).
- Ряд F имеет 1 в столбце 2 и поэтому выбран (недетерминированно).
- Алгоритм переходит к первой ветви на уровне 3…
- Уровень 3: выберите строку F
- Шаг 4 - ряд F входит в частичное решение.
- Ряд F имеет 1 в столбцах 2 и 7:
2 7 F 1 1
- Столбец 2 имеет 1 в строке F; а столбец 7 имеет 1 в строке F. Таким образом строка F удалить и столбцы 2 и 7 удалить:
2 7 F 1 1
- Шаг 1 - матрица пуста, поэтому эта ветвь алгоритма успешно завершается.
- Рядами B, D, и F выбраны, окончательное решение:
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
- Другими словами, подколлекция {B, D, F} является точным покрытием, поскольку каждый элемент содержится ровно в одном из множеств B = {1, 4}, D = {3, 5, 6} или F = {2, 7}.
- На уровне 3 больше нет выбранных строк, поэтому алгоритм переходит к следующей ветви на уровне 2…
- На уровне 2 больше нет выбранных строк, поэтому алгоритм переходит к следующей ветви на уровне 1…
- На уровне 1 больше нет выбранных строк, поэтому алгоритм переходит к следующей ветви на уровне 0…
На уровне 0 нет ветвей, поэтому алгоритм завершается.
Таким образом, алгоритм определяет, что существует только одно точное покрытие: = {B, D, F}.
Реализации
Дональд Кнут Основная цель описания алгоритма X заключалась в демонстрации полезности ссылки на танцы. Кнут показал, что алгоритм X может быть эффективно реализован на компьютере, используя танцующие ссылки в процессе, который Кнут называет. "DLX". DLX использует матричное представление точное покрытие проблема, реализованная как двусвязные списки единиц матрицы: каждый 1 элемент имеет ссылку на следующую 1 сверху, снизу, слева и справа от себя. (Технически, поскольку списки круглые, это формирует тор ). Поскольку проблемы с точным покрытием обычно редки, такое представление обычно намного эффективнее как по размеру, так и по времени обработки. Затем DLX использует «танцующие» ссылки для быстрого выбора перестановок строк в качестве возможных решений и для эффективного отслеживания (отмены) ошибочных предположений.[1]
Смотрите также
Рекомендации
- ^ а б Кнут, Дональд (2000). «Танцующие звенья». arXiv:cs / 0011047.
- Кнут, Дональд Э. (2000), «Танцующие звенья», Дэвис, Джим; Роско, Билл; Вудкок, Джим (ред.), Перспективы тысячелетия в компьютерных науках: материалы симпозиума Оксфорд-Майкрософт 1999 г. в честь сэра Тони Хора, Palgrave, стр. 187–214, arXiv:cs / 0011047, Bibcode:2000cs ....... 11047K, ISBN 978-0-333-92230-9.
внешняя ссылка
- Бумага Кнута - PDF-файл (также arXiv:cs / 0011047 )
- Статья Кнута с описанием оптимизации танцующих ссылок - Postscript-файл в формате Gzip.