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

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

Алгоритм

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

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

Если в матрице A нет столбцов, текущее частичное решение является допустимым; завершить успешно.
В противном случае выберите столбец c ( детерминированно ).
Выберите строку r такую, что A _{r , c} = 1 ( недетерминировано ).
Включите строку r в частичное решение.
Для каждого столбца j такого, что A _{r , j} = 1,
для каждой строки i такой, что A _{i , j} = 1,
удалить строку из матрицы A. i
удалить столбец 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. Строка А включается в частичное решение.

Шаг 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 ; есть 1 в строках A , C , E и F. а в столбце 7 Таким образом, строки 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 ; есть 1 в строках A , B и C. а в столбце 4 строки 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. Наименьшее количество единиц в любом столбце — единица. Столбец 5 является первым столбцом с единицей и поэтому выбирается (детерминированно):

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

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

Алгоритм переходит к первой ветви на уровне 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

стоит 1 В столбце 3 в строках D и E ; в столбце 5 стоит 1 в строке D ; стоит 1 а в столбце 6 в строках 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. Наименьшее количество единиц в любом столбце — единица. Столбец 2 является первым столбцом с единицей 1 и поэтому выбирается (детерминированно):

	5	7
Ф	1	1

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

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

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

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

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

	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 ^* знак равно { Б , D , F }.

Реализации

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

См. также

Ссылки

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

Кнут, Дональд Э. (2000), «Танцевальные связи», Дэвис, Джим; Роско, Билл; Вудкок, Джим (ред.), «Перспективы тысячелетия в области компьютерных наук: материалы симпозиума Оксфорд-Майкрософт 1999 года в честь сэра Тони Хоара» , Пэлгрейв, стр. 187–214, arXiv : cs/0011047 , Bibcode : 2000cs.... ...11047K , ISBN 978-0-333-92230-9 .

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

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

[knuth-1] Jump up to: ^а ^б Кнут, Дональд (2000). «Танцевальные звенья». arXiv : cs/0011047 .

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

[1]

[2]

v т и Дональд Кнут
Публикации	Искусство компьютерного программирования « Сложность песен » Компьютеры и набор текста Конкретная математика Сюрреалистические числа Вещи, о которых редко говорит компьютерный ученый Серия избранных статей
Программное обеспечение	ТеХ Метафонт ОБРАЗЕЦ ( СМЕСЬ ММИКС )
Шрифты	АМС Эйлер Компьютер современный Бетонный римский
Грамотное программирование	ВЕБ ВЕБ-САЙТ
Алгоритмы	Алгоритм Кнута X Алгоритм завершения Кнута – Бендикса Алгоритм Кнута – Морриса – Пратта Кнут перетасовать Переписка Робинсона-Шенстеда-Кнута Алгоритм Трабба Пардо – Кнута Обобщение алгоритма Дейкстры. Алгоритм Кнута Simpath
Другой	Танцевальные ссылки Чек на награду Кнута Премия Кнута Обозначение Кнута со стрелкой вверх Тест мужчина или мальчик Четвертьмнимая база -иллион Система мер и весов Потшеби