Основы искусственного интеллекта




Скачать 473.71 Kb.
НазваниеОсновы искусственного интеллекта
страница3/4
Дата26.09.2012
Размер473.71 Kb.
ТипУчебно-методическое пособие
1   2   3   4

Комментарий: write – стандартный предикат вывода, readln – стандартный предикат ввода строкового значения

5.7. Поиск с возвратом

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

Рассмотрим механизм поиска на примере. Пусть имеются факты:

знает (лена, таня).

знает (лена, иван).

студент (иван).

Требуется определить, есть ли у Лены знакомые студенты.

Программа:

PREDICATES

знает (symbol, symbol)

студент (symbol)

знаком_студент(symbol, symbol)

CLAUSES

знает (лена, таня). % (1)

знает (лена, иван). % (2)

студент (иван). % (3)

знаком_студент(X,Y):- знает (X,Y), студент (Y). % (4)

GOAL

знаком_студент(лена, Name).

Поиск решения:

1. Пытаясь выполнить целевое утверждение знаком_студент(лена, Name), ПРОЛОГ проверяет каждое предложение из раздела CLAUSES. В результате сопоставления с предложением (4) - X=лена. Переменная Y унифицируется с переменной Name.

2. Переход к первой подцели знает (лена,Y) и поиск соответствующего предложения. В результате сопоставления с предложением (1) – Y=таня. Возле факта знает (лена, таня) устанавливается маркер.

3. Переход ко второй подцели студент (таня) и поиск соответствующего предложения. Факт не найден – возврат в точку отката.

4. Дальнейший поиск фактов, соответствующих первой подцели знает(лена,Y). В результате сопоставления с предложением (2) – Y=иван.

5. Переход ко второй подцели студент (иван) и поиск соответствующего предложения приводит к успешному завершению поиска.

Результат:

Name=иван

1 Solition

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


рис.2. Целевое дерево поиска с возвратом

Благодаря механизму поиска с возвратом ПРОЛОГ в состоянии находить все возможные решения, имеющиеся для данной задачи.

Основные правила поиска с возвратом:

  1. Цели должны быть доказаны по порядку, слева направо.

  2. Для доказательства некоторой цели предложения просматриваются в том порядке, в каком они появляются в тексте программы.

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

  4. Цель считается доказанной, если с помощью соответствующих фактов доказаны все цели, находящиеся в листьевых вершинах дерева целей.

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

Для управление поиском с возвратом используются два стандартных предиката: fail и отсечения.

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

Пример 1. Вывести список студентов 4-го курса.

DOMAINS

name=string

kurs=integer

PREDICATES

Student(name, kurs)

spisok

CLAUSES

Student("Ира",2).

Student("Юра",4).

Student("Коля",1).

Student("Леша",4).

Student("Оля",4).

spisok:-Write("Список студентов 4 курса"), nl, Student(X,4),

Write(X), nl, fail.

GOAL

spisok.

Комментарий: nl (new line) – предикат перевода курсора на новую строку

    В данном примере после первого найденного решения (Х= «Юра») и его вывода предикат fail заставляет вернуться в точку отката и продолжить поиск, просматривая другие факты. В результате будут найдены все решения, удовлетворяющие запросу.

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

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

    Юра

    Леша

    Оля

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

Если задано предложение вида:

R:-A, B, ! , C.

то после достижения подцелей А и В процесс поиска других решений этих подцелей прекращается и вычислительный процесс перейдет к следующей подцели С.

Например, чтобы в примере 1 вывести все возможные пары одного из студентов 4-го курса со всеми остальными студентами, следует изменить правило spisok

spisok:- Student(X,4), !, Student(Y,_), X<>Y,
Write(X," - ",Y), nl, fail.

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

Юра - Ира

Юра - Коля

Юра - Леша

Юра – Оля

5.9. Арифметические вычисления

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

X + Y

Сумма X и Y

X - Y

Разность X и Y

X * Y

Произведение X и Y

X / Y

Деление X на Y

X mod Y

Остаток от деления X на Y

abs(X)

Абсолютная величина числа X

sqrt(X)

Квадратный корень из X

random(X)

Случайное число в диапазоне от 0 до 1

random(Int,X)

Случайное целое число в диапазоне от 0 до Int

sin(X)

Синус X

cos(X)

Косинус X

tan(X)

Тангенс X

log(X)

Натуральный логарифм (ln) числа X


Пролог располагает двумя числовыми типами доменов: целыми и действительными числами. Пролог позволяет также сравнивать арифметические выраже­ния, используя отношения:

=, <, <=, >, >=, <>

