Выводящий член множества с учетом неполных фактов о множестве

Question

Учитывая кучу фактов, таких как: Набор содержит хотя бы 1 из (A, B, C) Набор не содержит ни одного из (D, E, F)

о конечном наборе, где каждый член можетбыть конечным числом значений (скажем, целых чисел 1 ... m), как я могу перечислить все возможные множества, которые удовлетворяют списку фактов?

Я понимаю, что этот алгоритм имеет экспоненциальный характер, но яЯ хотел бы улучшить мою текущую наивную реализацию, которая состоит в том, чтобы перечислить все возможные наборы и исключить те, которые не удовлетворяют каждому условию в списке фактов.Я подумал, что, возможно, я мог бы использовать динамическое программирование и перебирать конечные значения.т.е. сначала учитывают только факты, относящиеся к значению 1, затем к значениям 1,2, затем к значениям 1,2,3 и т. д.

Answer 1

Ваши факты звучат так, как будто бы их легко перевести в экземпляр SAT (логическое удовлетворение).Затем вы можете использовать SAT-решатель, чтобы найти все возможные решения (получить одно решение, добавить предложение, которое устраняет это решение, и повторить).Есть много хороших SAT решателей, например, zChaff .