Ссылка на файл: >>>>>> http://file-portal.ru/Решение логических задач на прологе/
Решение логических задач на Prolog
Лекция 25. Пролог. Решение логических задач
Тема: Логические задачи на языке программирования Prolog
Заказать решение задачи на Prolog или попросить помощь. Язык пролог начал зарождаться в далеком году, точнее в этом году известный ученый Людвиг Фреге предложил исчисление предикатов, которое лежит в основе логического программирования. Фреге был не только математиком, но и философом как и большинство других известных ученых своего времени. В то время еще не начала рушиться классическая картина мира, популярным философским учением являлся позитивизм Конта, и Фреге разделял эти взгляды, относясь к школе аналитической философии. Одной из своих задач философы видели формализацию знаний, то есть пытались выразить знания на более точном, научном языке, например так, как делают математики. Работы по исчислению предикатов лаконично вписались в это направление. Позже по этой теме работали другие известные философы, такие как Бертран Рассел и Людвиг Витгенштейн, представители более новой школы логического позитивизма. Исследования ведутся до сих пор, но позитивисты несколько отошли от исчисления предикатов в сторону темпоральной логики. В х годах уже появились эффективные реализации Пролога и он рассматривался как универсальный язык, при этом использовался для реализации реляционных СУБД, автоматического доказательства теорем, разработки компиляторов, САПР и других областях [1]. В начале х годов пролог продвигался, в большей мере, как удобное средство разработки графического интерфейса лучших инструментов тогда не было [4]. В году провалился японский национальный проект компьютера пятого поколения, одной из целей которого было исследование искусственного интеллекта. В качестве языка программирования этого компьютера был выбран пролог, популярность которого резко упала [5]. В настоящее время, пролог используется , в основном, при разработке трансляторов и в задачах искусственного интеллекта [6]. Более подробно про историю языка Пролог можно почитать в толстых книгах [1, 2, 3], но а я привел эти факты чтобы чуть-чуть отразить особенности развития этого языка и решаемых на нем задач. Ноги у этих задач растут из автоматического доказательства теорем. В статье рассматривается 2 типа логических задач — задачи на установление соответствия и задачи поиска в пространстве состояний. Задачи на установление соответствия очень похожи на работу Шерлок Холмса, в них дается набор фактов, которые надо увязать между собой чтобы найти решение. Машина логического вывода решает такие задачи полным перебором, никакого пути поиска решения при этом нет. Как то раз случай свёл в купе астронома, поэта , прозаика и драматурга. Это были Алексеев, Борисов, Константинов и Дмитриев. Оказалось, что каждый из них взял с собой книгу написанную одним из пассажиров этого купе. Алексеев и Борисов углубились в чтение предварительно обменявшись книгами. Поэт читал пьесу, прозаик — очень молодой человек, выпустивший свою книгу, говорил что он никогда и ни чего не читал по астрономии. Борисов купил одно из произведений Дмитриева. Никто из пассажиров не читал свои книги. Что читал каждый из них, кто кем был? Перед тем, как запросить у машины логического вывода решение задачи, необходимо формализовать имеющиеся факты. В этой задаче даны 4 имени, 4 профессии и 4 вида книг. Профессии задавать не обязательно, так как профессию можно вывести из книги. Чтобы получить решение, надо попросить машину логического вывода найти четырех таких пассажиров с разными именами, читающих, написавших и купивших разные книги. Вспомогательный предикат unique, следящий за тем, чтобы элементы в списке не повторялись, описан в соседней статье: Задачи на списки [Prolog]. Если запустить такое правило — мы получим все варианты решения без учета ограничений, описанных в задаче. Для проверки того, что никто не читает и не покупал свою книгу потребуется вспомогательное правило:. В результате своей работы, программа выдает 2 решения, оба их которых подходят ко всем условиям задачи. Три друга заняли первое, второе и третье места в соревнованиях универсиады. Друзья — разной национальности, зовут их по-разному и любят они разные виды спорта. Майкл предпочитает баскетбол и играет лучше чем американец. Израильтянин Саймон играет лучше теннисиста. Игрок в крикет занял первое место. Решение задачи опять начинается с формализации фактов. Пролог не знает что теннис — это спорт, а Саймон — имя. Сообщим ему об этом:. Запросить у пролога решение можно следующим образом:. Видно, что решение этой и предыдущей задачи очень похожи. По приведенному шаблону решается множество логических задач, ориентированных на перебор. Другим, типом логических задач являются задачи поиска в пространстве состояний. Во многих логических задачах заданы начальное и конечное условия состояния , и какие-либо правила поведения. Требуется найти последовательность действий, которая переведет из начального состояния в конечное. Условно, такие задачи можно разделить на 3 типа, которые мы рассмотрим на примерах. Если множество возможных состояний программы очень мало — то их можно задать руками в виде графа, где вершины — состояния, а дуги отражают возможность перехода между ними. Для решения задачи достаточно запустить поиск пути из начального состояния в конечное. Если требуется найти оптимальный путь, то к графу применяют алгоритм обхода в ширину , если же требуется найти все варианты решения — то обходят в глубину. Лабиринт представляет собой систему комнат,соединенных между собой переходами. В лабиринте имеется вход и выход,а также комната с золотым кладом. Кроме того,имеются комнаты,запрещенные для посещений: Как именно выглядит лабиринт в задаче не сказано нет информации о расположении переходов. Предположим, возможны следующие переходы:. Собственно, но этом решение закончилось, осталось написать 3 запроса по запросу на каждый пункт задания:. Не все задачи поиска в пространстве состояний решаются так легко, состояний может быть настолько много, что мы не захотим формировать граф переходов руками. В этом случае, мы описываем только начальное состояние и правило порождения новых состояний. Попробуем сделать это на примере известной задачи о волке, козе и капусте. У фермера есть волк, коза и капуста. Все они находятся на левом берегу реки. Нельзя оставлять на одном берегу волка с козой и козу с капустой. Фермер может перевозить зверей как с левого берега на правый, так и с правого на левый, а может и проехать порожняком. Требуется соблюдать, чтобы в его отсутствие звери не угрожали друг другу, то есть состояние должно включать не только информацию о животных каждом берегу, но и положение фермера. Зверей на каждом берегу удобно представить списком. Программа должна начать работать из состояния, в котором волк, коза и капуста находятся на левом берегу, возле них сидит фермер. Чтобы получить решение, программа достраивает граф добавляя новые состояния и дуги и одновременно выполняет его обход, до тех пор, пока вся живность не будет перевезена на правый берег. Схематично, начало процесса работы программы показано на рис. Состояния изображены цветными овалами, возможность перехода отражают дуги. Программа должна рассматривать все состояния, выполнять проверку и добавлять в граф только зеленые. В этой задаче, предел длины — 1, так как в лодке одно место. Когда подсписок будет получен, его нужно будет отнять от одного берега правило subtraction и прибавить к другому стандартный предикат append. Проверка корректности списка правило check и генерация новых состояний правило generate могут быть выражены следующим образом:. Разберем по строчкам правило генерации из состояния фермера на левом берегу:. Генерация новых состояний при переходе с правого берега выполняется аналогично. Теперь, когда мы можем порождать новые состояния, осталось лишь слегка модифицировать правило обхода графа в ширину , чтобы получить решение задачи:. Видно, что в обычный обход графа в ширину, описанный ранее, была добавлена лишь третья строчка. Перед тем, как искать смежные вершины вызов findall в 4 строке надо их сгененировать, чем и занимается наш generate. Запрос для машины логического вывода и решение, найденное прологом, приведены на рис. Задачу о волке, козе и капусте мы могли бы решить и при помощи обхода графа в глубину , но тогда мы нашли бы решение, которое было бы не оптимальным по количеству переправ. В ряде логических задач пространство состояний растет так быстро, что найти оптимальное решение достаточно трудно. В этих случаях применяют поиск в глубину. Примером может быть задача о супружеских парах: Во время наводнения пять супружеских пар оказались отрезанными от суши водой. В их распоряжении была одна лодка, которая могла одновременно вместить только трех человек. Каждый супруг был настолько ревнив, что не мог позволить своей супруге находиться в лодке или на другом берегу с другим мужчиной или мужчинами в его отсутствие. Найти способ переправить на сушу этих мужчин и жен в целости и сохранности. Если мы попытались бы решить эту задачу также как предыдущую — нас ждала бы неудача, так как даже на первом шаге есть вариантов посадить в лодку 3 человека, а можно ведь заполнить лодку не полностью то есть в дереве, подобном тому, что приведено на рис. И это только на первом шаге. Очевидно, поиск в ширину по крайней мере, обычный не сработает в этой ситуации. Задачу можно решить поиском в глубину. Для начала, опишем пары и правила проверки списка на правильность пары в списке не должны быть разрушены:. По условию, в лодке пары тоже могут разрушиться, поэтому в программе, состояние выражается не двумя списками, а тремя. Кроме того, состояние, как и в предыдущей задаче содержит положение лодки. Правило proliferate , приведенное выше перегоняет лодку с одного берега на другой. При перегоне лодки с левого берега на правый, с берега в лодку набираются люди строка 3. При перегоне с правого берега на левый, часть людей высаживаются с лодки строка В принципе, можно научить пролог набирать людей на обоих берегах, но тогда он будет искать решение слишком долго. Как и в предыдущей задачи, обход графа лишь незначительно изменится но на этот раз, обход в ширину:. В первой строке описано условие, отражающее конечное состояние — берег и лодка пусты. В третьей строке вместо выбора дуги из вершины А в вершину X выполняется генерация этой дуги правилом proliferate. Решение логических задач — обширная тема, по которой написаны толстые и даже современные книги [ 7,8 ], которые явно стоит посмотреть всем небезразличным. Безразличные тоже могут почитать для расширения кругозора. В задаче про ревнивых мужей лодка один раз ходит пустая. Разве такое допустимо по условию задачи? Если ставить в предикате перевозки проверку наличия людей в лодке, то не выходит перевезти. Видимо, надо будет всё таки добавить возможность забора людей с правого берега, или даже высадки их на левом берегу. Попробовал это сделать, теперь вечно false получаю. В задании не оговорены операции над лодкой, я решил упростить задачу чтобы не усложнять код, но переборщил. Тут добавлены проверка пустоты лодки во время отплытия и возможность посадки в лодку людей с правого берега. Высадку людей с лодки на левый берег я добавлять не стал, чтобы не усложнять код: Решение сейчас выглядит примерно так:. Всё отлично работает, спасибо за ответ. Теперь стало интересно, как можно избежать бессмысленной переправы fe туда обратно перед конечным состоянием. Чтобы бессмысленную переправу fe устранить, надо высадить его сразу с me. Высаживается он отдельно, потому что правило sublist написано так, как написано. Можно переписать sublist так, чтобы первым делом оно возвращало исходный список ведь он является собственным подсписком , однако в этом случае постоянно одни и те же люди будут кататься туда-обратно на лодке. Поэтому sublist лучше не трогать, мне кажется что без этого можно обойтись. Здравствуйте, спасибо большое за ответ, но мне кажется, или если убрать отсечение оно будет выдавать бесконечное число одинаковых решений? Я согласна, что выдавать все решения это не очень хорошая затея, но это упражнение, чтобы продемонстрировать работу поиска по графу, что решения ветвятся, пока не получается это понять. И еще мне даже стало интересно, не могли бы вы подробнее рассказать также и про поезда, пожалуйста, как можно реализовать поиск и генерацию состояний. Я не совсем уверен, что количество решений будет бесконечным, но абсолютно уверен, что не все решения будут одинаковыми. Поиск одного решения — это тоже поиск в графе. Чтобы показать процесс поиска решения можно вставить куда-нибудь отладочную печать. Я уже привел фрагмент кода генерации состояний к задаче о поездах и рассказал как его можно дописать. Что конкретно не получается? Всё, чего Вы добились таким изменением кода — избавились от проверок лодки у правого берега и самого берега. Нет никаких сомнений, что она должна выполняться при таком коде. Простите за отсутствие конструктива, сам нахожусь в поиске корректного решения. Добавлена проверка того, что если на левом берегу уже пусто — то из лодки всегда стоит высадить всех людей. Хотя нет смысла в такой проверке, я думаю. Как использовался поиск в глубину, так и используется. Оптимальность решения не гарантируется. Если нужно избежать всех бессмысленных переправ — надо писать поиск в ширину. Но вопрос стоял так:. Поправил статью — вместо dif теперь нужно использовать предикат subtraction. Заменил название и поправил ссылку. Но теперь вы используете Sublist вместо permutation. Как он реализован подскажите пожалуйста. Тут использовалась нестандартная реализация предиката permutation, генерирующая перестановки, длина которых не превышает заданного значения, однако в SWI Prolog встроена функция, генерирующая перестановки заданной длины. В связи с этим я заменил свою реализацию и эта задача перестала работать. Я поправил статью, проверил корректность работы решения. Для отправки комментария вам необходимо авторизоваться. Блог программиста Программирование и туризм. Заказать решение задачи на Prolog или попросить помощь Язык пролог начал зарождаться в далеком году, точнее в этом году известный ученый Людвиг Фреге предложил исчисление предикатов, которое лежит в основе логического программирования. Логические задачи Задачи на установление соответствия Задачи на установление соответствия очень похожи на работу Шерлок Холмса, в них дается набор фактов, которые надо увязать между собой чтобы найти решение. Примером такой головоломки может быть задача про купе: Пассажир купе будет описываться фактом passenger: Для проверки того, что никто не читает и не покупал свою книгу потребуется вспомогательное правило: Остальные ограничения можно описать следующим образом: Добавить комментарий Отменить ответ Для отправки комментария вам необходимо авторизоваться.
Тесты бухгалтер тмц 2017
Больная любовь стихи
Новости чита торговый
Решение логических задач в ПРОЛОГе
Сколько времени делается иннв налоговой
Где логика 1 часть 64 уровень
Куры амераукана фото и описание
РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ НА ПРОЛОГЕ
Программирование классы и методы
Где можно недорого поесть в берлине
Решение логических задач
Сколько километров высота эверест
План воспитательных мероприятий в школе на год
Как оценить ущерб от затопления квартиры самостоятельно
РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ НА ПРОЛОГЕ
Пинг как проверить бесконечно