ИИСС. Практикум решения задач по курсу Основы искусственного интеллекта

• Название: Практикум решения задач по курсу Основы искусственного интеллекта
• Дата: 17.11.2022
• Размер: 0.73 Mb.
• Имя файла: metod_VP.doc
• Тип: Практикум; #795277
• страница: 3 из 8

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Доработайте исходный код примера следующим образом:

1) добавьте новое правило бабушка и определите, кто является бабушкой;

2) добавьте новое правило внук и определите, кто внук Анны;

3) добавьте новое правило брат и определите, кто брат Димы;

4) добавьте новое правило сестра и определите, кто сестра Ивана.

Отчет о выполненной самостоятельной работе должен содержать:

1. 
   тему лабораторной работы;
   
2. 
   условие задачи;
   
3. 
   полный окончательный код примера;
   
4. 
   результаты ее тестирования.
   

1.4 Поиск с возвратом

Поиск с возвратом (backtracking) – это один из основных приемов поиска решений поставленной задачи в ПРОЛОГ’е. Выполняя поиск, ПРОЛОГ может столкнуться с необходимостью выбора между альтернативными путями. Тогда он ставит маркер у места развилки (точка отката) и выбирает первую подцель. Если она не выполняется, то ПРОЛОГ возвращается в точку отката и переходит к следующей подцели.

Среда Visual Prolog позволяет использовать отладчик для пошагового выполнения программы. Отладчик работает с откомпилированным кодом. В исходном коде можно ставить точки останова и выполнять программу по шагам. В режиме пошагового выполнения программы можно просматривать значения переменных и содержимое утвержденных фактов.
Пример

Имеется база данных, содержащая факты вида отдыхает(имя, город), украина(город), россия(город), прибалтика(город). Составить правило, позволяющее определить, кто отдыхал в России.

Проследить поиск решения задачи с помощью отладчика Visual Prolog и построить целевое дерево поиска с возвратом.

Решение:

1. Создайте новый проект (Project | New Project) и наберите текст программы:

DOMAINS

имя, город=string

PREDICATES

отдыхает(имя, город)

украина(город).

россия(город).

прибалтика(город).

отдых_Россия(имя)

CLAUSES

отдыхает(sasha, antalia).

отдыхает(anna, sochi).

отдыхает(dima, urmala).

отдыхает(oleg, kiev).

украина(kiev).

россия(sochi).

прибалтика(urmala).

отдых_Россия(X):-

отдыхает(X,Y),

россия(Y).

GOAL

отдых_Россия(X),

write(X),nl.
3. Сохраните проект (Project | Save Project)
4. Запустите его на исполнение ( Project | Run, или клавиша , или кнопка ). Результат выполнения программы:

anna
5. Проследите поиск этого решения с помощью отладчика(Debugger). Для этого:

а) запустите отладчик (Project | Debug);

б) в окне отладчика выберите команду View | Local Variables (для просмотра текущих значений переменных);

в ) нажимайте клавишу (или Run | Trace Into) для пошагового выполнения программы, текущие значения переменных отображаются в окне Variables For Current Clause



рис.9. Окно отладчика

Поиск решения можно представить следующим образом:


решение: X= anna

рис.10. Целевое дерево поиска решения

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. База данных содержит следующие факты:

увлекается(“Коля”, гитара).

увлекается(“Оля”, скрипка).

увлекается(“Дима”, плаванье).

увлекается(“Таня”, теннис).

спорт(плаванье).

спорт(теннис).

муз_инстр(скрипка).

муз_инстр(гитара).

а) составить правило спортсмен и определить, кто увлекается спортом;

б) проследить за поиском решения с помощью отладчика;

в) построить целевое дерево поиска с возвратом.
2. База данных содержит следующие факты:

увлекается(“Дима”, плаванье).

увлекается(“Таня”, теннис).

увлекается(“Коля”, гитара).

увлекается(“Оля”, скрипка).

спорт(плаванье).

спорт(теннис).

муз_инстр(скрипка).

муз_инстр(гитара).

а) составить правило музыкант и определить, кто увлекается музыкой;

б) проследить за поиском решения с помощью отладчика;

в) построить целевое дерево поиска с возвратом.

Отчет о выполненной самостоятельной работе должен содержать:

1. 
   тему лабораторной работы;
   
2. 
   условие задачи;
   
3. 
   листинг программы;
   
4. 
   результаты ее тестирования;
   
5. 
   целевое дерево поиска решения.
   

1.5 Управление поиском с возвратом:
предикаты fail и отсечения.

fail – это тождественно-ложный предикат, искусственно создающий ситуацию неуспеха. После выполнения этого предиката управление передается в точку отката и поиск продолжается. Использование предиката fail позволяет найти все решения задачи.

Чтобы ограничить пространство поиска и прервать поиск решений при выполнении какого-либо условия, используется предикат отсечения (обозначается !), Однажды пройдя через отсечение, невозможно вернуться назад, т.к. этот предикат является тождественно-истинным. Процесс может только перейти к следующей подцели, если такая имеется.

Например, p :- p1, p2, !, p3.