Для реализации математических действий в Прологе используются предикаты. Следующие примеры демонстрируют их использование.


Пример 1.

Найти среднее арифметическое двух чисел.

PREDICATES

Sr (real, real, real)

CLAUSES

Sr (A, B, S):- S = (A+B)/2.

GOAL

Sr (8, 12, S), write (S).


Результат:

10

Пример 2.

Определить является ли натуральное число четным или нечетным

PREDICATES

Chet (integer)

CLAUSES

Chet (A): - A mod 2 =0, write (A, ‘- четное’); Write (A, ‘- не четное’).

GOAL

Chet (18).

Результат:

18 – четное

5.10. Рекурсия

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

Рассмотрим рекурсивное определение правила на примере правила predok

1. X является предком Z, если X - родитель Z

predok(X, Z):-roditel(X, Z)

2. X – предок для Z, если найдется такой Y, для которого X является родителем и Y является предком Z .

Predok (X,Z) :- roditel (X,Y), predok (Y,Z).

Первая часть этого правила нерекурсивная, она определяет условие завершения рекурсии. Поиск прекратится, как только будет найден ближайший предок - родитель.

Программа:

DOMAINS

name = string

PREDICATES

roditel (name, name)

predok (name, name)

CLAUSES

roditel (коля, оля).

roditel (оля, маша).

predok (X, Z):- roditel (X, Z).

predok (X, Z):- roditel (X,Y), predok (Y, Z).

GOAL

predok (коля, маша).

Результат:

yes

Пример. Рекурсивное вычисление факториала

Задача нахождения значения факториала n! сводится к нахождению значения факториала (n-1)! и умножения найденного значения на n.

Правило для вычисления факториала:

1. 0! = 1

fact (0, 1):- !. % нерекурсивная часть правила

2. N! = (N-1)!*N.

fact (N, FN):- M=N–1, % рекурсивная часть правила

fact (M, FM), FN=FM*N.

Программа:

PREDICATES

fact (integer, integer)

CLAUSES

fact (0, 1):- !.

fact (N, FactN):- M=N–1, fact (M, FactM), FactN=FactM*N.

GOAL

fact (3, FN), write (“3!=”, FN).


Результат работы программы:

3!=6

Для наглядного представления нахождения решения удобно использовать дерево целей:



рис.3 Целевое дерево вычисления факториала

5.11. Списки

Список – это объект, который содержит конечное число других объектов. Список в ПРОЛОГе можно приблизительно сравнить с массивами в других языках, но для списков нет необходимости заранее объявлять размерность.

Список в ПРОЛОГе заключается в квадратные скобки и элементы списка разделяются запятыми. Список, который не содержит ни одного элемента, называется пустым списком.

Примеры списков:

список, элементами которого являются целые числа: [1, 2, 3]

список, элементами которого являются строки: [“One”, “Two”, “Three”]

пустой список: []

Элементами списка могут быть списки: [[-1,3,5],[6,4,2,8]]

Чтобы использовать в ПРОЛОГ-программе списки, необходимо в разделе DOMAINS описать тип домена в формате.

<имя домена> = <тип элементов>*

Например,

DOMAINS

list = *

Список является рекурсивным объектом. Он состоит из головы (первого элемента списка) и хвоста (все последующие элемента). Хвост также является списком.

Например, [A, B, C] - список , у которого А – голова, [B,C] - хвост

В ПРОЛОГе имеется операция “|”, которая позволяет делить список на голову и хвост.

[A, B, C] = [A | [B, C] ] = [A | [B | [C] ] ] = [A | [B | [C | [ ] ] ] ]

Пустой список нельзя разделить на голову и хвост. Такая структура позволяет использовать рекурсию для обработки списка.

Пример программы, осуществляющей вывод элементов списка.

DOMAINS

list = integer *

PREDICATES

writelist(list)

CLAUSES

writelist ([]).

writelist ([A | Z]) :- write (A), nl, writelist (Z).

GOAL

writelist([10, 20, 30, 40]).

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

10

20

30

40

В данной программе A – голова списка, Z – его хвост

5.12. Стандартные задачи обработки списка

К наиболее типичным задачам обработки списков относятся:

1) генерирование списка;

2) объединение списков;

3) поиск заданного элемента в списке;

4) удаление указанного элемента из списка;

5) вставка указанного элемента в список.

1. Генерирование списка из (N2-N1) последовательных целых чисел, начиная с N1.

Для формирования списка создадим отношение genlist(N1, N2, L), где

N1 – начальный элемент списка

N2 – его верхняя граница

