Prolog:寻找所有解决方案 [英] Prolog: Finding all solutions
问题描述
标题可能看起来像一毛钱，但事实并非如此.这个方案的目的就是拿这些类(需求)
The title may look like it's a dime a dozen, but it's not. The object of this program is to take these classes (needs)
needs([[ece2090,1,m,13,16],
[ece3520,1,tu,11,14],
[ece4420,1,w,13,16]].
并将他们与具有教授课程证书并且在此期间也有空的大学助教配对(资源；对于 TA 的一天、开始和停止的价值意味着他目前不可用.)
and pair them with college teaching assistants that have the credentials to teach the class and are also free during that time (resources; the value with the day, start, and stop for the TA mean he isn't available at this time.)
resources([[joel, [ece2090,ece2010,ece3520,ece4420],[[m,13,16]]],
[sam, [ece2090,ece4420],[]],
[pete, [ece3520],[[w,13,16]]]].
在这个版本中，每个TA只能上一堂课.我已经建立了一个程序来做到这一点，下面是一个解决方案.
In this version, each TA can only take one class. I have built a program to do this, and a solution is below.
A = [[ece2090, 1, 'NONE'], [ece3520, 1, joel], [ece4420, 1, sam]] .
这些是助教与课程的配对.如您所见，其中一个标记为无.但是，如果您看一下，您会看到一个有效的配置，它分配了所有树 TA(Pete 分配给 ECE3520，Sam 分配给 ECE2090，Joel 分配给 ECE4420).出于以下问题的目的，这两个都将被视为解决方案.
These are the pairings of TAs to courses. As you can see, one is labelled none. However, if you look you'll see a valid configuration that assigns all tree TAs (Pete to ECE3520, Sam to ECE2090, and Joel to ECE4420). For the purposes of the following question, both of these will be considered solutions.
如何显示所有解决方案?Findall 通常是要走的路，并且有一个不可避免的失败子句也可以解决问题，但这里有一个关键点:在序言中，需求和资源都只是变量的一个实例，而不是三个，因为它们是矩阵.出于这个原因，如果我用失败子句或 findall 强制回溯，prolog 没有任何东西可以回溯
How do I display all of the solutions? Findall would typically be the way to go, and having an unavoidable fail clause would do the trick too, but here's the kicker: To prolog, needs and resources are both only one instance of a variable instead of three because they are matrices. For this reason, there's nothing for prolog to back track were I to force backtracking with a fail clause or findall
那么有没有办法找到所有解决方案?我能以某种方式将矩阵的所有可能排列方式都放入程序中吗?
So is there a way to find all solutions? Can I take every possible arrangement of a matrix somehow and toss them all into the program?
推荐答案
我完全同意 lurker 的数据组织.另外，我想说你的问题陈述让我想到了组合优化.在这种情况下，我总是建议使用 约束编程 将其制定为 CSP 并利用你的 Prolog 的 有限域库上的约束逻辑编程 (CLP(FD)).
I totally agree with lurker's data organization. In addition, I would say that your problem statement makes me think of a combinatorial optimization. In that case, I'd always recommend to formulate it as a CSP using Constraint Programming and to utilize your Prolog's Constraint Logic Programming over Finite Domains library (CLP(FD)).
约束满足问题
一般来说，CP问题包括:
Constraint Satisfaction Problems
Generally speaking, CP problems are those which consist of:
- 一组 X = {x_1, x_2, ..., x_N} 变量.
- 每个变量的域集合D = {D(x_1), D(x_2), ..., D(x_N)}，即:这些变量可以分配给的值集(例如 D(x_i) = {1, 2, 3})
- 变量之间的一组C约束(例如A > B)
约束满足问题 (CSP) 的解决方案是赋值 {x_1 = V_1, x_2 = V_2, ..., x_N = V_N} 以满足 C 中的所有约束.这就是要点.如果你想更多地了解这类问题，我建议你在当地图书馆找一本书，应该有很多.
A solution to a Constraint Satisfaction Problem (CSP) is an assignment of values {x_1 = V_1, x_2 = V_2, ..., x_N = V_N} such that satisfies all constraints in C. That's the gist. If you want to know more about these kinds of problems I suggest you look for a book at your local library, there should be plenty.
我建议您使用此公式，因为 CLP(FD) 库具有求解器，可用于找到在 CP 中公式化的问题的解决方案.使用 CP，您可以将程序构造成以下部分:
I'd recommend you use this formulation because CLP(FD) libraries have solvers which can be used to find a solution to problems formulated in CP. Using CP, you could structure your program in the following parts:
- 问题定义:定义决策变量的初始域.
- 应用一组约束.即:使用必须满足的条件链接"您的变量.
- 调用求解器，它会自动将值分配给指定域内的决策变量并满足您的所有约束.
在 Prolog 中实现 CSP
我写了一个简短的例子来向你展示如何在 SWI-Prolog 中做到这一点.首先，我假设您按以下方式构建输入数据:
Implementing CSP in Prolog
I've written a short example to show you how this would be done in SWI-Prolog. To begin with, I'll assume you structure your input data in the following way:
course(ece2090,1,m,13,16).
course(ece3520,1,tu,11,14).
course(ece4420,1,w,13,16).
ta(joel, [ece2090,ece2010,ece3520,ece4420], [m([13,16])]).
ta(sam, [ece2090,ece4420],[]).
ta(pete, [ece3520],[w([13,16])]).
ta(alan, [ece3520],[m([13,16],[19,21]),w([12,14])]).
请注意，我允许每个 TA 的可用性比您最初的规范更复杂一些.由于您想找到问题的所有可能解决方案，因此我将解决方案编码为列表列表，其中每个内部列表可以取 0 到 1 之间的值(即变量的 域).每个外部列表对应于每门课程，而内部列表对应于该特定课程的 TA 分配.
Note that I've allowed the availabilities of each TA to be a bit more complex than in your initial specifications. Since you want to find all possible solutions to your problem, I will encode a solution as a list of lists, where each inner list can take a value between 0 and 1 (that's the variables' domain). Each outer list corresponds to each course, whereas the inner lists correspond to the assignments of TA for that particular course.
% TA1, TA2, ...
Assignments = [ [1, 0, ...] , % Course 1
[0, 1, ...] , % Course 2
[0, 0, ...] | ... ] % ...
如果我们只有 2 个助教(例如 Joel 和 Sam)，上述解决方案将意味着 Joel 被分配到第一门课程，而 Sam 被分配到第二门课程.您要做的是用域 0..1 定义 unbounded 变量，应用所有必要的约束，然后自动解决它(即 label).
If we had only 2 TA's (say, Joel and Sam), the solution above would mean that Joel is assigned to the first course while Sam is assigned to the second. What you want to do is to define unbounded variables with the domain 0..1, apply all necessary constraints, and then automatically solve it (i.e. label).
timetable(ASs) :-
findall(C, course(C,_,_,_,_), Cs), % Gets all courses.
findall(TA, ta(TA,_,_), TAs), % Gets all T.A.'s
length(TAs, Nta),
assign(Cs, TAs, Nta, ASs), % ASs is a list of assignments.
append(ASs,Xs),
sum(Xs,#>,0), % Applies an extra constraint
% to discard solutions with no
% assignments.
label(Xs). % Starts the solver.
这里，assign/4 正在生成如上定义的分配列表.但是，这些值既不绑定到 0 也不绑定到 1.列表 ASs 看起来像这样:
Here, assign/4 is generating a list of assignments as defined above. However, the values are not bound to neither 0 nor 1. The list ASs would look something like this:
% TA1, TA2, ...
Assignments = [ [X1, 0, ...] , % Course 1
[ 0, X1, ...] , % Course 2
[ 0, 0, ...] | ... ] % ...
本质上，assign/4 谓词只是简单地将 0 放置在不匹配的每个项目 TA-course 中，先验，任何条件(即如果 TA 没有教授课程的证书或者他/她在特定时间很忙，则分配是 0.
In essence, the assign/4 predicate is simply placing 0 for each item TA-course that does not match, a priori, any of the conditions (i.e. an assignment is 0 if the TA doesn't have the credentials to teach the course or if he/she is busy at that particular time).
如果这是你的作业，我建议你停止阅读这里并尝试提供你自己的 assign/4 实现.如果您对CP不熟悉或想找到一点灵感，我会留下我自己的.我使用了谓词 available(?TA,+C) 当助教 TA 可用于教授课程 C 和具有这样做的必要凭据.此外，谓词 assign_(?Xs:list, +TAs:list, ?Ms:list) 是一个简单的谓词，它将在以下情况下将变量 (X) 绑定到 0TA 不是 Ms 中可用 TA 列表的成员.
If this was your homework I'd suggest you stop reading here and try to provide your own implementation of assign/4. I will leave my own in case you are not familiar with CP or want to find a bit of inspiration. I've used the predicate available(?TA,+C) which succeeds when the teaching assistant TA is available to teach the course C and has the necessary credentials to do so. In addition the predicate assign_(?Xs:list, +TAs:list, ?Ms:list) is a simple predicate which will bind the variables (X) to 0 when the TA is not a member of the list of available TA's in Ms.
assign([], _, _, []). % Stops recursion.
assign([C|Cs], TAs, Nta, [AS|ASs]) :- % Iterates through courses.
length(AS, Nta), % Generates a new list with Nta elements.
AS ins 0..1, % Sets the domain for each element in the list.
findall(TA, available(TA,C), Ms), % Finds all possible TA's for course C.
assign_(AS, TAs, Ms), % Ms now has 0s for the unavailable TA's.
sum(AS, #=<, 1), % Sets a constraint: only one TA can be assigned to a course.
assign(Cs,TAs,Nta,ASs). % Continues for the rest of courses.
% Helper predicate:
assign_([],[],_).
assign_([_|Xs],[TA|TAs],Ms) :-
memberchk(TA,Ms),
assign_(Xs,TAs,Ms).
assign_([0|Xs],[_|TAs],Ms) :-
assign_(Xs,TAs,Ms).
参见 sum/3 了解如何应用约束.为了完成程序，您只需要提供 available/2 谓词的实现.然后，下面的电话会给你一个答案:
See sum/3 to understand how constraints are applied. In order to complete the program you'd simply need to provide an implementation to the available/2 predicate. Then, the following call would give you one answer:
?- timetable(Solution).
如果您想要每种可能的解决方案，您只需再次使用 findall/3:
If you want each possible solution, you'd simply use findall/3 again:
?- findall(S, timetable(S), AllSolutions).
我还没有真正测试过我的程序，它只是为了说明，但我希望它对你有帮助.
I haven't really tested my program, it was only meant to be illustrative, but I hope you find it helpful anyway.
注意:请记住，组合问题(尤其是您想要所有解决方案的问题)在计算上是复杂的.我想你想找到那些以后优化你的时间表.在这种情况下，我鼓励您在程序本身中这样做(即 labeling/2).
NOTE: Bear in mind that combinatorial problems (and specially this one in which you want all solutions) are computationally complex. I imagine you want to find those to later optimize your timetable. That being the case I'd encourage you to do so within the program itself (i.e. labeling/2).
这篇关于Prolog:寻找所有解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
