Лабораторный практикум пролог. Методические рекомендации по дисциплине Анализ данных
 Скачать 311.21 Kb.
|
|
Краткие теоретические сведения В отличие от процедурных языков, в которых программист должен точно описать процесс решения задачи, Пролог является описательным (декларативным) языком. Программа на Прологе содержит описание проблемы, для этого используются правила и факты, и цель. Выполнение программы заключается в попытке доказать целевое утверждение, используя предположения, заданные в программе. Механизм поиска решений “встроен” в Пролог, он называется “поиск с возвратом”. Поиск с возвратом (backtracking) - это один из основных приемов поиска решений поставленной задачи в ПРОЛОГ'е. Выполняя поиск, ПРОЛОГ может столкнуться с необходимостью выбора между альтернативными путями. Тогда он ставит маркер у места развилки (точка отката) и выбирает первую подцель. Если она не выполняется, то ПРОЛОГ возвращается в точку отката и переходит к следующей подцели. Пример 1. Рассмотрим программу, которая содержит сведения об именах и возрасте нескольких игроков в теннисном клубе. Цель состоит в подборе пары игроков, возраст которых 9 лет. Решение: DOMAINS child = symbol age = integer PREDICATES player(child, age) /*игрок(ребенок, возраст)*/ CLAUSES player(peter, 9). player(paul, 10). player(chris, 9). player(susan, 9). Goal player(Person1,9),player(Person2,9),Person1<>Person2, write(Person1, “-“,Person2). На первом шаге ПРОЛОГ пытается найти решение для первой подцели player(Person1,9). Эта подцель согласуется путем сопоставления Person1 с peter, так как Пролог просматривает утверждения для согласования сверху вниз. После достижения первой подцели ПРОЛОГ переходит ко второй подцели: player(Person2,9). Эта подцель опять согласуется при сопоставлении Person2 с peter. На следующем шаге ПРОЛОГ переходит к согласованию третьей подцели: Person1<>Person2. Так как Person1 и Person2 имеют значения peter, то данная подцель не согласуется, и Пролог осуществляет откат к предыдущей подцели player(Person2,9). Эта подцель сопоставляется с фактом player(chris,9), и Person2 согласуется с crhis .Теперь Пролог опять в качестве текущей подцели выполняет цель Person1<>Person2 . Эта подцель успешна, так как peter и chris отличны. Таким образом, ПРОЛОГ согласовал все подцели целевого утверждения, и цель считается согласованной. Получена пара игроков: Peter- Chris. Результат выполнения программы: Peter - chris Среда Visual Prolog позволяет использовать отладчик для пошагового выполнения программы. Отладчик работает с откомпилированным кодом. В исходном коде можно ставить точки останова и выполнять программу по шагам. В режиме пошагового выполнения программы можно просматривать текущие значения переменных и содержимое утвержденных фактов. Пример 2. Имеется база данных, содержащая факты вида отдыхает(имя, город), украина(город), россия(город), прибалтика(город). Составить правило, позволяющее определить, кто отдыхал в России. Проследить поиск решения задачи с помощью отладчика Visual Prolog и построить целевое дерево поиска с возвратом. Решение: 1. Создайте новый проект (Project | New Project) и наберите текст программы: DOMAINS имя, город= symbol PREDICATES отдыхает(имя, город) украина(город). россия(город). прибалтика(город). отдых_Россия(имя) CLAUSES отдыхает(sasha, antalia). отдыхает(anna, sochi). отдыхает(dima, urmala). отдыхает(oleg, kiev). украина(kiev). россия(sochi). Прибалтика(urmala). отдых Россия^) отдыхает(X,Y), россия(Y). GOAL отдых РоссияШ, write(X),nl. Сохраните проект (Project | Save Project) Запустите его на исполнение ( Project | Run, или клавиша anna Проследите поиск этого решения с помощью отладчика^еЬиддег). Для этого: а) запустите отладчик (Project | Debug); б) в окне отладчика выберите команду View | Local Variables (для просмотра текущих значений переменных); в) нажимайте клавишу  рис.9. Окно отладчика Поиск решения можно представить следующим образом:  рис.10. Целевое дерево поиска решения Управление поиском с возвратом заключается в решении двух задач: включении поиска с возвратом при необходимости найти все возможные решения задачи и отключении поиска с возвратом для ограничения пространства поиска. Для решения этих задач используются два стандартных предиката: fail и отсечение. fail - это тождественно-ложный предикат, искусственно создающий ситуацию неуспеха. После выполнения этого предиката управление передается в точку отката и поиск продолжается. Чтобы прервать поиск решений при выполнении какого-либо условия, используется предикат отсечения (обозначается !), Однажды пройдя через отсечение, невозможно вернуться назад, т.к. этот предикат является тождественно-истинным. Процесс может только перейти к следующей подцели, если такая имеется. Например, p :- p1, p2, !, p3. Если достигнуты цели p1 и p2, то возврат к ним для поиска новых решений невозможен. Пример 3 База данных содержит факты вида: stiulent(iLMH, курс). Создать проект, позволяющий сформировать список студентов 1-го курса. Решение: PREDICATES student(symbol,integer) spisok CLAUSES student(vova,3). student(lena,1). student(dima,1). student(ira,2). student(marina,1). spisok:-student(X,1),write(X),nl,fail. GOAL write("Сnисок студентов 1-курса"),nl,spisok. |