Это третья статья из серии, в которой показано, как кодировать LSAT Puzzles на языке программирования Ergo Lite. Чтобы начать сначала, перейдите к вступительному посту.
В этом посте я покажу вам, как вы можете использовать Ergo Lite для автоматического создания всех возможных расписаний.
В некоторых вопросах, которые мы собираемся кодировать, вопрос будет заключаться в том, всегда ли что-то верно или никогда не верно в расписании, которое придерживается правил. Чтобы позволить компьютеру легко ответить на эти вопросы, мы можем заставить его генерировать все возможные расписания и просто искать, чтобы увидеть, всегда ли эти вещи верны.
Существует несколько способов создания такого рода данных. Это только один пример. Наша стратегия будет заключаться в том, чтобы создать все возможные действительные расписания для одного дня, а затем объединить их для создания трехдневных фестивалей.
Обратите внимание, что мы ограничиваемся действительными расписаниями, потому что ни один из вопросов, которые мы кодируем, не содержит вопросов о недопустимых расписаниях.
Действующее расписание на один день включает от 1 до 3 показов разных фильмов. В расписании также есть просмотры, поэтому начнем с того, что возможный день — это тип расписания.
PossibleDay::Schedule.
Теперь нам нужно «создать» все возможные дни с одним просмотром. Как правило, мы могли бы сказать, что один возможный день — это единственный показ фильма в первом слоте для каждого известного нам фильма. Мы можем добиться этого в коде, создав правило.
pd1(?film):PossibleDay[screenings->ps1(?film):Screening[slot->First,film->?film]] :- ?film:Film.
Здесь вы можете видеть, что мы делаем правило. Тело или условие правила: ?film:Film. Это означает, что «в базе данных есть объект, который я назову «фильм», который является объектом типа «Фильм».
Если вы зададите этот вопрос базе данных, она скажет вам, что таких объектов три, и перечислит их. Итак, наше правило будет срабатывать три раза, и каждый раз вывод правила будет подтверждаться.
Глава правила намного сложнее, но в основном говорит: «Есть объект с именем pd1(FilmName), который является Возможным днем, и имеет показ, который является объектом с именем ps1(FilmName), который является показом FilmName в Первый слот».
Разница между «созданием объекта» и «доказательством существования объекта» на самом деле ничем не отличается. Это потому, что все утверждения в Ergo Lite на самом деле являются Правилами, но в некоторых из них отсутствуют части.
Правило head :- body. гласит: «голова доказана, если тело верно». Если вы опустите тело, вы получите head :-., которое можно сократить до head.. Если у правила нет тела, то оно всегда верно. Таким образом, правило без тела называется «фактом». Доказательство того, что что-то истинно с помощью правила, и утверждение, что это истинно с помощью «факта», — это просто разные способы доказательства того, что это истинно.
Затем, если у вас есть правило без заголовка, вы получите :- body., которое вы можете указать как ?- body.. Если вы говорите «когда это верно, ничего не доказано», опуская заголовок правила, Ergo Lite рассматривает это утверждение как вопрос «Когда это верно?» и будет искать в базе данных соответствующие объекты и отображать их для вас.
Запросы обычно используются при использовании интерактивного терминала Ergo Lite. Мы будем использовать запросы позже в этой серии, чтобы получить ответы на наши вопросы.
Итак, мы создали новый объект «Возможный день» pd1(Film) для каждого фильма в базе данных.
Мы можем сделать то же самое для двухдневных и трехдневных графиков. Конечно, в двухдневном графике есть два фильма, и нам нужно четко указать, что они отличаются друг от друга, и нам нужно создать два показа.
Обратите внимание, что мы могли бы, если бы захотели, сгенерировать недопустимые возможные дни, включив дни, в которые один и тот же фильм показывают дважды. Тогда мы могли бы полагаться на наши правила, чтобы различать действительные и недействительные расписания. Но если бы мы следовали этой стратегии, то получили бы почти 60 000 возможных расписаний, каждое из которых нужно было бы проверять на достоверность каждый раз, когда мы хотели задать вопрос только о действительных. Это сделало бы наш код слишком медленным, чтобы его можно было использовать.
Поскольку мы знаем, что будем задавать вопросы только о допустимых расписаниях, мы можем избежать такого рода проблем, ограничив создаваемые нами примеры теми, которые настолько достоверны, насколько мы можем их сделать. Здесь мы можем сделать их более достоверными, чтобы убедиться, что фильмы не повторяются в данный день.
pd2(?first,?second):PossibleDay,
pd2(?first,?second)[screenings->ps2(?second):Screening],
pd2(?first,?second)[screenings->ps1(?first):Screening],
ps2(?second)[slot->Second,film->?second],
ps1(?first)[slot->First,film->?first] :-
?first:Film,
?second:Film,
?first !== ?second.
И затем, для трехдневных графиков, шаблон продолжается.
pd3(?first,?second,?third):PossibleDay,
pd3(?first,?second,?third)[screenings->ps1(?first):Screening],
pd3(?first,?second,?third)[screenings->ps2(?second):Screening],
pd3(?first,?second,?third)[screenings->ps3(?third):Screening],
ps3(?third)[slot->Third,film->?third],
ps2(?second)[slot->Second,film->?second],
ps1(?first)[slot->First,film->?first] :-
?first:Film,
?second:Film,
?third:Film,
?first !== ?second,
?first !== ?third,
?second !== ?third.
Итак, мы создали все возможные дни. Как оказалось, их всего 15. Теперь нам нужно объединить три из этих возможных действительных дней, чтобы создать все действительные расписания фестиваля.
Для этого мы сообщаем коду, что TestSchedule — это тип расписания.
TestSchedule:Schedule
Затем мы сообщаем ему, что если есть три Возможных дня, то существует объект расписания тестирования с этими тремя возможными днями. Чтобы сделать эти расписания максимально достоверными и ограничить размер базы данных, которую нам нужно искать, мы создадим тестовое расписание только из дней, действительных в течение трех дней фестиваля.
Для этого нам нужно переформулировать наши правила для четверга, пятницы и субботы, чтобы определить не то, действительно ли расписание, а то, является ли возможный день действительным для этого дня недели. Мы можем сделать это, взяв правила трех дней и правило «последнего» и изменив ссылки на «Расписание» на ссылки «Возможный день» и удалив ссылки на определенные дни. Код выглядит следующим образом:
?x[last->?film] :-
?x:PossibleDay[screenings->?_s[slot->?_slot,film->?film]],
\naf ?x[screenings->?_os[slot->?_[after->?_slot]]].
?x[thursday_eligible->\true] :-
?x:PossibleDay[screenings->?_s[film->Harvest]],
?x[last->Harvest].
?x[friday_eligible->\true] :-
( // either
?x:PossibleDay[last->Greed],
\naf exists(?_s)^?x[screenings->?_s[film->Limelight]]
) \or (
?x:PossibleDay[last->Limelight],
\naf exists(?_s)^?x[screenings->?_s[film->Greed]]
).
?x[saturday_eligible->\true] :-
( // either
?x:PossibleDay[last->Greed],
\naf exists(?_s)^?x[screenings->?_s[film->Harvest]]
) \or (
?x:PossibleDay[last->Harvest],
\naf exists(?_s)^?x[screenings->?_s[film->Greed]]
).
Теперь мы можем написать правило, которое говорит, что расписание тестов существует для каждой комбинации допустимых четверга, пятницы и субботы. Имя, данное этим объектам, разработано таким образом, что когда мы ищем имя расписания испытаний, это имя расскажет нам все о его содержании.
test_sched(?ps1,?ps2,?ps3):TestSchedule[thursday->?ps1,friday->?ps2,saturday->?ps3] :-
?ps1:PossibleDay[thursday_eligible->\true],
?ps2:PossibleDay[friday_eligible->\true],
?ps3:PossibleDay[saturday_eligible->\true].
Затем мы говорим, что если у атрибута TestSchedule четверг (который является возможным днем) есть проверка, то у TestSchedule также есть этот объект проверки.
?x[screenings->s(r,?f,?s):Screening[film->?f,slot->?s,day->Thursday]] :-
?x:TestSchedule[thursday->?_[screenings->?_y[film->?f,slot->?s]]].
Затем мы делаем то же самое для пятницы и субботы.
?x[screenings->s(f,?f,?s):Screening[film->?f,slot->?s,day->Friday]] :-
?x:TestSchedule[friday->?_[screenings->?_y[film->?f,slot->?s]]].
?x[screenings->s(s,?f,?s):Screening[film->?f,slot->?s,day->Saturday]] :-
?x:TestSchedule[saturday->?_[screenings->?_y[film->?f,slot->?s]]].
Сейчас мы сгенерировали все возможные действительные расписания и несколько недействительных, потому что мы не проверяли, чтобы каждый фильм был показан хотя бы один раз. По этой причине из 80 возможных расписаний 16 недействительны. Вы можете изменить правило, создающее объекты test_sched, чтобы проверить, включен ли каждый фильм в один из трех возможных дней хотя бы один раз, но это остается читателю в качестве упражнения.
Теперь у нас есть данные, необходимые для поиска всех возможных действительных расписаний, и мы готовы начать отвечать на вопросы.
Джейсон Моррис — кандидат юридических наук в области вычислительного права на юридическом факультете Университета Альберты, оператор Round Table Law и соучредитель Lemma Legal Consulting. С ним можно связаться по адресу @RoundTableLaw в Твиттере. Если вам нужна помощь в том, чтобы заставить компьютеры заниматься юриспруденцией, не стесняйтесь обращаться к нам.
