stringtranslate.com

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

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

Алгоритм

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

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

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

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

Алгоритм X с предложенной Кнутом эвристикой выбора столбцов решает эту проблему следующим образом:

Уровень 0

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

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

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

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

Уровень 1: Выберите строку A
Шаг 4 — Строка A включена в частичное решение.
Шаг 5 — В строке A в столбцах 1, 4 и 7 стоит 1:
В столбце 1 есть 1 в строках A и B ; в столбце 4 есть 1 в строках A , B и C ; а в столбце 7 есть 1 в строках A , C , E и F. Таким образом, строки A , B , C , E и F должны быть удалены, а столбцы 1, 4 и 7 должны быть удалены:
Остается строка D и столбцы 2, 3, 5 и 6:
Шаг 1 — Матрица не пуста, поэтому алгоритм продолжается.
Шаг 2 — Наименьшее количество единиц в любом столбце равно нулю, а столбец 2 — первый столбец с нулевым количеством единиц:
Таким образом, эта ветвь алгоритма завершается неудачно.
Алгоритм переходит к следующей ветви на уровне 1…
Уровень 1: Выберите строку B
Шаг 4 — Строка B включена в частичное решение.
В строке B в столбцах 1 и 4 стоит 1:
В столбце 1 есть 1 в строках A и B ; а в столбце 4 есть 1 в строках A , B и C. Таким образом, строки A , B и C должны быть удалены, а столбцы 1 и 4 должны быть удалены:
Строки D , E и F остаются, а столбцы 2, 3, 5, 6 и 7 остаются:
Шаг 1 — Матрица не пуста, поэтому алгоритм продолжается.
Шаг 2 — Наименьшее количество единиц в любом столбце равно 1. Столбец 5 — первый столбец с одной единицей и поэтому выбирается (детерминированно):
Шаг 3 — В строке D в столбце 5 стоит 1, поэтому она выбрана (недетерминированно).
Алгоритм переходит к первой ветви на уровне 2…
Уровень 2: Выберите строку D.
Шаг 4 — Строка D включена в частичное решение.
Шаг 5 — В строке D в столбцах 3, 5 и 6 стоит 1:
В столбце 3 есть 1 в строках D и E ; в столбце 5 есть 1 в строке D ; и в столбце 6 есть 1 в строках D и E. Таким образом, строки D и E должны быть удалены, а столбцы 3, 5 и 6 должны быть удалены:
Остается строка F и столбцы 2 и 7:
Шаг 1 — Матрица не пуста, поэтому алгоритм продолжается.
Шаг 2 — Наименьшее количество единиц в любом столбце равно 1. Столбец 2 — первый столбец с одной единицей и поэтому выбирается (детерминированно):
В строке F в столбце 2 стоит 1, поэтому она выбрана (недетерминированно).
Алгоритм переходит к первой ветви на уровне 3…
Уровень 3: Выберите строку F
Шаг 4 — Строка F включена в частичное решение.
В строке F в столбцах 2 и 7 стоит 1:
В столбце 2 есть 1 в строке F ; а в столбце 7 есть 1 в строке F. Таким образом, строка F должна быть удалена, а столбцы 2 и 7 должны быть удалены:
Не осталось ни строк, ни столбцов:
Шаг 1 — Матрица пуста, поэтому эта ветвь алгоритма завершается успешно.
Поскольку строки B , D и F были выбраны (шаг 4), окончательное решение в этой ветви будет следующим:
Другими словами, подмножество { 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]

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

Ссылки

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

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