Алгоритм Кнута X

Алгоритм для задачи точного покрытия

Алгоритм X — это алгоритм для решения задачи точного покрытия . Это простой рекурсивный , недетерминированный , глубинный алгоритм обратного поиска , который Дональд Кнут использовал для демонстрации эффективной реализации под названием DLX, использующей технику танцующих связей . ^[1]^[2]

Алгоритм

Точная задача покрытия представлена в алгоритме X матрицей инцидентности A, состоящей из нулей и единиц. Цель состоит в том, чтобы выбрать подмножество строк таким образом, чтобы цифра 1 появлялась в каждом столбце ровно один раз.

Алгоритм X работает следующим образом:

Если матрица A не имеет столбцов, текущее частичное решение является допустимым решением; завершить успешно.
В противном случае выберите столбец c ( детерминированно ).
Выберите строку r так, чтобы _Ar , _c₌ 1 ( недетерминировано ).
Включите строку r в частичное решение.
Для каждого столбца j такого, что A _{r , j} = 1,
для каждой строки i такой, что A _{i , j} = 1,
удалить строку i из матрицы A.
удалить столбец j из матрицы A.
Повторите этот алгоритм рекурсивно на редуцированной матрице A.

Недетерминированный выбор r означает, что алгоритм рекурсивно выполняет независимые подалгоритмы; каждый подалгоритм наследует текущую матрицу A , но уменьшает ее относительно другой строки r . Если столбец c полностью равен нулю, подалгоритмов нет, и процесс завершается неудачно.

Подалгоритмы образуют дерево поиска естественным образом, с исходной проблемой в корне и с уровнем k, содержащим каждый подалгоритм, который соответствует k выбранным строкам. Обратный поиск — это процесс обхода дерева в прямом порядке, сначала в глубину.

Любое систематическое правило выбора столбца c в этой процедуре найдет все решения, но некоторые правила работают намного лучше других. Чтобы сократить количество итераций, Кнут предлагает, чтобы алгоритм выбора столбца выбирал столбец с наименьшим количеством единиц в нем.

Пример

Например, рассмотрим точную задачу покрытия, заданную вселенной U = {1, 2, 3, 4, 5, 6, 7} и набором множеств S = { A , B , C , D , E , F }, где:

А = {1, 4, 7};
В = {1, 4};
С = {4, 5, 7};
Д = {3, 5, 6};
Е = {2, 3, 6, 7}; и
Ф = {2, 7}.

Эта задача представлена матрицей:

	1	2	3	4	5	6	7
А	1	0	0	1	0	0	1
Б	1	0	0	1	0	0	0
С	0	0	0	1	1	0	1
Д	0	0	1	0	1	1	0
Э	0	1	1	0	0	1	1
Ф	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
Б	1	0	0	1	0	0	0
С	0	0	0	1	1	0	1
Д	0	0	1	0	1	1	0
Э	0	1	1	0	0	1	1
Ф	0	1	0	0	0	0	1

Шаг 3 — В строках A и B в столбце 1 содержится 1, поэтому они выбираются (недетерминированно).

Алгоритм переходит к первой ветви на уровне 1…

Уровень 1: Выберите строку A

Шаг 4 — Строка A включена в частичное решение.

Шаг 5 — В строке A в столбцах 1, 4 и 7 стоит 1:

	1	2	3	4	5	6	7
А	1	0	0	1	0	0	1
Б	1	0	0	1	0	0	0
С	0	0	0	1	1	0	1
Д	0	0	1	0	1	1	0
Э	0	1	1	0	0	1	1
Ф	0	1	0	0	0	0	1

В столбце 1 есть 1 в строках A и B ; в столбце 4 есть 1 в строках A , B и C ; а в столбце 7 есть 1 в строках A , C , E и F. Таким образом, строки A , B , C , E и F должны быть удалены, а столбцы 1, 4 и 7 должны быть удалены:

	1	2	3	4	5	6	7
А	1	0	0	1	0	0	1
Б	1	0	0	1	0	0	0
С	0	0	0	1	1	0	1
Д	0	0	1	0	1	1	0
Э	0	1	1	0	0	1	1
Ф	0	1	0	0	0	0	1

Остается строка D и столбцы 2, 3, 5 и 6:

	2	3	5	6
Д	0	1	1	1

Шаг 1 — Матрица не пуста, поэтому алгоритм продолжается.

Шаг 2 — Наименьшее количество единиц в любом столбце равно нулю, а столбец 2 — первый столбец с нулевым количеством единиц:

	2	3	5	6
Д	0	1	1	1

Таким образом, эта ветвь алгоритма завершается неудачно.

Алгоритм переходит к следующей ветви на уровне 1…

Уровень 1: Выберите строку B

Шаг 4 — Строка B включена в частичное решение.

В строке B в столбцах 1 и 4 стоит 1:

	1	2	3	4	5	6	7
А	1	0	0	1	0	0	1
Б	1	0	0	1	0	0	0
С	0	0	0	1	1	0	1
Д	0	0	1	0	1	1	0
Э	0	1	1	0	0	1	1
Ф	0	1	0	0	0	0	1

В столбце 1 есть 1 в строках A и B ; а в столбце 4 есть 1 в строках A , B и C. Таким образом, строки A , B и C должны быть удалены, а столбцы 1 и 4 должны быть удалены:

	1	2	3	4	5	6	7
