Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

define_window, current_window, delete_window, create_popup, exit_popup.

'меню':- repeat, создать_окно_для_меню,

перейти_из_текущего_окна_в_окно_меню,

write('Открыть красное окно'),

write('Открыть желтое окно'),

read(X), процесс(X).

процесс(красное):- открыть_окно,

перейти_из_текущего_окна_в_красное,

write('Закрыть_окно?'),read(X),

удаление_окна(X),!,fail.

.....................................

процесс(Выход).

1. ИСПОЛЬЗОВАНИЕ НАДРЕЗОВ (SNIP).

Надрез обозначается открывающей скобкой [! и закрывающей скобкой !]. Например, для правила

цель:- подцель1,[! подцель2,подцель3 !],подцель4.

действие надреза распространяется на подцели подцель2 и подцель3, расположенные между этими двумя скобками.

Snip аналогичен cut, однако отличается от него тем, что если после бектрекинга управление передастся snip, весь предикат неуспешным не будет. Бектрекинг лишь "пропустит" те подцели, которые находятся внутри snip и продолжится для подцелей, которые расположены раньше snip.

Отличие надреза от отсечения:

Надрезы целесообразно использовать в случаях, когда нужно ограничить бектрекинг для исключения ненужного поиска, но отсечение не требуется.

Задание 8. Используйте базу данных из задания 6 лабораторной работы 1 (стр. 8). Добавьте факты для каждого животного X

'животное'(X).

Для исключения повторения названия животных на запросы

"Кто живет хотя бы (ровно) в двух средах обитания?"

II. СПИСКИ

ЦЕЛЬ. Знакомство с понятием списка и операциями над списками.

Список - это упорядоченная последовательность элементов. Элементами списка могут быть любые термы Пролога. Удобной формой записи списков является так называемое списочное обозначение. В данном обозначении каждый элемент списка отделяется от соседнего запятой, а весь набор элементов заключается в квадратные скобки, например, [a,b,c,d].

Фактически список - это структура с функтором ' .'/2 (точка с арностью 2). Согласно этому определению, список состоит из первого элемента и хвоста, который представляет собой список из остальных элементов.

Пустой список - это список, не содержащий ни одного элемента, он обозначается [].

Примеры.

№	элементы списка	запись со скобками	запись с функтором "."
1	a	[a]	'.'(a,[])
2	a b c	[a,b,c]	'.'(a,'.'(b,'.'(c,[])))
3	[a]	[[a]]	'.'([],[])
4	[]	[[]]	'.'('.'(a,[])
5	[a] [b,c]	[[a],[b,c]]	'.'(b,'.'(c,[])))

1 2 3 4 5

. . . . .

/ \ / \ / \ / \ / \

a [] a ^{. .} [] [] [] ^{. .}

/ \ / \ / \ / \

b ^. a [] a [] b ^.

/ \ / \

c [] c []

Список унифицируется с другим списком, если попарно унифицируются их элементы.

write('Открыть зеленое окно'),

write('Выйти из меню), убрать_окно,

Список может делиться на "голову" и "хвост" с помощью операции отделения головы, которая обозначается вертикальной чертой (|), т.е. [Голова|Хвост].

Голова - фиксированное количество элементов. Хвост - список из оставшихся элементов списка. Чаще всего используется голова, состоящая из одного элемента.

В виде дерева список [X|Y] изображается следующим образом:

.

/ \

X Y

Примеры сопоставления списков со списком [Голова|Хвост]

Список [1,2|[3,4]] равен списку [1,2,3,4]. При сопоставлении со списком [X,Y|Z] получим X=1, Y = 2 и Z = [3,4].

. .

/ \ / \

X ^{. 1 .}

/ \ / \

Y Z 2 ^.

/ \

3 ^.

/ \

4 []

В Arity/Prolog имеется особый вид списков - символьные списки. Символьный список – это фактически последовательность целых чисел, соответствующих ASCII-коду символов. Символьные списки заключаются в двойные кавычки. Следующие три списка являются сопоставимыми:

"abc" [ 97, 98, 99 ] ' .'(97,' .' (98,'.' (99),[])))

write_list([]).

write_list([H|T]):- /* разделение списка на голову и хвост, */

write(H), nl, /* печать головы, пропуск строки */

write_list(T). /* рекурсивный вызов предиката от

оставшегося списка */

Задание 9. Запустите программу 1, посмотрите результат для списка [1,2,a,3].

Программа 2. Конкатенация и разбиение списков.

append([],List,List).

append([X|L1],List2,[X|L3):-append(L1,List2,L3).

Задание 10. Используя предикат append(X,Y,Z), осуществите склейку списков [1,2,3] и [4,5], вычитание списка [4,5] из [1,2,3,4,5]) и "разбиение" списка на две части в режиме трассировки.

