Определение
Вот так точная проблема с обложкой распространяется на неосновные предметы на странице 7 (в настоящее время) из Pre-Fascicle 5C , Танцующие ссылки:
... проблема точного покрытия включает N различных элементов, из которых N1 являются первичными, а N2 = N - N1 вторичными.Он определяется семейством параметров, каждый из которых является подмножеством элементов. Каждый параметр должен включать хотя бы один основной элемент. Задача состоит в том, чтобы найти все подмножества параметров, которые (i) содержат каждый основной элемент ровно по одному, и (ii) содержат каждый дополнительный элемент не более одного раза.
(Опции, которые являются чисто вторичными, исключены из этого нового определения, потому что они никогда не будут выбраны алгоритмом X, как мы его уточнили. Если по какой-то причине вам не нравится это правило, вы всегда можете пойтиВернемся к идее слабых опций. В упражнении 19 обсуждается еще одна интересная альтернатива.)
На ваш вопрос отвечает подчеркнутое (Кнутом) предложение в первом абзаце и во втором абзаце.Точная проблема покрытия, решаемая Кнутом, запрещает (или игнорирует) опции, которые не помогают покрыть первичные предметы, то есть состоят исключительно из вторичных предметов.
Пример
В вашем примере ввопрос, давайте назовем столбцы A, B, C, где A вторична, а B и C первичны.Возможны следующие варианты:
[0, 1, 0] -- option 0: [B]
[0, 0, 1] -- option 1: [C]
[1, 0, 0] -- option 2: [A]
[1, 1, 0] -- option 3: [A, B]
[0, 1, 1] -- option 4: [B, C]
[1, 1, 1] -- option 5: [A, B, C]
Итак, третья строка [1 0 0], т. Е. Опция 2, не содержит основных элементов.
Вы можете запустить любую из программ Кнута DANCE или DLX1 со следующимивведите в файл (скажем) foo.dlx:
B C | A
B
C
A
A B
B C
A B C
Программы находят одинаковые четыре решения:
$ ./dance 1 < foo.dlx
1:
C (1 of 3)
B (1 of 2)
2:
C (1 of 3)
B A (2 of 2)
3:
C B (2 of 3)
4:
C A B (3 of 3)
Altogether 4 solutions, after 12 updates.
или
% ./dlx1 m1 < foo.dlx
Option ignored (no primary items): A
(5 options, 2+1 items, 14 entries successfully read)
1:
C (1 of 3)
B (1 of 2)
2:
C (1 of 3)
B A (2 of 2)
3:
C B (2 of 3)
4:
C A B (3 of 3)
Altogether 4 solutions, 261+231 mems, 12 updates, 360 bytes, 6 nodes.
(Примечаниеявное предупреждение во второй программе, что Вариант 2, который содержит только вторичный элемент A, игнорируется.)
Решение 1. Измените проблему
Если вы удалите параметры (строки), которыене содержат первичных элементов (столбцов), то программа уже работает: решения, которые вы получаете, действительно являются исчерпывающими для новой проблемы.
Решение 2: Варианты слабины
Как говорит Кнут во втором цитируемом сообщенииабзац (игнорируйте альтернативу Упражнения 19; она предназначена для решения другой проблемы), если вы действительно хотите включить опции, которые содержат только вторичные элементы, вы можете вернуться к идее слабых опций.В статье 2000 года эта идея является следующим предложением после цитируемого вами абзаца:
Обобщенную проблему покрытия можно преобразовать в эквивалентную задачу точного покрытия, если мы просто добавим одну строку для каждого вторичного столбца., содержащий один столбец в этом столбце.
(то есть для каждого вторичного элемента мы добавляем параметр, содержащий только этот элемент, и теперь рассматриваем его как проблему точного покрытия только с первичными элементами.)
Более подробно, я предполагаю, что вы хотите решить следующую проблему:
Есть N различных элементов (столбцов), некоторые из которых являются основными, а другиеявляются вторичными.
Существует несколько семейств опций (строк), каждый из которых представляет собой набор элементов (столбцов). Некоторые из них могут не содержать первичных элементов.
Найти все подмножества параметров, которые содержат каждый первичный элемент ровно один раз, а каждый вторичный элемент - не более одного раза.
Чтобы решить эту проблему, мы можем сделать следующее:
Среди заданных параметров (строк) определите те, которые содержат только вторичные элементы (колонны).Таким образом, вы берете набор всех заданных строк и делите его на два набора: один набор (назовите его X), в котором каждый параметр содержит хотя бы один первичный элемент, и один набор (назовите его Y), в котором каждый параметрсодержит только второстепенные элементы.
Для каждого вторичного элемента сформируйте параметр (строку), который содержит только этот элемент.Пусть Z будет набором всех таких опций из одного элемента (slack).
Теперь замените ваш список опций (X + Y) на (X + Y + Z), где + - это объединение: может быть некоторое перекрытие между Y и Z, но вы сохраните только одинкаждой опции.
Наконец, решите исходную проблему точного покрытия (ту, в которой все опции являются основными).Вы получите несколько решений.
Для каждого решения, которое вы получите,
первый выброс (игнорирование) каждого варианта, который не былв X или Y (т. е. это один из дополнительных параметров, которые вы добавили дополнительно)
из оставшихся параметров образуют набор Y 'параметров в решении, которые содержат только вторичные элементы.Пусть X 'будет оставшимся набором (то есть опциями в решении, которые содержат хотя бы один первичный элемент).
Добавить решение (X' union S) для каждого подмножества Y '.
В вашем примере в вопросе: X - это следующий набор:
[0, 1, 0] -- option 0: [B]
[0, 0, 1] -- option 1: [C]
[1, 1, 0] -- option 3: [A, B]
[0, 1, 1] -- option 4: [B, C]
[1, 1, 1] -- option 5: [A, B, C]
, а Y - следующий набор:
[1, 0, 0] -- option 2: [A]
и Z совпадает с Y, поэтому вам не нужно ничего добавлять в этом случае.
Вы решаете исходную проблему точного покрытия (все является первичным) и получаете следующеерешения:
[0, 1, 2].Здесь X '= [0, 1] и Y' = [2] и имеет два подмножества: пустое множество ([]) и сам Y ([2]).Поэтому добавьте два решения [0, 1] и [0, 1, 2].
[1, 3].Здесь X '= [1, 3] и Y' = [].Добавить раствор [1, 3].
[2, 4].Здесь X '= [4], а Y' = [2].Добавьте два решения [4] и [2, 4].
[5].Здесь X '= [5], а Y' = [].Добавьте решение [5].
Это даст все шесть решений.