А	1	0	0	1	0	0	1
Б	1	0	0	1	0	0	0
С	0	0	0	1	1	0	1
Д	0	0	1	0	1	1	0
Э	0	1	1	0	0	1	1
Ф	0	1	0	0	0	0	1

Остаются строки D , E и F , а также столбцы 2, 3, 5, 6 и 7:

	2	3	5	6	7
Д	0	1	1	1	0
Э	1	1	0	1	1
Ф	1	0	0	0	1

Шаг 1 — Матрица не пуста, поэтому алгоритм продолжается.

Шаг 2 — Наименьшее количество единиц в любом столбце равно 1. Столбец 5 — первый столбец с одной единицей и поэтому выбирается (детерминированно):

	2	3	5	6	7
Д	0	1	1	1	0
Э	1	1	0	1	1
Ф	1	0	0	0	1

Шаг 3 — В строке D в столбце 5 стоит 1, поэтому она выбрана (недетерминированно).

Алгоритм переходит к первой ветви на уровне 2…

Уровень 2: Выберите строку D.

Шаг 4 — Строка D включена в частичное решение.

Шаг 5 — В строке D в столбцах 3, 5 и 6 стоит 1:

	2	3	5	6	7
Д	0	1	1	1	0
Э	1	1	0	1	1
Ф	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
Д	0	1	1	1	0
Э	1	1	0	1	1
Ф	1	0	0	0	1

Остается строка F и столбцы 2 и 7:

	2	7
Ф	1	1

Шаг 1 — Матрица не пуста, поэтому алгоритм продолжается.

Шаг 2 — Наименьшее количество единиц в любом столбце равно 1. Столбец 2 — первый столбец с одной единицей и поэтому выбирается (детерминированно):

	2	7
Ф	1	1

В строке F в столбце 2 стоит 1, поэтому она выбрана (недетерминированно).

Алгоритм переходит к первой ветви на уровне 3…

Уровень 3: Выберите строку F

Шаг 4 — Строка F включена в частичное решение.

В строке F в столбцах 2 и 7 стоит 1:

	2	7
Ф	1	1

В столбце 2 есть 1 в строке F ; а в столбце 7 есть 1 в строке F. Таким образом, строка F должна быть удалена, а столбцы 2 и 7 должны быть удалены:

	2	7
Ф	1	1

Не осталось ни строк, ни столбцов:

Шаг 1 — Матрица пуста, поэтому эта ветвь алгоритма завершается успешно.

Поскольку строки B , D и F были выбраны (шаг 4), окончательное решение в этой ветви будет следующим:

	1	2	3	4	5	6	7
Б	1	0	0	1	0	0	0
Д	0	0	1	0	1	1	0
Ф	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 ветвей нет, поэтому алгоритм завершается.

Подводя итог, алгоритм определяет, что существует только одно точное покрытие: S ^* = { B , D , F }.

Реализации

Главной целью Кнута при описании алгоритма X было продемонстрировать полезность танцующих связей . Кнут показал, что алгоритм X может быть эффективно реализован на компьютере с использованием танцующих связей в процессе, который Кнут называет «DLX» . DLX использует матричное представление задачи точного покрытия , реализованное в виде двусвязных списков единиц матрицы: каждый элемент 1 имеет ссылку на следующую 1 выше, ниже, слева и справа от себя. (Технически, поскольку списки являются круговыми, это образует тор ). Поскольку задачи точного покрытия, как правило, разрежены, это представление обычно намного эффективнее как по размеру, так и по требуемому времени обработки. Затем DLX использует танцующие связи для быстрого выбора перестановок строк в качестве возможных решений и для эффективного отслеживания (отмены) ошибочных предположений. ^[1]

Смотрите также

Ссылки

^ ab Кнут, Дональд (2000). "Танцующие ссылки". arXiv : cs/0011047 .
^ Баннерджи, Бикрамджит; Крамер, Лэндон; Лайл, Джереми (2010-07-04). «Распознавание многоагентных планов: формализация и алгоритмы». Труды конференции AAAI по искусственному интеллекту . 24 (1): 1059– 1064. doi : 10.1609/aaai.v24i1.7746 . ISSN 2374-3468.

Knuth, Donald E. (2000), «Танцующие связи», в Davies, Jim; Roscoe, Bill; Woodcock, Jim (ред.), Millennial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare , Palgrave, стр. 187–214 , arXiv : cs/0011047 , Bibcode : 2000cs.......11047K, ISBN 978-0-333-92230-9.

Внешние ссылки

Статья Кнута - PDF-файл (также arXiv :cs/0011047)
Статья Кнута, описывающая оптимизацию Dancing Links — сжатый с помощью Gzip файл PostScript.

[knuth-1] Кнут, Дональд (2000). "Танцующие ссылки". arXiv : cs/0011047 .

[2] Баннерджи, Бикрамджит; Крамер, Лэндон; Лайл, Джереми (2010-07-04). «Распознавание многоагентных планов: формализация и алгоритмы». Труды конференции AAAI по искусственному интеллекту . 24 (1): 1059– 1064. doi : 10.1609/aaai.v24i1.7746 . ISSN 2374-3468.