如何通过 Answer Set Programming 获得一组满足学位要求的课程

Question

（这里是菜鸟。）假设我的学位要求学生修读 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).

其中 course(A,B) 表示 A 是满足要求 B 的课程。这就是我难倒的地方。我不确定如何告诉 clingo 我正在寻找一组符合要求的集合。查看 https://potassco.org/doc/ 上的文档很有帮助，但在我看来（在我的无知中）大多数示例都有固定数量的输出变量。

Answer 1

您当前方法的主要问题是它已经将每门课程的要求定义为事实。这意味着这些事实中的 none 可以被反驳而不会使程序无法满足。我们需要解决您提出的问题的是具有相同要求的课程之间的脱节。如果我们像下面这样定义我们的事实：

% 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).

通常，我们将通过定义所有可能的事实及其析取，然后用规则限制它们来启动答案集程序。对于这个程序，我们有一个相当小的起始集，但它们可以变得非常大，因此复杂的规则可以派上用场。但是，对于这个问题，我们不需要任何！

（嘿 Ricks 博士，我是游戏 Programming/Image 处理中的艾萨克！偶然发现你的问题，希望我的回答对你有帮助！）

如何通过 Answer Set Programming 获得一组满足学位要求的课程

How to get a set of courses that fulfill degree requirements with Answer Set Programming

answer-set-programming