序言:查找所有解决方案 [英] 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与课程的配对.如您所见，一个标记为none.但是，如果您看一下，您会看到一个有效的配置，该配置分配了所有树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是可行的方法，并且具有不可避免的fail子句也可以解决问题，但是这里有一个要点:序言，需求和资源都是变量的一个实例，而不是三个变量，因为它们是矩阵.出于这个原因，如果我用fail子句或findall强制回溯，那么序言就没什么回溯了
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 )
- A set X = {x_1, x_2, ..., x_N} of variables.
- A collection D = {D(x_1), D(x_2), ..., D(x_N)} of domains per every variable, that is: the set of values that these variables can be assigned to (e.g. D(x_i) = {1, 2, 3})
- A set C of constraints among variables (e.g. 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(即变量的 domain ).每个外部列表对应于每个课程，而内部列表对应于该特定课程的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个TA(例如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谓词只是为与先验条件不匹配的每个项TA课程当然都放置0(即，如果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)是一个简单的谓词，当TA不是Ms中可用TA列表的成员时，它将变量(X)绑定为0.
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).
这篇关于序言:查找所有解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