Задание 11. Используя понятие списка, напишите программы для решения следующих задач:

1. Определение длины списка.

(Длина пустого списка равна 0. Длина непустого списка равна длине его хвоста плюс 1).

1. Определение принадлежности элемента к списку. (Элемент принадлежит списку, если он - его голова. Элемент принадлежит списку, если он принадлежит хвосту списка.)

2. Поиск суммы элементов числового списка.

3. Поиск максимального и минимального элементов числового списка с использованием одной рекурсии.

4. Инверсия списка.

Задание 12. Напишите программу сортировки числового списка методом "пузырька".

ЧАСТЬ II. ПРИКЛАДНЫЕ ЗАДАЧИ ИИ

ЛАБОРАТОРНАЯ РАБОТА №4

СТРАТЕГИИ ПОИСКА ПУТИ НА ГРАФЕ

1. Стратегия поиска в глубину

Логический вывод по существу сводится к достижению цели G на основе последовательного процесса доказательства истинности (или ложности) частичных целей через механизм унификации и возвратов.

Существуют различные подходы к проблеме поиска решающего пути для задач, сформулированных в терминах пространства состояний.

Пространство состояний – это граф, вершины которого соответствуют ситуациям, встречающимся в задаче, а решение задачи сводится к поиску пути на графе. Вершины графа соответствуют проблемным ситуациям, дуги – разрешенным переходам из одних состояний в другие. Задача отыскания плана решения задачи эквивалентна задаче построения пути между заданной начальной ситуацией и некоторой указанной заранее конечной ситуацией, называемой целевой вершиной. В терминах пространства ситуаций основными стратегиями поиска являются стратегии поиска в глубину и в ширину. Рассмотрим сначала первую из них (рис. 1.1).

В терминах логического программирования вычисление цели j приводит к полному обходу в глубину конкретного дерева поиска цели j, в котором выбирается самая левая цель. По существу здесь декларирован некоторый порядок извлечения целей. Действительно, говоря о поиске в глубину, мы имеем в виду тот порядок, в котором рассматриваются альтернативы в пространстве состояний. В соответствии с этим порядком запоминается одна альтернативная вершина и связанные с ней потомки. Весь проход в глубину образует путь, который, возможно, не достигнет цели, поэтому сработает механизм возврата для поиска альтернативы, вновь ведущей вглубь.

/*********************************************

** Решается задача поиска на графе в глубину **

**********************************************

* База фактов: *

* Cостояние дуг исходного графа – after; *

* целевые вершины – but. *

**********************************************/

/******** Исходный граф ***************/

after(a,b).

after(a,c).

after(b,d).

after(b,e).

after(c,f).

after(c,g).

after(d,h).

after(e,i).

after(e,j).

after(f,k).

but(f).

but(j).

solve(N,S):-

long([],N,S).

long(P,N,[N|P]):-

but(N).

long(P,N,S):-

after(N,N1),

not member(N1,P),

long([N|P],N1,S).

member(X,[X|Q]).

member(X,[H|Q]):-member(X,Q).

/***************************

* Выполнение запроса *

****************************/

?-solve(a,X).

X=[j,e,b,a]->;

X=[f,c,a]->;

no

2. Стратегия поиска в ширину.

В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую очередь к вершинам, ближайшим к стартовой вершине. В результате процесс поиска имеет тенденцию развиваться более в ширину, чем в глубину, что иллюстрирует рис. 1.2.

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

1. если голова первого пути – это целевая вершина, то взять путь в качестве решения, иначе

1. удалить первый путь из множества кандидатов и породить множество всех возможных продолжений этого пути на один шаг; множество продолжений добавить в конец множества кандидатов, а затем выполнить поиск в ширину с полученным новым множеством.

В случае примера рис. 1.2 этот процесс будет развиваться следующим образом:

1. Начинаем с начального множества кандидатов:

[ [a] ]

1. Порождаем продолжение пути [a]:

[ [b, a], [c, a] ]

1. Удаляем первый путь из множества кандидатов и порождаем его продолжения:

[ [d,b,a], [e,b,a] ]

Добавляем список продолжений в конец списка кандидатов:

[ [c,a], [d,b,a], [e,c,a] ]

1. Удалим [c,a], а затем добавляем все его продолжения в конец множества кандидатов:

[ [d,b,a], [e,b,a], [f,c,a], [g,c,a] ]

После того, как пути [d,b,a] и [e,b,a] будут продолжены, измененный список кандидатов примет вид

[ [f,c,a], [g,c,a], [h,d,b,a], [i,e,b,a], [j,e,b,a] ]

В этот момент обнаруживается путь [f,c,a], содержащий целевую вершину f. Этот путь выдается в качестве решения.

/*********************************************

** Решается задача поиска на графе в ширину **

*********************************************/

Характеристики

Список файлов лабораторной работы