Хорошо, я не могу обойтись 2 ^ N, но я могу уменьшить выборку. Для этого мы вычислим «Составные ограничения». Составное ограничение - это ограничение, при котором, если выбраны все параметры на левой стороне, тогда ни один из параметров на правой стороне не может быть выбран, но никакие другие ограничения, основанные на параметрах левой стороны, не могут применяться.
Нам нужно вычислить набор всех возможных составных ограничений из набора ограничений. Хотя это и не нужно, мы «исправим» существующие ограничения, поменяв местами левую и правую руки, если группа правой руки меньше, чем группа левой. Это может уменьшить некоторые составные ограничения, хотя возможна лучшая эвристика для замены.
Нам также необходимо вычислить «минимальный набор» опций, которые могут быть произвольно выбраны для каждой группы. Этот минимальный набор вычисляется путем удаления из списка доступных параметров любых параметров, появляющихся слева от составного ограничения.
Алгоритм следует, но я не доказываю, что он правильно вычисляет CC. Я докажу, что, если это так, то они могут быть использованы для вычисления количества возможных комбинаций.
- Исправьте ограничения так, чтобы группа левой руки была меньше или равна группе правой руки.
Составьте ограничения:
- Сортировка ограничений левой рукой
Последовательно, для каждого ограничения:
- Сложите ограничение со всеми последующими ограничениями одной и той же левой рукой, превратив
x1 <-> y1, x1 <-> y2 ... x1 <-> yN в Set(x1) <-> Set(y1 ... yN)
- Составьте сложенное ограничение с каждым уже сложенным ограничением, если:
- x1 находится не в правой части уже сложенного ограничения
- x1 не входит в ту же группу любого элемента в левой руке
- Добавить сложенное ограничение и все его композиции к набору свернутых ограничений
Вычислите минимальный набор, выбрав все параметры и удалив те, которые указаны в левой части фиксированных ограничений.
Теперь вы можете вычислить количество комбинаций по формуле ниже. Давайте назовем CC составным ограничением. Тогда количество комбинаций:
C(Mininum Set) + CCC1 + ... + CCCn
Где:
- C (Minimum Set) - количество возможных комбинаций с минимальным набором.
- CCCx - это число возможных комбинаций, взяв минимальный набор, заменив любые группы, для которых есть опция на левой стороне CCx, этой опцией, а затем удалив любые опции на правой руке CCx.
Обратите внимание, что выражение является чисто аддитивным. Это означает, что для того, чтобы это выражение дало ожидаемый результат, должны выполняться следующие два условия:
- Никакие два термина не могут содержать одну и ту же комбинацию.
- Все комбинации должны учитываться этими условиями.
- Никакие недопустимые комбинации не могут быть получены любым термином.
Для первого доказательства, обратите внимание, что нет двух разных CC с одинаковой левой рукой. Если бы два CC имели одинаковую левую руку, но разные правые руки, это означало бы, что существует дополнительное ограничение, которое должно применяться к одному из CC, или недопустимое ограничение, применяемое к другому.
Поскольку не существует двух СС с одинаковой левой рукой, и минимальный набор не содержит левой части любой СС по определению, то любые две СС можно отличить по крайней мере по одной опции, выбранной для одной, но не для другого. Поэтому никакие два СС не могут давать одинаковую комбинацию.
Что касается второго доказательства, обратите внимание, что набор CC содержит, по определению, все действительные комбинации для опций слева.
Предположим, что есть одна комбинация, которая не фигурирует ни в минимальном наборе, ни в наборе СС. Если эта комбинация не содержит никакой левой опции, то она должна быть комбинацией из минимального набора, по определению. Следовательно, он должен содержать опции из левой руки.
Поскольку набор CC содержит все допустимые комбинации для левой руки, то существует один CC с такими же опциями для левой руки. Следовательно, эта комбинация должна иметь опцию, которая не включена ни в одну комбинацию для этой CC. Но единственными вариантами, не включенными в этот CC, являются те, которые появляются в левой руке для других CC, и те, которые должны быть исключены из него ограничениями. Поскольку ни один из них не может иметь место, эта комбинация не может существовать.
Для третьего доказательства давайте сначала рассмотрим минимальное множество. Минимальный набор не содержит никаких опций в левой части любой группы. Поскольку все ограничения находятся между одной левой и одной правой опцией, никакое ограничение не применяется к минимальному набору.
Теперь давайте рассмотрим CC. CC имеет правильную комбинацию левых опций по определению. Любая опция, несовместимая с этой левой рукой, должна появиться в правой руке, а любая опция из этой правой руки должна быть удалена из минимального набора. Поскольку на минимальном наборе параметров, несовместимых между собой, нет никаких опций, не может быть неудовлетворенного ограничения в любой комбинации на CC.
И этим заканчивается доказательство.
Посмотрим, как это применимо, на примере из комментариев:
G1: x1, x2, x3
G2: y1, y2
G3: z1, z2, z3
R1: x1 <-> y2
R2: x3 <-> y2
R3: y1 <-> z1
R4: y2 <-> z2
R5: y2 <-> z3
CC1: {x1} <-> {y2}
CC2: {x3} <-> {y2}
CC3: {y1} <-> {z1}
CC4: {x1, y1} <-> {y2, z1}
CC5: {x3, y1} <-> {y2, z1}
CC6: {y2} <-> {z2, z3}
Давайте вкратце рассмотрим составные группы, которых нет в списке:
R1&R2: {x1, x3} <-> {y2} -- not in the list because x1 and x3 belongs to the same
group
R1&R5: {x1, y2} <-> {y2} -- not in the list because the left hand of R2, y2
appears in the right hand of R1
Теперь посмотрим, какие варианты возможны в каждом наборе:
Minimum Set: (x2), (), (z1, z2, z3)
CC1: (x1), (), (z1, z2, z3) -- replace G1 with x1, remove y2 from G2
CC2: (x3), (), (z1, z2, z3) -- replace G1 with x3, remove y2 from G2
CC3: (x2), (y1), (z2, z3) -- replace G2 with y1, remove z1 from G3
CC4: (x1), (y1), (z2, z3) -- replace G1 with x1, G2 with y1, remove y2 and z1
CC5: (x3), (y1), (z2, z3) -- replace G1 with x3, G2 with y1, remove y2 and z1
CC6: (x2), (y2), (z1) -- replace G2 with y2, remove z2 and z3 from G3
Теперь давайте добавим:
C(Minimum Set) = 1 * 0 *3 = 0
CCC1 = 1 * 0 * 3 = 0
CCC2 = 1 * 0 * 3 = 0
CCC3 = 1 * 1 * 2 = 2
CCC4 = 1 * 1 * 2 = 2
CCC5 = 1 * 1 * 2 = 2
CCC6 = 1 * 1 * 1 = 1
C(Minimum Set) + CCC1 + CCC2 + CCC3 + CCC4 + CCC5 + CCC6
0 + 0 + 0 + 2 + 2 + 2 + 1 = 7
Я добавлю еще одну мысль здесь. Несмотря на то, что для 5 правил существует только 6 CCC, что намного меньше ожидаемых 32 терминов, в противном случае эти CCC рассчитываются с наихудшим временем 2 ^ N, поскольку для каждого правила вы должны сравнить и объединить его со всеми созданными к настоящему времени CCC. Вы можете думать о них как о двоичных числах, где бит устанавливается, если правило объединяется, и не устанавливается, если нет.
Однако несовместимые комбинации сразу отбрасываются, поэтому для каждого нового объединяемого правила не теряется время на комбинациях, уже признанных недействительными. Кроме того, путем предварительной сортировки правил можно отбросить последовательные правила в той же группе, даже не проверяя на несовместимость с правильными структурами данных.
Как показывает этот конкретный пример, среднее время может быть намного лучше, чем 2 ^ N.
Альтернативные алгоритмы и соображения
Ходят разговоры о 2-SAT и 3-SAT. Мне кажется, что это проблема 2-SAT, в том смысле, что каждое ограничение a <-> b на самом деле является предложением "! A ||! B". Таким образом, все ограничения вместе можно просто записать как «(! X1 ||! Y2) && (! X1 ||! Z4) && (! Y2 &&! Z3)» и т. Д. Это означает, что вы можете «решить» это в том смысле, что вы можете узнать, есть ли логическое назначение для каждой опции, которое превратит это истинное значение . Для этого существует линейный алгоритм Аспалла, Пласса и Тарьяна со слайд-презентацией здесь .
Но знать, могут ли быть разрешены ограничения или нет - это не то, о чем спрашивали . Был задан номер способов установки всех опций при сохранении истинности проблемы 2-SAT.
Теперь существуют эффективные алгоритмы для подсчета количества способов решения проблемы 2-SAT. Например, в этой статье представлен алгоритм, который работает в 1.2561 n . Но даже это не поможет нам, так как нам нужно знать , что решения должны быть в состоянии вычислить количество комбинаций, которые удовлетворяют этому решению.
Согласно Википедии, эта статья имеет алгоритм, который эффективно перечисляет все решения, что мы и хотим. Но если подсчет уже экспоненциальный, будет и перечисление. Возможно, лучше, чем 2 n , но все же экспоненциально.
Если мы перечислим все решения проблемы 2-SAT, количество комбинаций для каждой группы будет равно 1, умноженному на количество свободных опций, опций, которые не появляются ни в одном ограничении, каждой группы, для которой нет Вариант был выбран решением.
Например, принимая предыдущий набор групп и ограничений. Проблема 2-SAT, включая взаимное исключение:
(! X1 ||! Y2) && (! X3 ||! Y2) && (! Y1 ||! Z1) && (! Y2 ||! Z2) && (! Y2 ||! Z3) &&
(! x1 ||! x3) && (! y1 ||! y2) && (! z1 ||! z2) && (! z1 ||! z3) && (! z2 ||! z3)
Первая строка - пять правил. Вторая строка - это взаимное исключение всех параметров в той же группе, которые появляются в правилах ограничения.
Решения этой проблемы 2-SAT:
x1 x3 y1 y2 z1 z2 z3 Combinations
true false true false false true false 1
true false true false false false true 1
true false true false false false false 0
true false false false true false false 0
true false false false false true false 0
true false false false false false true 0
true false false false false false false 0
false true true false false true false 1
false true true false false false true 1
false true true false false false false 0
false true false false true false false 0
false true false false false true false 0
false true false false false false true 0
false true false false false false false 0
false false true false false true false 1
false false true false false false true 1
false false true false false false false 0
false false false true true false false 1
false false false true false false false 0
false false false false true false false 0
false false false false false true false 0
false false false false false false true 0
false false false false false false false 0
В первых двух решениях нет групп без выбранной опции, поэтому количество комбинаций равно 1. В третьем решении не выбрана опция для группы G3, поэтому мы умножаем 1 на 0. В начинающихся строках при значении «false false» для группы G1 не выбрана ни одна опция, а одна свободная опция: x2. Таким образом, мы умножаем 1 на 1 для них и на 0, если для G2 или G3 не выбрана ни одна опция (в этом случае количество свободных опций равно 0).
Теперь возникает вопрос о том, как заставить один вариант, выбранный в каждой группе, по-прежнему претендовать на 2-SAT. Проблема, как указано, имеет два неявных ограничения: для каждой группы должен быть выбран один и только один вариант. Эти два ограничения могут быть записаны как:
x 1 || х 2 || x 3 (для группы x с параметрами x 1 .. x 3 )
(! x 1 ||! x 2 ) && (! x 1 ||! x 3 ) && (! x 2 ||! X 3 )
Последующее ограничение - 2-SAT, первое - 3-SAT для любого нетривиального случая. Как это происходит, я не применяю первое ограничение, но тогда счет становится равным 0. Алгоритм подсчета должен выглядеть следующим образом:
- Для комбинаций без ограничений умножьте количество вариантов без ограничений в каждой группе друг на друга.
- Для комбинаций с полным ограничением добавьте результат следующих подсчетов:
- Для каждого решения умножьте количество параметров без ограничений в каждой группе, чтобы параметр не оценивался как «true» друг для друга.
Таким образом, для каждой группы, в которой есть хотя бы одна опция без ограничений, выбор является неявным и анонимным. Для каждой группы, в которой все опции являются частью какого-либо ограничения, если ни одна опция не была выбрана, то счетчик для этой группы становится 0, и, следовательно, количество комбинаций для этого решения также становится равным 0.
Это похоже на обман проблемы с допустимым ограничением> 2-SAT. В конце концов, если бы это было возможно, тогда проблему 3-SAT можно было бы решить, просто перечислив решения ее части 2-SAT, а затем отбросив все, которые не удовлетворяют ее части 3-SAT. Увы, есть одно принципиальное отличие, которое я могу выделить:
- Все предикаты, не решаемые с помощью 2-SAT-части задачи, свободны от каких-либо дополнительных ограничений.
Учитывая это довольно ограничительное ограничение для предложений, мы можем решить эту проблему, перечислив решения явных ограничений 2-SAT.
Если кто-то хочет продолжить это, продолжайте. Я доволен улучшением предложенного мной решения 2 n .