О sat4j, как использовать sat4j для решения псевдобулевых проблем?

Question

У меня есть псевдо-логические проблемы, и мне нужно решить с Sat4j.

Кто-нибудь может мне помочь?

Вот моя проблема:

• У меня есть список переменных с именем: A, B, C, D, E, F

• И у меня есть список значений, представленных: #1, # 2, # 3.....

• h (a, #1) означает присвоение #1

У меня есть несколько примеров ограничений:

h(a,#1)=1
h(a,#1)+h(b,#1)+h(c,#1)=1
h(a,#1)+h(a,#5)>=1
h(b,#2)+h(b,#3)+h(b,#4)>=1

Так много ограничений, как примеры выше. Наконец, я хочу результат присваивания, какие значения, какое значение.

Как я могу решить это с sat4J? Как я должен представлять ограничения?

Answer 1

Если я правильно понимаю вашу проблему как псевдобулеву проблему удовлетворения, вы можете напрямую закодировать ее как файл OPB:

* #variable= 7 #constraint= 4
1 x1 = 1;
1 x1 1 x2 1 x3 = 1;
1 x1 1 x4 >= 1;
1 x5 1 x6 1 x7 >= 1;

где я произвольно закодировал h(a,#1) как x1, h(b,#1) как x2, h(c,#1) как x3, h(a,#5) как x4, h(b,#2) как x5, h(b,#3) как x6, а также h(b,#4) как x7, (Вы можете добавить такие ограничения, как

-1 x1 -1 x4 >= -1;
-1 x2 -1 x5 -1 x6 -1 x7 >= -1;

указав, что каждая переменная имеет не более одного значения, или = ровно по одному значению.)

Тогда беги

java -jar org.sat4j.pb.jar yourfile.opb

какие выходные данные (игнорируя множество строк комментариев, начинающихся с c):

s SATISFIA@KyleJones You don’t need to manually build adders and comparators to use a pseudo-boolean solver like `org.sat4j.pb`.BLE
v x1 -x2 -x3 -x4 x5 -x6 -x7 

имея в виду x1 а также x5 правда в то время как x2, x3, x4, x6, а также x7 ложные

(Я уверен, что есть способ сделать то же самое, используя org.sat4j.pb Java API, но, возможно, этот рецепт командной строки даст вам отправную точку, чтобы помочь вам понять это.)