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

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

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

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

Если матрица A не имеет столбцов, текущее частичное решение является допустимым решением; завершиться успешно.
В противном случае выберите столбец c ( детерминированно ).
Выберем строку r такую, что A _{r , 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} и набором множеств = { A , B , C , D , E , F }, где : ${\ Displaystyle {\ mathcal {S}}}$

А = {1, 4, 7};
B = {1, 4};
С = {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 - Каждая из строк A и B имеет 1 в столбце 1 и, таким образом, выбирается (недетерминированно).

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

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

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

Шаг 5 - строка A имеет 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 в строках A и B ; столбец 4 имеет 1 в строках A , B и C ; и столбец 7 имеет 1 в строках , 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
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 и 4 стоит 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

Столбец 1 имеет 1 в строках A и B ; и столбец 4 имеет 1 в строках , B и C . Таким образом, строки A , 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 в строках D и E стоит 1 ; столбец 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 в столбцах 2 и 7 стоит 1:

	2	7
F	1	1

В столбце 2 в строке F стоит 1 ; и столбец 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 }. ${\ Displaystyle {\ mathcal {S}} ^ {*}}$

Реализации [ править ]

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

См. Также [ править ]

Ссылки [ править ]

^ ^a ^b Кнут, Дональд (2000). «Танцующие звенья». arXiv : cs / 0011047 .

Кнут, Дональд Э. (2000), «Танцующие связи», Дэвис, Джим; Роско, Билл; Вудкок, Джим (ред.), Millennium Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in Honor of Sir Tony Hoare , Palgrave, pp. 187–214, arXiv : cs / 0011047 , Bibcode : 2000cs .... ... 11047 КБ , ISBN 978-0-333-92230-9.

Внешние ссылки [ править ]

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

[knuth-1] Кнут, Дональд (2000). «Танцующие звенья». arXiv : cs / 0011047 .

[1]

vтеДональд Кнут
Публикации	Искусство программирования « Сложность песен » Компьютеры и набор текста Конкретная математика Сюрреалистические числа Вещи, о которых редко говорят компьютерные ученые Избранные статьи
Программного обеспечения	TeX Метафонт MIXAL ( MIX MMIX GNU MDK )
Шрифты	AMS Euler Компьютер Модерн Бетон Роман
Грамотное программирование	WEB CWEB
Алгоритмы	Алгоритм Кнута X Алгоритм завершения Кнута – Бендикса Алгоритм Кнута – Морриса – Пратта Кнут перемешать Переписка Робинсона – Шенстеда – Кнута Алгоритм Трабба Пардо – Кнута Обобщение алгоритма Дейкстры Алгоритм Knuth's Simpath
Другой	Танцы Links Проверка награды Кнута Приз Кнута Тест на мужчину или мальчика Четвертичная мнимая база -иллион Система мер и весов Potrzebie