L – список

Возможны случаи:

1) если N1 = N2, тогда N1 – не добавляется в список и L – пустой список.

genlist (N2, N2, [ ]) – первая часть правила (условие останова).

2) если N1 < N2, то N1 помещаем в голову списка, затем увеличиваем N1 на 1 и для нового значения снова вызывается genlist. Получаем вторую часть правила:

genlist (N1, N2, [N1 | L]): - N1 < N2, N = N1+1, genlist (N, N2, L).

Таким образом, правило формирования списка имеет вид:

genlist (N2, N2, [ ]). % нерекурсивная часть правила

genlist (N1, N2, [N1 | L]): - % рекурсивная часть правила

N1 < N2, N = N1+1, GenList (N, N2, L).

Например, для формирования списка [2, 3, 4, 5] следует указать запрос:

GOAL

GenList (2, 6, L), Write (L), nl.

2. Объединение списков.

Создадим отношение append(L1, L2, L3), где L1, L2 – исходные списки, L3 – список, полученный в результате присоединения L2 к L1.

Возможны случаи:

1) если L1 пустой список, то результирующий список L3 равен списку L2. Получаем первую (нерекурсивную) часть правила:

append ([ ], L, L).

2) если L1 не пустой список, то делим его на голову и хвост ( [X | L1]). Вторая (рекурсивная) часть правила:

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

Таким образом, правило объединения списков имеет вид:

append ([ ], L, L).

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

Например, для объединения списков [1, 2, 3] и [4, 5] следует написать запрос:

GOAL

append ([1, 2, 3], [4, 5], L) write [L].

Результат:

[1, 2, 3, 4, 5]

При выполнении программы из L1 выделяется и заносится в стек по одному элементу (голова списка) до тех пор, пока L1 не станет пустым. После этого выполняется первая часть правила и L3 получает значение L2, то есть L3 = [4, 5] начинается выгрузка элементов из стека и добавление их в голову L3.

Правило append обладает большое гибкостью и позволяет решать множество задач по обработке списка. Его можно использовать для решения обратной задачи: разбиение исходного списка на две части.

Например, чтобы определить все возможные способы разбиения списка [1,2,3], следует составить запрос:

GOAL

append (L1, L2, [1,2,3]), write (“L1=”, L1, “L2=”, L2), fail, nl.

Результат:

L1 = [ ] L2 = [1, 2, 3]

L1 = [1] L2 = [2, 3]

L1 = [1, 2] L2 = [3]

L1 = [1, 2, 3] L2 = [ ]

1   2   3   4

Похожие:

Основы искусственного интеллекта iconУчебно-методический комплекс по дисциплине “основы искусственного интеллекта”
...
Основы искусственного интеллекта icon«Основы искусственного интеллекта»
Рабочая учебная программа по дисциплине «Основы искусственного интеллекта» для ооп «050100 Физика и информатика по циклу б в. 13...
Основы искусственного интеллекта iconУчебно-методический комплекс по дисциплине “основы искусственного интеллекта” для специальности
...
Основы искусственного интеллекта iconУчебно-методический комплекс по дисциплине “основы искусственного интеллекта” для специальности
...
Основы искусственного интеллекта iconВ. К. Финн к структурной когнитологии: феноменология сознания с точки зрения искусственного интеллекта
Ки и искусственного интеллекта – полигона экспериментальной проверки научных средств имитации рациональности и продуктивного мышления....
Основы искусственного интеллекта iconКонспект лекций по дисциплине «Системы искусственного интеллекта»
Место среди других наук, первые шаги и современные направления искусственного интеллекта
Основы искусственного интеллекта icon«шаг за шагом» создание искусственного интеллекта гашева Светлана
Интеллект рассматривают как прикладную область исследований, связанных с имитацией отдельных функций интеллекта человека [6]. Распознавание...
Основы искусственного интеллекта iconФилософия искусственного интеллекта в свете новой методологии познания
М.: Философия искусственного интеллекта. Материалы Всероссийской междисциплинарной конференции, иф ран, 2005 г., с. 143-146
Основы искусственного интеллекта iconО работе научного советаран по методологии искусственного интеллекта
Первой Всероссийской междисциплинарной конференции, посвященной философским, методологическим и теоретическим проблемам искусственного...
Основы искусственного интеллекта iconСтатья рассматривает вопросы в области информационных технологий в системах: человек-машина, человек-информация. В статье раскрыты моменты: функции обработки информации,
Целью данной работы является моделирование алгоритма искусственного интеллекта на доминантах функций: интроверсии, экстраверсии;...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница