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]].

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]]]].

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]] .

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.

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?

回答1:

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

Constraint Satisfaction Problems
Generally speaking, CP problems are those which consist of:

• 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)

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.

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:

1. Problem definition: define the initial domains of your decision variables.
2. Apply a set of constraints. That is: "link" your variables using conditions that must be satisfied.
3. Call a solver which automatically assigns values to your decision variables within the specified domain and satisfying all your constraints.

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

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, ...] | ... ]  % ...

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.

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, ...] | ... ]  % ...

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

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

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

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.

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

回答2:

This is probably an assignment, so I'll stop short of giving away a complete solution. But I would recommend structuring your information differently, to be more typical of how it's done in Prolog:

need(ece2090, 1, [m, 13, 16]).
need(ece3520, 1, [tu, 11, 14]).
need(ece4420, 1, [w, 13, 16]).

qualified_for(joel, ece2090).
qualified_for(joel, ece2010).
qualified_for(joel, ece3520).
qualified_for(joel, ece4420).
qualified_for(sam, ece2090).
qualified_for(sam, ece4420).
qualified_for(pete, ece3520).

busy(joel, [m, 13, 16]).
% busy(sam, []).  % absence of this fact means sam isn't busy
busy(pete, [w, 13, 16]).
busy(pete, [f, 9, 12]).

Here, rather than having embedded lists in facts, each fact stands on its own. Each distinct functor is like one table in a database that you can query, and the different functors are different tables that are interrelated based upon some argument.

So if you want to know what joel is qualified for:

| ?- qualified_for(joel, C).

C = ece2090 ? ;
C = ece2010 ? ;
C = ece3520 ? ;
C = ece4420

yes
| ?-

If you need a list of all the qualified TAs:

| ?- setof(TA, C^qualified_for(TA, C), AllTAs).

AllTAs = [joel,pete,sam]

yes
| ?-

If you want to see what needed classes joel is available for and qualified to teach:

| ?-  need(Class, I, Schedule), qualified_for(joel, Class), \+ busy(joel, Schedule).

Class = ece3520
I = 1
Schedule = [tu,11,14] ? a

Class = ece4420
I = 1
Schedule = [w,13,16]

(1 ms) yes
| ?-

The assumption above is that "schedule" blocks are all described in the same way, [day, start, end] as you show, so they can simply be matched as entire 3-element lists. With a little extra effort, this can be more generalized to check days and time intervals in more detail. But that doesn't appear to be a requirement for you. The above are good building blocks to help solve your problem. It only requires a few lines of code (I used only 12 lines, plus the above facts). :)