Prolog: Поиск всех решений

Question

Название может показаться, что это десяток десятков, но это не так. Целью данной программы является взять эти классы (потребности)

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

и соединить их с обучением в колледже помощников, которые имеют полномочия, чтобы научить класс и также бесплатно в течение этого времени (ресурсов, значение с днем , запуск и остановка для TA означает, что он не доступен в данный момент.)

resources([[joel, [ece2090,ece2010,ece3520,ece4420],[[m,13,16]]], 
[sam, [ece2090,ece4420],[]], 
[pete, [ece3520],[[w,13,16]]]]. 

В этой версии, каждая из ТА может принимать только один класс. Я создал программу для этого, и решение ниже.

A = [[ece2090, 1, 'NONE'], [ece3520, 1, joel], [ece4420, 1, sam]] . 

Это пары TA для курсов. Как вы можете видеть, один помечен как none. Однако, если вы посмотрите, вы увидите действительную конфигурацию, которая присваивает все TA дерева деревьев (Пит к ECE3520, Сэму к ECE2090 и Джоэлю - ECE4420). Для целей следующего вопроса оба из них будут рассматриваться как решения.

Как отобразить все решения? Findall, как правило, был бы способ пойти, и наличие неизбежного предложения об отказе тоже могло бы сделать трюк, но вот кикер: для пролога потребности и ресурсы - это только один экземпляр переменной вместо трех, потому что они являются матрицами. По этой причине нет ничего для пролома для обратной дорожки, если бы я принудительно возвращал назад с предложением о провале или обнаружил

Так есть способ найти все решения? Могу ли я каким-либо образом принять любую возможную структуру матрицы и бросить их всех в программу?

Answer 1

Возможно, это задание, поэтому я прекращу предоставление полного решения. Но я бы рекомендовал структурировать информацию по-разному, чтобы быть более типичным, как это делается в Прологе:

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

Здесь, вместо того вложенных списков в фактах, каждый факт стоит самостоятельно. Каждый отдельный функтор похож на одну таблицу в базе данных, которую вы можете запросить, а разные функторы - разные таблицы, которые взаимосвязаны на основе некоторого аргумента.

Так что, если вы хотите знать, что joel квалифицирован для:

| ?- qualified_for(joel, C). 

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

yes 
| ?- 

Если вам нужен список всех квалифицированных ТА:

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

AllTAs = [joel,pete,sam] 

yes 
| ?- 

Если вы хотите увидеть, что нужно классы joel доступна для обучения и квалификации для обучения:

| ?- 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 
| ?- 

Вышеприведенное предположение состоит в том, что все блоки расписания описаны так же, как вы показываете, [day, start, end], поэтому их можно просто сопоставить как целые 3-элементные списки. С небольшими дополнительными усилиями это может быть более обобщенным для более детального изучения дней и временных интервалов. Но это не является для вас требованием. Вышеупомянутые являются хорошими строительными блоками, помогающими решить вашу проблему. Это требует только нескольких строк кода (я использовал только 12 строк, а также приведенные выше факты). :)

Answer 2

Я полностью согласен с lurker данные организации данных. Кроме того, я бы сказал, что ваше заявление о проблеме заставляет меня думать о комбинаторной оптимизации.В этом случае я всегда рекомендую сформулировать его как CSP с использованием Constraint Programming и использоватьProlog (CLP (FD)).

Constraint Satisfaction Проблемы
Вообще говоря, проблемы CP являются те, которые состоят из:

• набор X = {x_1, x_2, ..., x_n} переменных.
• Коллекция D = {D (x_1), D (x_2), ..., D (X_n)} доменов на каждой переменной, то есть: множество значений, что эти переменные могут быть назначены к (например, D (x_i) = {1, 2, 3})
• Множество с ограничений между переменными (например, A> B)

раствор к Задача ограничения ограничений (CSP) - это назначение val ues {x_1 = V_1, x_2 = V_2, ..., x_N = V_N}, который удовлетворяет всем ограничениям в C. Это суть. Если вы хотите узнать больше об этих проблемах, я предлагаю вам найти книгу в вашей местной библиотеке, должно быть много.

Я бы рекомендовал вам использовать эту формулировку, потому что библиотеки CLP (FD) имеют решатели, которые могут быть использованы для поиска решения проблем, сформулированных в CP. Используя CP, вы можете структурировать свою программу в следующих частях:

1. Определение проблемы: определить начальные домены переменных решения.
2. Применить набор ограничений. То есть: «свяжите» свои переменные с условиями, которые должны быть выполнены.
3. Позвоните в решатель, который автоматически присваивает значения вашим переменным решения в указанном домене и удовлетворяет всем вашим ограничениям.

Реализация СНТ в Прологе
Я написал небольшой пример, чтобы показать вам, как это будет сделано в SWI-Prolog. Начнем с того, я предполагаю, что вы структурировать входные данные следующим образом:

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

Обратите внимание, что я позволившая наличность каждый ТОТ, чтобы быть немного более сложным, чем в ваших исходных спецификациях. Поскольку вы хотите найти все возможные решения своей проблемы, я буду кодировать решение как список списков, где каждый внутренний список может принимать значение от 0 до 1 (это переменные «», домен). Каждый внешний список соответствует каждому курсу, тогда как внутренние списки соответствуют назначениям TA для этого конкретного курса.

   % TA1, TA2, ... 
Assignments = [ [1, 0, ...] ,  % Course 1 
       [0, 1, ...] ,  % Course 2 
       [0, 0, ...] | ... ] % ... 

Если бы мы имели только 2 ТЕ (скажем, Джоэл и Сэм), указанное решение будет означать, что Джоэл назначен на первый курс в то время как Сэм относятся ко второму. Что вы хотите сделать, так это определить неограниченные переменные с доменом 0..1, применить все необходимые ограничения, а затем автоматически решить его (т. Е. ярлык).

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 будет выглядеть примерно так:

   % TA1, TA2, ... 
Assignments = [ [X1, 0, ...] ,  % Course 1 
       [ 0, X1, ...] ,  % Course 2 
       [ 0, 0, ...] | ... ] % ... 

В сущности, assign/4 предикат просто помещая 0 для каждого элемента TA-конечно, что не соответствует, a priori, любое из условий (т.е. присвоение - 0, если у TA нет полномочий для обучения курсу или если он/она занят в это конкретное время).

Если бы это была ваша домашняя работа, я предлагаю вам прекратить читать здесь и попытаться обеспечить вашу собственную реализацию assign/4. Я оставлю свое, если вы не знакомы с CP или хотите найти немного вдохновения. Я использовал предикат available(?TA,+C), который преуспевает, когда преподаватель TA доступен для обучения курсу C и имеет необходимые полномочия для этого. Кроме того, предикат assign_(?Xs:list, +TAs:list, ?Ms:list) является простым предикатом, который свяжет переменные (X) с 0, когда TA не является членом списка доступных TA в 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. Затем, следующий вызов даст вам один ответ:

?- timetable(Solution). 

Если вы хотите, чтобы каждые из возможных решений, вы бы просто использовать findall/3 снова:

?- findall(S, timetable(S), AllSolutions). 

Я действительно не проверил мои программы, ее был предназначен только для иллюстрации, но, надеюсь, вы найдете его полезным в любом случае.

ПРИМЕЧАНИЕ: Помните, что комбинаторные проблемы (и особенно этот, в котором вы хотите все решения) являются вычислительно сложными. Я предполагаю, что вы хотите найти тех, кто позже оптимизирует ваше расписание. В этом случае я бы посоветовал вам сделать это в самой программе (т. Е. labeling/2).