Как получить набор курсов, отвечающих требованиям степени, с программированием набора ответов

(Нуб здесь.) Скажем, у меня есть степень, которая требует, чтобы студент сдал CS1 и CS2 и (CS3 или CS4). Я хотел бы использовать ASP, чтобы получить список курсов, которые студент может пройти, чтобы выполнить требования степени. В частности, я ожидаю, что ответ будет {CS1, CS2, CS3} и {CS1, CS2 и CS4}.

На данный момент я вывел следующие правила:

course(cs_1,1).
course(cs_2,2).
course(cs_3,3).
course(cs_4,3).

requirement(X) :- course(_,X).

где курс (A, B) указывает, что курс A соответствует требованию B. Вот где я в тупике. Я не знаю, как сообщить cligo, что я ищу набор наборов, отвечающий требованиям. Просмотр документации по адресу https://potassco.org/doc/ оказался полезным, но большинство примеров кажутся мне (по моему невежеству) иметь фиксированное количество выходных переменных.


answer-set-programming
person bricksphd    schedule 07.07.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Основная проблема с вашим нынешним подходом заключается в том, что он уже определил, что каждый курс требует в качестве фактов. Это означает, что ни один из этих фактов нельзя опровергнуть, не сделав программу невыполнимой. Что нам нужно, чтобы решить проблему, которую вы поставили, так это дизъюнкцию между курсами, которые имеют одинаковые требования. Если мы определим наши факты следующим образом:

% fulfills(course, requirement)
fulfills(cs_1,1).
fulfills(cs_2,2).
fulfills(cs_3,3) | fulfills(cs_4,3).

становится намного проще определить правило, чтобы получить нам информацию, которую мы хотим. Из этого списка фактов мы видим, что cs_1 удовлетворяет требованию 1, cs_2 удовлетворяет требованию 2, а cs_3 или cs_4 удовлетворяет требованию 3. Это означает, что в нашем наборе ответов не может быть одновременно fulfills(cs_3,3) и fulfills(cs_4,3). Вместо этого у нас может быть только один из этих фактов, поскольку, если бы у нас были оба, наш набор не был бы минимальным.

Хотя мы могли бы написать некоторые правила, чтобы сократить наборы ответов, которые это генерирует, или определить больше отношений, программа хороша как есть! Он генерирует следующее, которое соответствует вашим желаемым результатам:

Answer: 1
fulfills(cs_1,1) fulfills(cs_2,2) fulfills(cs_3,3)
Answer: 2
fulfills(cs_1,1) fulfills(cs_2,2) fulfills(cs_4,3)
SATISFIABLE

Models       : 2
Calls        : 1
Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

Затем мы можем расширить его до большего количества курсов и требований:

fulfills(cs_1,1).
fulfills(cs_2,2) | fulfills(cs_3,2).
fulfills(cs_4,3) | fulfills(cs_5,3).
fulfills(cs_6,4) | fulfills(cs_7,4) | fulfills(cs_8,4).
fulfills(cs_9, 5).

что дает нам гораздо больше возможностей:

Answer: 1
fulfills(cs_1,1) fulfills(cs_9,5) fulfills(cs_6,4) fulfills(cs_4,3) fulfills(cs_2,2)
Answer: 2
fulfills(cs_1,1) fulfills(cs_9,5) fulfills(cs_6,4) fulfills(cs_4,3) fulfills(cs_3,2)
Answer: 3
fulfills(cs_1,1) fulfills(cs_9,5) fulfills(cs_6,4) fulfills(cs_5,3) fulfills(cs_2,2)
Answer: 4
fulfills(cs_1,1) fulfills(cs_9,5) fulfills(cs_6,4) fulfills(cs_5,3) fulfills(cs_3,2)
Answer: 5
fulfills(cs_1,1) fulfills(cs_9,5) fulfills(cs_8,4) fulfills(cs_4,3) fulfills(cs_3,2)
Answer: 6
fulfills(cs_1,1) fulfills(cs_9,5) fulfills(cs_8,4) fulfills(cs_5,3) fulfills(cs_3,2)
Answer: 7
fulfills(cs_1,1) fulfills(cs_9,5) fulfills(cs_8,4) fulfills(cs_4,3) fulfills(cs_2,2)
Answer: 8
fulfills(cs_1,1) fulfills(cs_9,5) fulfills(cs_8,4) fulfills(cs_5,3) fulfills(cs_2,2)
Answer: 9
fulfills(cs_1,1) fulfills(cs_9,5) fulfills(cs_7,4) fulfills(cs_4,3) fulfills(cs_3,2)
Answer: 10
fulfills(cs_1,1) fulfills(cs_9,5) fulfills(cs_7,4) fulfills(cs_4,3) fulfills(cs_2,2)
Answer: 11
fulfills(cs_1,1) fulfills(cs_9,5) fulfills(cs_7,4) fulfills(cs_5,3) fulfills(cs_3,2)
Answer: 12
fulfills(cs_1,1) fulfills(cs_9,5) fulfills(cs_7,4) fulfills(cs_5,3) fulfills(cs_2,2)
SATISFIABLE

Models       : 12
Calls        : 1
Time         : 0.002s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

если мы хотим, мы могли бы даже опустить второй аргумент до fulfills, так как мы еще ни для чего его не используем. Следующее дает те же результаты, что и наш первый пример:

course(cs_1).
course(cs_2).
course(cs_3) | course(cs_4).

Как правило, мы начинаем программу набора ответов, определяя все наши возможные факты и их дизъюнкции, а затем ограничивая их правилами. Для этой программы у нас есть довольно небольшой начальный набор, но он может стать довольно большим, поэтому сложные правила могут пригодиться. Однако для этой задачи нам ничего не нужно!

(Привет, доктор Рикс, это Исаак из Game Programming/Image Processing! Наткнулся на ваш вопрос, надеюсь, мой ответ будет полезен!)

person izeke    schedule 14.07.2020