Если достигнуты цели p1 и p2, то возврат к ним для поиска новых решений невозможен.
Пример 1

База данных содержит факты вида: student(имя, курс). Создать проект, позволяющий сформировать список студентов 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("Список студентов 1-курса"),nl,spisok.
Результат выполнения программы:

Список студентов 1-курса

lena

dima

marina

Пример 2

База данных содержит факты вида father(name, name). Создать проект, позволяющий определить кто чей отец.

Решение:

DOMAINS

name=symbol

PREDICATES

father (name, name)

everybody

CLAUSES

father ("Павел", "Петр").

father ("Петр", "Михаил").

father ("Петр", "Иван").

everybody:- father (X, Y),

write(X," - это отец",Y,"а"),nl,

fail.

GOAL

everybody.
Результат выполнения программы:

Павел - это отец Петра

Петр - это отец Михаила

Петр - это отец Ивана
Пример 3

Создать проект, реализующий железнодорожный справочник. В справочнике содержится следующая информация о каждом поезде: номер поезда, пункт назначения и время отправления.

а) вывести всю информацию из справочника.

Решение:

DOMAINS

nom=integer

p, t=string

PREDICATES

poezd(nom,p,t)

CLAUSES

poezd(233,moskva,"12-30").

poezd(257,moskva,"22-40").

poezd(133,armavir,"10-20").

poezd(353,armavir,"20-40").

poezd(353,adler,"02-30").

poezd(413,adler,"11-10").

poezd(256,piter,"21-30").

GOAL

write(" Расписание поездов"), nl,

write("Номер Пункт прибытия Время отправления"),

nl, poezd(N,P,T), write(N," ",P," ",T),nl,fail.

Результат выполнения программы

Расписание поездов

Номер Пункт прибытия Время отправления

233 moskva 12-30

257 moskva 22-40

133 armavir 10-20

353 armavir 20-40

353 adler 02-30

413 adler 11-10

256 piter 21-30
б) организовать поиск поезда по пункту назначения.

Решение:

GOAL

write (" Пункт назначения:"), Readln(P), nl,

write ("Номер Время отправления"), nl,

poezd(N,P,T), write(N," ",T), nl, fail.
Комментарий: Readln –стандартный предикат ввода строкового значения
Результат выполнения программы

Пункт назначения:armavir
Номер Время отправления

133 10-20

353 20-40

в) вывести информацию о поездах, отправляющихся в заданный временной промежуток

Решение:

GOAL

write(" Время отправления:"),nl,

write("c..."), Readln(T1),

write("до..."), Readln(T2), nl,

write("Номер Пункт назначения Время отправления"),

nl,poezd(N,P,T),T>=T1,T<=T2,write(N," ",P," ", T),

nl, fail.
Результат выполнения программы

Время отправления:

c...10-00

до...15-00
Номер Пункт назначения Время отправления

233 moskva 12-30

133 armavir 10-20

413 adler 11-10

Пример 4

Имеется база данных, содержащая данные о спортсменах: имя и вид спорта. Определить возможные пары одного из спортсменов-теннисистов с другими теннисистами.

Решение:

DOMAINS

имя,вид_сп=string

PREDICATES

играет(имя,вид_сп)

спис_спортс

CLAUSES

играет("Саша",теннис).

играет("Аня",волейбол).

играет("Олег",футбол).

играет("Коля",теннис).

играет("Саша",футбол).

играет("Андрей",теннис).

спис_спортс:- играет(X,теннис),!,играет(Y,теннис),

X<>Y,write(X,"-",Y),nl,fail.

GOAL

write("Пары теннисистов"),nl,

спис_спортс.
Результат выполнения программы:

Пары теннисистов

Саша-Коля

Саша-Андрей
Пример 5

Студенту в зависимости от набранной в процессе обучения суммы баллов Z присваивается квалификация:

магистр (М), если 80<=Z<=100

специалист (S), если 60<= Z< 80

бакалавр (B), если 40<= Z< 60

неудачник (N), если 0<=Z< 40

Составить программу, которая определит квалификацию в зависимости от введенного значения Z

Решение:

Для решения задачи составим правило grade, устанавливающее связь между количеством баллов (z) и квалификацией (r). Правило состоит из нескольких частей. Первые две части обеспечивают проверку недопустимых значений Z с выводом соответствующего сообщения. Остальные части правила определяют квалификацию в зависимости от значения Z.

DOMAINS

z=integer

r=string

PREDICATES

grade(z,r)

CLAUSES

grade(Z,""):-Z<0,!, write("Неверный ввод данных!").

grade(Z,""):-Z>100,!,write("Неверный ввод данных!").

grade(Z,"M"):-Z>=80,!.

grade(Z,"S"):-Z>=60,!.

grade(Z,"B"):-Z>=40,!.

grade(Z,"N").

GOAL

write("Z="), readint(Z), grade(Z,R),write(R).
Комментарий: readint – стандартный предикат ввода целочисленного значения
Результат выполнения программы:

1-й случай:

Z=88

M

2-й случай:

Z=65

S

3-й случай:

Z=39

N

4-й случай:

Z=110

Неверный ввод данных!