Решение логических задач на Prolog
Опубликовано: 01.09.2018
Язык пролог начал зарождаться в далеком 1879 году, точнее в этом году известный ученый Людвиг Фреге предложил исчисление предикатов, которое лежит в основе логического программирования. Фреге был не только математиком, но и философом (как и большинство других известных ученых своего времени). В то время еще не начала рушиться классическая картина мира, популярным философским учением являлся позитивизм Конта, и Фреге разделял эти взгляды, относясь к школе аналитической философии. Одной из своих задач философы видели формализацию знаний, т.е. пытались выразить знания на более точном, научном языке, например так, как делают математики. Работы по исчислению предикатов лаконично вписались в это направление.
Позже по этой теме работали другие известные философы, такие как Бертран Рассел и Людвиг Витгенштейн, представители более новой школы логического позитивизма. Исследования ведутся до сих пор, но позитивисты несколько отошли от исчисления предикатов в сторону темпоральной логики.
Структура программы на ПРОЛОГе
В 1980х годах уже появились эффективные реализации Пролога и он рассматривался как универсальный язык, при этом использовался для реализации реляционных СУБД, автоматического доказательства теорем, разработки компиляторов, САПР и других областях [1]. В начале 1990х годов пролог продвигался, в большей мере, как удобное средство разработки графического интерфейса (лучших инструментов тогда не было) [4]. В 1992 году провалился японский национальный проект компьютера пятого поколения, одной из целей которого было исследование искусственного интеллекта. В качестве языка программирования этого компьютера был выбран пролог, популярность которого резко упала [5]. В настоящее время, пролог используется , в основном, при разработке трансляторов и в задачах искусственного интеллекта [6].
Лекция 1: Что такое логическое программирование
Более подробно про историю языка Пролог можно почитать в толстых книгах [1, 2, 3], но а я привел эти факты чтобы чуть-чуть отразить особенности развития этого языка и решаемых на нем задач. Традиционно в российских ВУЗах на предметах «логическое и функциональное программирование», «искусственный интеллект» выдаются задания связанные с решением логических задач. Ноги у этих задач растут из автоматического доказательства теорем.
В статье рассматривается 2 типа логических задач — задачи на установление соответствия и задачи поиска в пространстве состояний.
Логические задачи
Задачи на установление соответствия
Задачи на установление соответствия очень похожи на работу Шерлок Холмса, в них дается набор фактов, которые надо увязать между собой чтобы найти решение. Машина логического вывода решает такие задачи полным перебором, никакого пути поиска решения при этом нет.
Примером такой головоломки может быть задача про купе:
Как то раз случай свёл в купе астронома, поэта , прозаика и драматурга. Это были Алексеев, Борисов, Константинов и Дмитриев. Оказалось, что каждый из них взял с собой книгу написанную одним из пассажиров этого купе. Алексеев и Борисов углубились в чтение предварительно обменявшись книгами. Поэт читал пьесу, прозаик — очень молодой человек, выпустивший свою книгу, говорил что он никогда и ни чего не читал по астрономии. Борисов купил одно из произведений Дмитриева. Никто из пассажиров не читал свои книги. Что читал каждый из них, кто кем был?
Перед тем, как запросить у машины логического вывода решение задачи, необходимо формализовать имеющиеся факты. В этой задаче даны 4 имени, 4 профессии и 4 вида книг. Профессии задавать не обязательно, т.к. профессию можно вывести из книги.
man(alekseev). man(borisov). man(konstantinov). man(dmitriev). writebook(astronomy). writebook(poetry). writebook(prose). writebook(piece).Пассажир купе будет описываться фактом passenger:
passenger(Name, Read, Buy, Write)Чтобы получить решение, надо попросить машину логического вывода найти четырех таких пассажиров с разными именами, читающих, написавших и купивших разные книги. Вспомогательный предикат unique, следящий за тем, чтобы элементы в списке не повторялись, описан в соседней статье: Задачи на списки [Prolog] .
solve(Solve):- Solve = [passenger(X, XRead, XBuy, XWrite), passenger(Y, YRead, YBuy, YWrite), passenger(Z, ZRead, ZBuy, ZWrite), passenger(W, WRead, WBuy, WWrite)], % 4 разных пасажира man(X), man(Y), man(Z), man(W), unique([X, Y, Z, W]), % каждый написал книгу writebook(XWrite), writebook(YWrite), writebook(ZWrite), writebook(WWrite), unique([XWrite, YWrite, ZWrite, WWrite]), % каждый купил книгу writebook(XBuy), writebook(YBuy), writebook(ZBuy), writebook(WBuy), unique([XBuy, YBuy, ZBuy, WBuy]), % каждый читает книгу writebook(XRead), writebook(YRead), writebook(ZRead), writebook(WRead), unique([XRead, YRead, ZRead, WRead]).Если запустить такое правило — мы получим все варианты решения без учета ограничений, описанных в задаче. Для проверки того, что никто не читает и не покупал свою книгу потребуется вспомогательное правило:
check([]):-!. check([passenger(_, XRead, XBuy, XWrite)|T]):- !, not(XRead = XWrite), not(XBuy = XWrite), check(T).Остальные ограничения можно описать следующим образом:
% поэт читает пьесу member(passenger(_, piece, _, poetry), Solve), % прозаик читает не астрономию not(member(passenger(_, astronomy, _, prose), Solve)), % прозаик не покупал астрономию not(member(passenger(_, _, astronomy, prose), Solve)), % никто не читает и не покупал свою книгу check(Solve), % алексеев и борисов обменялись книгами member(passenger(alekseev, AlekseevRead, AlekseevBuy, _), Solve), member(passenger(borisov, AlekseevBuy, AlekseevRead, _), Solve), % Борисов купил произведение Дмитриева member(passenger(dmitriev, _, _, DmitrievWrite), Solve), member(passenger(borisov, DmitrievWrite, _, _), Solve)В результате своей работы, программа выдает 2 решения, оба их которых подходят ко всем условиям задачи.
рис. 1 результат решения логической задачи про купе
Рассмотрим еще одну задачу на поиск соответствия:
Три друга заняли первое, второе и третье места в соревнованиях универсиады. Друзья — разной национальности, зовут их по-разному и любят они разные виды спорта.
Майкл предпочитает баскетбол и играет лучше чем американец. Израильтянин Саймон играет лучше теннисиста. Игрок в крикет занял первое место.
Кто является австралийцем? Каким видом спорта занимается Ричард?
Решение задачи опять начинается с формализации фактов. Пролог не знает что теннис — это спорт, а Саймон — имя. Сообщим ему об этом:
nation(austrian). nation(american). nation(israeli). sport(basketball). sport(tennis). sport(cricket). name(mikl). name(saimon). name(richard). prize(1). prize(2). prize(3).Мы не будем описывать правила «играть лучше«, вместо этого можно сравнить места, которые отражаются фактами prize. Запросить у пролога решение можно следующим образом:
solve(Mans):- Mans = [man(X, XNat, XSp, XP), man(Y, YNat, YSp, YP), man(Z, ZNat, ZSp, ZP)], name(X), name(Y), name(Z), unique([X, Y, Z]), nation(XNat), nation(YNat), nation(ZNat), unique([XNat, YNat, ZNat]), sport(XSp), sport(YSp), sport(ZSp), unique([XSp, YSp, ZSp]), prize(XP), prize(YP), prize(ZP), unique([XP, YP, ZP]), % Майкл играет в баскетбол member(man(mikl, _, basketball, MiklPos), Mans), % Майкл играет лучше чем американец member(man(_, american, _, AmerPos), Mans), MiklPos < AmerPos, % Саймон - израильтянин member(man(saimon, israeli, _, SaimonPos), Mans), % Саймон играет лучше теннисиста member(man(_, _, tennis, TennPos), Mans), SaimonPos < TennPos, % игрок в крикет занят первое место member(man(_, _, cricket, 1), Mans). start(Solve):- solve(Solve), Solve = [man(_, _, _, 1), man(_, _, _, 2), man(_, _, _, 3)].
рис. 2 результат решения логической задачи про спортсменов
Видно, что решение этой и предыдущей задачи очень похожи. По приведенному шаблону решается множество логических задач, ориентированных на перебор. Другим, типом логических задач являются задачи поиска в пространстве состояний.
Задачи поиска в пространстве состояний
Во многих логических задачах заданы начальное и конечное условия (состояния), и какие-либо правила поведения. Требуется найти последовательность действий, которая переведет из начального состояния в конечное. Условно, такие задачи можно разделить на 3 типа, которые мы рассмотрим на примерах.
Фиксированное число состояний
Если множество возможных состояний программы очень мало — то их можно задать руками в виде графа, где вершины — состояния, а дуги отражают возможность перехода между ними. Для решения задачи достаточно запустить поиск пути из начального состояния в конечное. Если требуется найти оптимальный путь, то к графу применяют алгоритм обхода в ширину , если же требуется найти все варианты решения — то обходят в глубину.
В качестве примера рассмотрим следующую задачу:
Лабиринт представляет собой систему комнат,соединенных между собой переходами.В лабиринте имеется вход и выход,а также комната с золотым кладом.Кроме того,имеются комнаты,запрещенные для посещений:комната монстров и комната разбойников.
Найди путь в лабиринте от входа до входа,не посещая дважды одной и той же комнаты; Найти путь с посещением золотой комнаты; Найти путь,избегающий запрещенных к посещению комнат.Как именно выглядит лабиринт в задаче не сказано (нет информации о расположении переходов). Предположим, возможны следующие переходы:
edge(in, out). edge(in, gold). edge(in, monster). edge(in, robber). edge(gold, out). edge(gold, monster). edge(gold, robber). edge(monster, out). edge(monster, gold). edge(monster, robber). edge(robber, out). edge(robber, gold). edge(robber, monster).Собственно, но этом решение закончилось, осталось написать 3 запроса (по запросу на каждый пункт задания):
?- dfs(in, out, [], Path). %1 ?- dfs(in, out, [], Path), member((_, gold), Path). %2 ?- dfs(in, out, [], Path), not(member((_, robber), Path)), not(member((_, monster), Path)). %3Результаты выполнения запросов приведены на рисунках 3-5.
рис. 3 писк всех путей в лабиринте
рис. 4 поиск путей через золотую комнату
рис. 5 поиск путей без запрещенных комнат
Не все задачи поиска в пространстве состояний решаются так легко, состояний может быть настолько много, что мы не захотим формировать граф переходов руками. В этом случае, мы описываем только начальное состояние и правило порождения новых состояний. Попробуем сделать это на примере известной задачи о волке, козе и капусте.
У фермера есть волк, коза и капуста. Все они находятся на левом берегу реки. Необходимо перевезти это «трио» на правый берег, но в лодку может поместиться что-то одно — волк, коза или капуста. Нельзя оставлять на одном берегу волка с козой и козу с капустой.
Фермер может перевозить зверей как с левого берега на правый, так и с правого на левый, а может и проехать порожняком. Требуется соблюдать, чтобы в его отсутствие звери не угрожали друг другу, т.е. состояние должно включать не только информацию о животных каждом берегу, но и положение фермера. Зверей на каждом берегу удобно представить списком.
Программа должна начать работать из состояния, в котором волк, коза и капуста находятся на левом берегу, возле них сидит фермер. Чтобы получить решение, программа достраивает граф (добавляя новые состояния и дуги) и одновременно выполняет его обход, до тех пор, пока вся живность не будет перевезена на правый берег.
Схематично, начало процесса работы программы показано на рис. 6. Состояния изображены цветными овалами, возможность перехода отражают дуги. Зеленым цветом выделены «правильные» состояния, которые обрабатывается программой, красным — «неверные» состояния (в которых коза съест капусту или волк — козу), желтым — уже обработанные состояния. Программа должна рассматривать все состояния, выполнять проверку и добавлять в граф только зеленые.
рис. 6 дерево решения задачи о волке, козе и капусте
Для генерации новых состояний будем использовать правило permutation_length , которое выдаст нам все варианты подсписков заданной величины. В этой задаче, предел длины — 1, т.к. в лодке одно место. Когда подсписок будет получен, его нужно будет отнять от одного берега (правило subtraction ) и прибавить к другому (стандартный предикат append ).
Проверка корректности списка (правило check) и генерация новых состояний (правило generate) могут быть выражены следующим образом:
check(L):- member(wolf, L), !, not(member(goat, L)); member(goat, L), !, not(member(cabbage, L)); !. generate((Left, Right, left)):- permutation_length(Left, 1, LeftPart), subtraction(Left, LeftPart, NewLeft), append(LeftPart, Right, NewRight), check(NewLeft), not(edge(_, (NewLeft, NewRight, right))), assert(edge((Left, Right, left), (NewLeft, NewRight, right))), fail;!. generate((Left, Right, right)):- permutation_length(Right, 1, RightPart), subtraction(Right, RightPart, NewRight), append(RightPart, Left, NewLeft), check(NewRight), not(edge(_, (NewLeft, NewRight, left))), assert(edge((Left, Right, right), (NewLeft, NewRight, left))), fail;!.Разберем по строчкам правило генерации из состояния фермера на левом берегу:
в 7 строке из списка зверей левого берега (Left) выделяется подсписок (LeftPart), длина которого не превышает 1; в 8 строке LeftPart вычитается из Left, чтобы получить список зверей, остающихся на левом берегу (NewLeft); в 9 строке список LeftPart присоединяется к правому берегу (Right), в результате получается список NewRight; в следующем состоянии фермер переедет на правый берег и звери на левом берегу останутся совсем одни. Их безопасность проверяется в 10 строке; нет смысла обрабатывать состояния, которые уже были обработаны (на рис. 6 выделены желтым цветом), в 11 строке выполняется соответствующая фильтрация; 12 строка добавляет в граф новую дугу, которая идет из старого состояния (Left, Right, left) в новое — (NewLeft, NewRight, right); чтобы программа добавила не одно, а все возможные новые состояния, 13 строка завершает правило неудачей. В результате, процесс вычисления откатывается до 7 строки, генерируется новый подсписок (LeftPart) и процесс повторяется.Генерация новых состояний при переходе с правого берега выполняется аналогично. Теперь, когда мы можем порождать новые состояния, осталось лишь слегка модифицировать правило обхода графа в ширину , чтобы получить решение задачи:
path(Finish, [[Finish | PathPart] | _], [Finish | PathPart]):-!. path(Finish, [[X | PathPart] | ProcList], Path):- generate(X), findall(Y, step(X, PathPart, Y), AdjNodes), append(ProcList, AdjNodes, NewProcList), !, path(Finish, NewProcList, Path). step(X,T,[Y,X|T]):- edge(X,Y), not(member(Y,T)). path(Start, Finish):- path(Finish, [[Start]], RPath), !, reverse(RPath,Path), write(Path).Видно, что в обычный обход графа в ширину, описанный ранее, была добавлена лишь третья строчка. Перед тем, как искать смежные вершины (вызов findall в 4 строке) надо их сгененировать, чем и занимается наш generate.
Запрос для машины логического вывода и решение, найденное прологом, приведены на рис. 7.
рис. 7 решение задачи о волке, козе и капусте
Задачу о волке, козе и капусте мы могли бы решить и при помощи обхода графа в глубину, но тогда мы нашли бы решение, которое было бы не оптимальным по количеству переправ. В ряде логических задач пространство состояний растет так быстро, что найти оптимальное решение достаточно трудно. В этих случаях применяют поиск в глубину. Примером может быть задача о супружеских парах:
Во время наводнения пять супружеских пар оказались отрезанными от суши водой. В их распоряжении была одна лодка, которая могла одновременно вместить только трех человек. Каждый супруг был настолько ревнив, что не мог позволить своей супруге находиться в лодке или на другом берегу с другим мужчиной (или мужчинами) в его отсутствие. Найти способ переправить на сушу этих мужчин и жен в целости и сохранности.
Если мы попытались бы решить эту задачу также как предыдущую — нас ждала бы неудача, т.к. даже на первом шаге есть 120 вариантов посадить в лодку 3 человека, а можно ведь заполнить лодку не полностью (т.е. в дереве, подобном тому, что приведено на рис. 6 из начальной вершины выходило бы более 100 дуг). И это только на первом шаге. Очевидно, поиск в ширину (по крайней мере, обычный) не сработает в этой ситуации. Задачу можно решить поиском в глубину.
Для начала, опишем пары и правила проверки списка на правильность (пары в списке не должны быть разрушены):
pair(ma, fa). % ma - муж, fa - женщина pair(mb, fb). pair(mc, fc). pair(md, fd). pair(me, fe). check(L):- onlyfemale(L); check(L, L). onlyfemale([]):-!. onlyfemale([H|T]):- pair(_, H), !, onlyfemale(T). check([], _):-!. check([H|T], L):- pair(X, H), !, member(X, L), check(T, L). check([_|T], L):- check(T, L).По условию, в лодке пары тоже могут разрушиться, поэтому в программе, состояние выражается не двумя списками, а тремя. Кроме того, состояние, как и в предыдущей задаче содержит положение лодки.
proliferate((Left, Boat, Right, left), (Left_1, Boat_1, Right, right)):- length(Boat, LenBoat), LenLeftPart is 3 - LenBoat, permutation_length(Left, LenLeftPart, LeftPart), subtraction(Left, LeftPart, Left_1), append(Boat, LeftPart, Boat_1), check(Boat_1), check(Left_1). proliferate((Left, Boat, Right, right), (Left, Boat_1, Right_1, left)):- length(Boat, LenBoat), permutation_length(Boat, LenBoat, BoatPart), subtraction(Boat, BoatPart, Boat_1), append(Right, BoatPart, Right_1), check(Boat_1), check(Right_1).Правило proliferate, приведенное выше перегоняет лодку с одного берега на другой. При перегоне лодки с левого берега на правый, с берега в лодку набираются люди (строка 3). При перегоне с правого берега на левый, часть людей высаживаются с лодки (строка 12). В принципе, можно научить пролог набирать людей на обоих берегах, но тогда он будет искать решение слишком долго.
Как и в предыдущей задачи, обход графа лишь незначительно изменится (но на этот раз, обход в ширину):
dfs(([], [], L, Dir), _, [([], [], L, Dir)]):-!. dfs(A, VN, [A|TR]):- proliferate(A, X), not(member(X, VN)), dfs(X, [A|VN], TR).В первой строке описано условие, отражающее конечное состояние — берег и лодка пусты. В третьей строке вместо выбора дуги из вершины А в вершину X выполняется генерация этой дуги правилом proliferate.
рис. 8 решение логической задачи о супружеских парах
Решение логических задач — обширная тема, по которой написаны толстые (и даже современные) книги [7,8], которые явно стоит посмотреть всем небезразличным. Безразличные тоже могут почитать для расширения кругозора.