Задача о точном покрытии и алгоритм X | Комплект 1

Если вы когда-либо пытались создать программу для решения судоку, вы могли столкнуться с проблемой Exact Cover . В этой статье мы обсудим, какова точная проблема покрытия и алгоритм «Алгоритм X», предложенный Дональдом Кнутом для решения этой проблемы.

Учитывая набор S подмножеств множества X , точное покрытие - это подмножество S * в S, такое, что каждый элемент X содержится, является ровно одним подмножеством S *. Он должен удовлетворять следующим двум условиям -

• Пересечение любых двух подмножеств в S * должно быть пустым. То есть каждый элемент X должен содержаться не более чем в одном подмножестве S *.
• Объединение всех подмножеств в S * есть X. Это означает, что объединение должно содержать все элементы в множестве X. Таким образом, мы можем сказать, что S * покрывает X.

Пример (стандартное представление) -
Пусть S = {A, B, C, D, E, F} и X = {1, 2, 3, 4, 5, 6, 7} такие, что -

• А = {1, 4, 7}
• B = {1, 4}
• C = {4, 5, 7}
• D = {3, 5, 6}
• E = {2, 3, 6 7}
• F = {2, 7}

Тогда S * = {B, D, F} - точное покрытие, потому что каждый элемент X содержится ровно один раз в подмножествах {B, D, F}. Если мы объединим подмножества, мы получим все элементы X -
[Tex] B bigcup D bigcup F = {1,2,3,4,5,6,7 } [ Tex]

Проблема точного покрытия - это проблема решения, позволяющая определить, существует ли точное покрытие или нет. Это считается NP-полной задачей.

Проблема может быть представлена в виде матрицы, где строка представляет подмножества S, а столбцы представляют элемент X. Вышеупомянутая проблема может быть представлена как -

матрица проблем

В контексте матричного представления наше точное покрытие - это такой выбор строк, в котором каждый столбец содержит только одну единицу среди выбранных строк. Итак, ниже мы видим, что в каждом столбце есть только одна единица среди выбранных строк B, D, F.

точное покрытие

Алгоритм X

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

Алгоритм X - это рекурсивный алгоритм поиска с возвратом в глубину. Он не является детерминированным по своей природе, что означает, что для одного и того же входа он может демонстрировать разное поведение в другом прогоне.
Ниже приведен псевдокод для алгоритма X -

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

Недетерминированный выбор r означает, что алгоритм копирует себя в подалгоритм. Каждый вспомогательный алгоритм наследует исходную матрицу A, но уменьшает ее по отношению к выбранному r (мы вскоре увидим это в примере)

Подалгоритм формирует дерево поиска с исходной проблемой в корне, и каждый уровень k имеет подалгоритм, соответствующий строкам, выбранным на предыдущем уровне (точно так же, как пространство поиска n-queen).

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

Пример
Рассмотрим приведенный выше пример, мы применим к нему алгоритм X, чтобы найти точное покрытие -

Уровень - 0
Шаг 1: Наша матрица не пуста, в ней есть столбцы, затем продолжаем
Шаг 2: Первый столбец с минимальным количеством единиц в нем - это C-1, поэтому мы выберем его.
Шаг 3: Строки A и B имеют 1 в C-1, поэтому они выбираются.

Итак, теперь алгоритм переходит к первой ветви на уровне 1.

Уровень - 1 (выберите строку A)
Шаг 4: выберите строку A и добавьте ее к частичным решениям
Шаг 5: строка A имеет 1 в столбцах 1, 4, 7.

C-1 имеет 1 в строках A и B, C-4 имеет 1 в A, B и C, C-7 имеет 1 в строках A, C, E и F.

Поэтому столбцы 1, 4, 7 и строки A, B, C, E и F следует удалить.

Шаг 1 - Матрица не пуста, продолжайте
Шаг 2 - Первый столбец с минимальным количеством единиц - это C-2.
Поскольку в столбце C-2 нет единиц, наш поиск завершится здесь безуспешно.
Теперь наш алгоритм вернется на уровень 0 и перейдет к строке B во второй ветви на уровне 1.

Уровень - 1 (выберите строку B)
Шаг - 4: Выберите строку B и добавьте ее к частичным решениям.
Шаг - 5: В строке B 1 в столбцах C-1 и C-4.

У C-1 единицы в строках A и B. C-4 имеют единицы в строках A, B и C.

Таким образом, C-1, C-2 и строки A, B, C будут удалены из матрицы.

Теперь повторяем алгоритм -
Шаг 1: матрица не пуста, продолжаем
Шаг 2: C-5 содержит минимальное количество единиц, поэтому он выбран.

Шаг-3: В строке D 1 на C-5, поэтому он выбран
Теперь алгоритм переходит к 1-й ветви на уровне 2 с матрицей, имеющей строки D, E и F.

Уровень-2 (выберите строку D)
Шаг 4: выбирается строка D и добавляется к частичному раствору.
Шаг 5: C-3, C-5, C-6 имеют 1 в строке D

В C-3 ряду D и E по 1, в C-5 ряду D - 1, а в C-6 ряду D, E - 1.

Итак, эти строки и столбцы должны быть удалены, и мы остались с матрицей, содержащей только строку F и столбец 2, 7.

Теперь повторим алгоритм -
Шаг 1: матрица не пуста, продолжайте
Шаг 2: C-2 - это первый столбец, имеющий минимальный номер, если в нем стоит 1. Итак, это выбрано
Шаг 3: В строке F 1 на C-2, поэтому он выбран.
Теперь алгоритм перейдет к первой ветви на уровне 3.

Уровень - 3 (Выбрать строку F)
Шаг 4: Строка F добавляется к частичному раствору.
Шаг 5: C-2 и C-7 имеют 1 в строке F.

C-2 имеет 1 в строке F, C-7 имеет 1 в строке F

Итак, C2, C7 и строка F должны быть удалены. После удаления у нас останется пустая матрица, так что наш поиск может здесь успешно закончиться и у нас есть точное покрытие {B, D, F}

субалгоритм откатывается на уровне 2, и поскольку на уровне 3 не осталось строки.
Далее он возвращается на уровень 1. Поскольку на уровне 1 не остается строки, наш алгоритм завершается.

В следующей статье мы обсудим, как эффективно реализовать DLX для решения Exact Cover.

использованная литература

• https://en.wikipedia.org/wiki/Exact_cover
• https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

Эта статья предоставлена Атулом Кумаром. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.