Решение логических задач на Prolog
Язык пролог начал зарождаться в далеком 1879 году, точнее в этом году известный ученый Людвиг Фреге предложил исчисление предикатов, которое лежит в основе логического программирования. Фреге был не только математиком, но и философом (как и большинство других известных ученых своего времени). В то время еще не начала рушиться классическая картина мира, популярным философским учением являлся позитивизм Конта, и Фреге разделял эти взгляды, относясь к школе аналитической философии. Одной из своих задач философы видели формализацию знаний, т.е. пытались выразить знания на более точном, научном языке, например так, как делают математики. Работы по исчислению предикатов лаконично вписались в это направление.
Позже по этой теме работали другие известные философы, такие как Бертран Рассел и Людвиг Витгенштейн, представители более новой школы логического позитивизма. Исследования ведутся до сих пор, но позитивисты несколько отошли от исчисления предикатов в сторону темпоральной логики.
В 1980х годах уже появились эффективные реализации Пролога и он рассматривался как универсальный язык, при этом использовался для реализации реляционных СУБД, автоматического доказательства теорем, разработки компиляторов, САПР и других областях [1]. В начале 1990х годов пролог продвигался, в большей мере, как удобное средство разработки графического интерфейса (лучших инструментов тогда не было) [4]. В 1992 году провалился японский национальный проект компьютера пятого поколения, одной из целей которого было исследование искусственного интеллекта. В качестве языка программирования этого компьютера был выбран пролог, популярность которого резко упала [5]. В настоящее время, пролог используется , в основном, при разработке трансляторов и в задачах искусственного интеллекта [6].
Более подробно про историю языка Пролог можно почитать в толстых книгах [1, 2, 3], но а я привел эти факты чтобы чуть-чуть отразить особенности развития этого языка и решаемых на нем задач. Традиционно в российских ВУЗах на предметах «логическое и функциональное программирование», «искусственный интеллект» выдаются задания связанные с решением логических задач. Ноги у этих задач растут из автоматического доказательства теорем.
В статье рассматривается 2 типа логических задач — задачи на установление соответствия и задачи поиска в пространстве состояний.
Задачи на установление соответствия
Задачи на установление соответствия очень похожи на работу Шерлок Холмса, в них дается набор фактов, которые надо увязать между собой чтобы найти решение. Машина логического вывода решает такие задачи полным перебором, никакого пути поиска решения при этом нет.
Примером такой головоломки может быть задача про купе:
Как то раз случай свёл в купе астронома, поэта , прозаика и драматурга. Это были Алексеев, Борисов, Константинов и Дмитриев. Оказалось, что каждый из них взял с собой книгу написанную одним из пассажиров этого купе. Алексеев и Борисов углубились в чтение предварительно обменявшись книгами. Поэт читал пьесу, прозаик — очень молодой человек, выпустивший свою книгу, говорил что он никогда и ни чего не читал по астрономии. Борисов купил одно из произведений Дмитриева. Никто из пассажиров не читал свои книги. Что читал каждый из них, кто кем был?
Перед тем, как запросить у машины логического вывода решение задачи, необходимо формализовать имеющиеся факты. В этой задаче даны 4 имени, 4 профессии и 4 вида книг. Профессии задавать не обязательно, т.к. профессию можно вывести из книги.
Пассажир купе будет описываться фактом passenger:
passenger(Name, Read, Buy, Write).
Чтобы получить решение, надо попросить машину логического вывода найти четырех таких пассажиров с разными именами, читающих, написавших и купивших разные книги. Вспомогательный предикат unique, следящий за тем, чтобы элементы в списке не повторялись, описан в соседней статье: Задачи на списки Prolog.
Если запустить такое правило — мы получим все варианты решения без учета ограничений, описанных в задаче. Для проверки того, что никто не читает и не покупал свою книгу потребуется вспомогательное правило:
Остальные ограничения можно описать следующим образом:
В результате своей работы, программа выдает 2 решения, оба их которых подходят ко всем условиям задачи.
рис. 1 результат решения логической задачи про купе
Рассмотрим еще одну задачу на поиск соответствия:
Три друга заняли первое, второе и третье места в соревнованиях универсиады. Друзья — разной национальности, зовут их по-разному и любят они разные виды спорта.
Майкл предпочитает баскетбол и играет лучше чем американец. Израильтянин Саймон играет лучше теннисиста. Игрок в крикет занял первое место.
Кто является австралийцем? Каким видом спорта занимается Ричард?
Решение задачи опять начинается с формализации фактов. Пролог не знает что теннис — это спорт, а Саймон — имя. Сообщим ему об этом:
Мы не будем описывать правила «играть лучше«, вместо этого можно сравнить места, которые отражаются фактами prize. Запросить у пролога решение можно следующим образом:
рис. 2 результат решения логической задачи про спортсменов
Видно, что решение этой и предыдущей задачи очень похожи. По приведенному шаблону решается множество логических задач, ориентированных на перебор. При этом четко просматривается структура шаблона — сначала заставляем интерпретатор перебирать все возможные значения, а затем — проверяем их. Эта струткруа лежит в основе метода генерации гипотезы.
Метод генерации гипотезы
Метод заключается в переборе всех возможных решений и их проверке на соответствие правилам задачи. На форуме этим методом решено более 100 логических задач — это указывает на его относительную универсальность. Особое внимание в нем уделяется формализации понятия «гипотеза», то есть набора предположений, который должен выдвигать и проверять интерпретатор.
Рассмотрим пример задачи:
Какие выводы вы сделали бы из следующих фактов? — спросил инспектор Крэг у сержанта Макферсона:
1. Если А виновен и В невиновен, то С виновен; 2. С никогда не действует в одиночку; 3. А никогда «не ходит на дело» вместе с С; 4. Никто, кроме А, В и С, в преступлении не замешан, и по крайней мере один из этой тройки виновен.
Сержант поскреб в затылке и сказал: «Боюсь, что я смогу извлечь из этих фактов не слишком много, сэр. А вы можете, опираясь на них, доказать, кто из трех подозреваемых виновен и кто не виновен?»
«Не могу, — признался Крэг, — но, чтобы выдвинуть неопровержимое обвинение против одного из них, материала вполне достаточно». Чья виновность не вызывает сомнений?
Объекты в этой задаче — подозреваемые. Они имеют имя и виновность. Гипотезой является список из трех объектов.
Rод этой задачи написан на Visual Prolog 5.2 (совместим с Turbo Prolog). В нем отсутствуют встроенные предикаты типа member , однако их аналоги можно взять тут. Visual Prolog лучше чем SWI в части типизации, мы можем в секции domains описать типы данных и если где-то в коде опечатаемся и вместо имени персонажа передадим что-то иное (ошибемся в раскладке клавиатуры) — программа не скомпилируется и ошибка будет найдена до ее запуска.
Для это й задачи типы описаны следующим образом:
Тут заведено три типа данных, два из них задается перечислением. А третий — описывается структурой, то есть объединяет имя и виновность.
То есть эта задача заключается в установлении соответствия между именем и виновностью. В соответствии с этим методом, программа должна перебирать виновность участников. Для этого надо добавить в программу правила для перебора возможных имен и виновностей. Программа на этом этапе выглядит так:
Эта программа перебирает все возможные имена и виновности — генерирует 6 решений:
Теперь можно описать правило генерации гипотезы, которое будет формировать список из трех элементов (подозреваемых). Так как список имен заранее известен — то перебирать имена в этой программе на самом деле не требуется.
Правило генерации гипотезы формирует список из структур, при этом имя в структуре задано явно, а виновность подбирается. Всего программа находит 8 вариантов генерации.
Остается выполнить проверку гипотез, то есть соответствие их условиям задачи… Как это делалось показано на первом условии:
Видно, что одно условие превратилось в 3 правила. Дело в том, что условие типа
ЕСЛИ ххх то уууу
не говорит ничего о том, что должно случиться если ххх = false . Но по логике описанного высказывания, если А невиновен — то никаких ограничений на С не должно накладываться. Вот прямо это тут и записано.
Остальные условия описаны так:
Теперь можно описать правило проверки гипотезы, заключающееся в проверке всех четырех условий и запустить программу (цель указывается в секции goal):
Тут видно, что А всегда невиновен, А и С всегда виновны. Это не соответствует задаче, так как согласно ней, следователям не удалось установить кто виновен, а кто — нет. Однако: 1. генерация работает верно — легко проверить что она выдает все возможные варианты гипотез. 2. правила проверки были проверены на 10 раз, даже несколько раз переписывались «по другому». Все равно ответ один…
Однако, даже так — эта программа не дает ответ на вопрос «кто виновен».
Для этого написан такой предикат:
Этот предикат проверяет что определенный подозреваемый может быть виновен или невиновен. Например
проверит существует ли хоть одна подходящая под условия задачи гипотеза, такая что в ней А — виновен.
С использованием этого предиката можно записать такой:
он ищет виновных, то есть таких подозреваемых, что виновны во всех гипотезах. Он проверяет что существует хоть один вариант генерации при котором Х виновен и что не существует ни одного варианта когда он не виновен.
Другим, типом логических задач являются задачи поиска в пространстве состояний.
Задачи поиска в пространстве состояний
Во многих логических задачах заданы начальное и конечное условия (состояния), и какие-либо правила поведения. Требуется найти последовательность действий, которая переведет из начального состояния в конечное. Условно, такие задачи можно разделить на 3 типа, которые мы рассмотрим на примерах.
Фиксированное число состоянийЕсли множество возможных состояний программы очень мало — то их можно задать руками в виде графа, где вершины — состояния, а дуги отражают возможность перехода между ними. Для решения задачи достаточно запустить поиск пути из начального состояния в конечное. Если требуется найти оптимальный путь, то к графу применяют алгоритм обхода в ширину, если же требуется найти все варианты решения — то обходят в глубину.
В качестве примера рассмотрим следующую задачу:
- Найди путь в лабиринте от входа до входа,не посещая дважды одной и той же комнаты;
- Найти путь с посещением золотой комнаты;
- Найти путь,избегающий запрещенных к посещению комнат.
Как именно выглядит лабиринт в задаче не сказано (нет информации о расположении переходов). Предположим, возможны следующие переходы:
Собственно, но этом решение закончилось, осталось написать 3 запроса (по запросу на каждый пункт задания):
Результаты выполнения запросов приведены на рисунках 3-5.
рис. 3 писк всех путей в лабиринте рис. 4 поиск путей через золотую комнату рис. 5 поиск путей без запрещенных комнат
Не все задачи поиска в пространстве состояний решаются так легко, состояний может быть настолько много, что мы не захотим формировать граф переходов руками. В этом случае, мы описываем только начальное состояние и правило порождения новых состояний. Попробуем сделать это на примере известной задачи о волке, козе и капусте.
У фермера есть волк, коза и капуста. Все они находятся на левом берегу реки. Необходимо перевезти это «трио» на правый берег, но в лодку может поместиться что-то одно — волк, коза или капуста. Нельзя оставлять на одном берегу волка с козой и козу с капустой.
Фермер может перевозить зверей как с левого берега на правый, так и с правого на левый, а может и проехать порожняком. Требуется соблюдать, чтобы в его отсутствие звери не угрожали друг другу, т.е. состояние должно включать не только информацию о животных каждом берегу, но и положение фермера. Зверей на каждом берегу удобно представить списком.
Программа должна начать работать из состояния, в котором волк, коза и капуста находятся на левом берегу, возле них сидит фермер. Чтобы получить решение, программа достраивает граф (добавляя новые состояния и дуги) и одновременно выполняет его обход, до тех пор, пока вся живность не будет перевезена на правый берег.
Схематично, начало процесса работы программы показано на рис. 6. Состояния изображены цветными овалами, возможность перехода отражают дуги. Зеленым цветом выделены «правильные» состояния, которые обрабатывается программой, красным — «неверные» состояния (в которых коза съест капусту или волк — козу), желтым — уже обработанные состояния. Программа должна рассматривать все состояния, выполнять проверку и добавлять в граф только зеленые.
рис. 6 дерево решения задачи о волке, козе и капусте
Для генерации новых состояний будем использовать правило permutation, которое выдаст нам все варианты подсписков заданной величины. В этой задаче, предел длины — 1, т.к. в лодке одно место. Когда подсписок будет получен, его нужно будет отнять от одного берега (правило subtraction) и прибавить к другому (стандартный предикат append).
Проверка корректности списка (правило check) и генерация новых состояний (правило generate) могут быть выражены следующим образом:
Разберем по строчкам правило генерации из состояния фермера на левом берегу:
- в 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) и процесс повторяется.
Генерация новых состояний при переходе с правого берега выполняется аналогично. Теперь, когда мы можем порождать новые состояния, осталось лишь слегка модифицировать правило обхода графа в ширину, чтобы получить решение задачи:
Видно, что в обычный обход графа в ширину, описанный ранее, была добавлена лишь третья строчка. Перед тем, как искать смежные вершины (вызов findall в 4 строке) надо их сгененировать, чем и занимается наш generate.
Запрос для машины логического вывода и решение, найденное прологом, приведены на рис. 7.
рис. 7 решение задачи о волке, козе и капусте
Задачу о волке, козе и капусте мы могли бы решить и при помощи обхода графа в глубину, но тогда мы нашли бы решение, которое было бы не оптимальным по количеству переправ. В ряде логических задач пространство состояний растет так быстро, что найти оптимальное решение достаточно трудно. В этих случаях применяют поиск в глубину. Примером может быть задача о супружеских парах:
Оптимизация поиска в прострастве состояний на PrologРассмотрим решение следующей задачи:
Пять супружеских пар необходимо переправить на трехместной лодке. Ни одна супруга не может находиться на берегу или в лодке без супруга.
Если мы попытаемся решить эту задачу также как предыдущую — нас ждала бы неудача, т.к. даже на первом шаге есть 120 вариантов посадить в лодку 3 человека, а можно ведь заполнить лодку не полностью (т.е. в дереве, подобном тому, что приведено на рис. 6 из начальной вершины выходило бы более 100 дуг). И это только на первом шаге. Однако, сделаем это чтобы было от чего отталкиваться.
Попытка решения 1
Программа должна поддерживать списки людей, находящихся на каждом берегу и в лодке, при этом для каждого из таких списков надо проверять условие задачи. Сделать это можно таким предикатом:
Предикат check_fail завершится успешно если условие задачи нарушается, то есть если в списке есть хоть одна женщина, при этом в этом списке нет ее мужа, но есть другой мужчина. Для поиска элемента в списке тут используется встроенный предикат member. Предикат check завершается успешно если выполнение check_fail с такими же аргументами проваливается.
На каждом шаге программа должна выбирать из списка подмножество, причем размером не более чем позволяет вместить лодка. Для этого вот тут был взят готовый предикат subset_length и написан вспомогательный:
Затем, были описаны правила перехода между состояниями. Если лодка находится слева — то из всех кто находится на левом берегу и в ложке формируется список, из которого выбираются те, кто поедет на правый берег. С правого берега аналогично:
Теперь, чтобы реализовать поиск в глубину достаточно перебирать состояния пока из текущего состояния можно куда то перейти:
этот предикат хранит список OldStates чтобы одни и теже персонажи не ездили туда-сюда.
Функция check проверялась таким запросом:
Функция выбора элементов списка таким:
?- subset_length_less([ma, mb, mc, md, me, fa,fb,fc,fd,fe], 3, Sub, Other).
При выполнении запроса на поиск решения:
Программа зависает — работает очень долго, дождаться результата не получается.
Попытка решения 2
Изучив вывод программы — порядок перебора состояний, можно заметить что несмотря на проверку — они все равно повторяются многократно:
Тут красным цветом выделены состояния, отличающиеся лишь порядком перевозки людей на правый берег. Повторяются не только эти состояния, но и многие другие.
Проблема возникает потому, что вызов
проверяет что состояние раньше не встречалось, но при этом проверяется лишь точное совпадение списков. Решить проблему можно отсортировав списки людей. Для этого заведена функция сортировки всех списков в состоянии:
, а перед поиском текущее состояние тоже сортируется:
При запуске с такой целью:
Программа дает результат, но он в крайне ненаглядном формате. Программа находит путь из 533 шагов.
Чисто формально результат верный и на этом можно остановиться. Для перевода вывода в более наглядный формат написан такой предикат:
Дело в том, что состояния загрузки людей в лодку и выгрузки чередуются и направление лодки удобно показывать стрелками.
Попытка решения 3
На скриншоте выше видна проблема, но она заключается не в том, что лодка плавает пустая, а в том, что одно и тоже состояние многократно повторяется. Если на правый берег перевезено 3 женщины — то каждую из них можно очереди перевести на левый, а потом перевести их парами…
В процессе поиск решения этой задачи так или иначе формируется дерево состояний. Схематично такое дерево показано на рисунке:
Можно было бы попробовать заменить поиск в глубину в этой задаче на поиск в ширину. Однако, это не даст результат, так как дерево растет очень быстро, и если поиск в глубину хранит в памяти только последний узел — то поиск в ширину хранит все узлы текущего яруса дерева.
На этом рисунке очень схематично показано что из начального состояния можно было бы сначала перевезти пару А или пару Б или пару Е, или …. Если перевезена пара А — то затем можно перевезти пару Б или пару Е или …. Тут видно, что при перевезти пары А, Б, Е можно различными способами — [A, B, E] или [E, A, B] или … всего N! вариантов. Где N — количество пар. Однако, это не точная интерпретация задачи, ведь по условию задачи можно посадить в лодку, например, трех женщин или двух или одну. А можно посадить трех мужчин если на берегу остались одни женщины и так далее.
Решение проблемы заключается с сохранении полученных ранее результатов в каком-то виде. Дело в том, что часто не важен точный порядок элементов, а важно лишь их количество. В данной задаче можно предположить что два решения в которых на берегах и в лодке одинаковое количество пар и свободных женщин будут эквиваленты. Дело в том, что не важно пара А в лодке или пара Б.
Для сохранения в памяти найденных решений используем базу данных, добавим для этого такие предикаты:
Первые 2 предиката выбирают соответственно женщин и пары из списка. Вторые два — считают их количество с помощью встроенных функций findall и length .
Предикат state_to_db преобразует состояние программы, которое использовалось ранее в структуру info , которая хранит что то типа хэша состояния.
Наконец, предикат if_new_state_add проверяет наличие факта а БД и если его нет — добавляет его. Исходный код программы целиком: