РуЛиб - онлайн библиотека > Григорьев Л. > Учебники и пособия ВУЗов > Системы искусственного интеллекта: Учебное пособие > страница 17
Читаем онлайн «Системы искусственного интеллекта: Учебное пособие» 17 cтраница
корень и правое поддерево. Левое и правое поддеревья сами являются бинарными деревьями.
Например, дерево, представленное на рис.10, можно представить следующим термом: бд(бд((бд(nil, d, nil), b, бд(nil, e, nil))), a, бд(nil, c, nil)). Атом nil используется для представления пустого дерева.
Рис. 10 Бинарное дерево.
Для эффективного использования бинарное дерево должно быть упорядочено таким образом, чтобы любой элемент в левом поддереве был меньше, чем значение корня, а любой элемент в правом поддереве – больше (рис. 11).
Рис. 11 Упорядоченное бинарное дерево.
Пример 7.4
1. Добавление элемента в упорядоченное бинарное дерево.
При добавлении если элемент меньше корневого элемента, то он добавляется к левому поддереву, если же больше, то – к правому. Для проверки порядка следования использованы операторы @< и @>.
вкл_бд(nil, X, бд (nil, X, nil)).
вкл_бд(бд(Лд,K,Пд), X, бд(Лд1,K,Пд)):- X @< K,
вкл_бд (Лд,X,Лд1).
вкл_бд(бд(Лд,K,Пд), X, бд(Лд,K,Пд1)):- X @> K,
вкл_бд (Пд,X,Пд1).
2. Построение упорядоченного дерева из списка (в общем случае, неупорядоченного).
список_в_дерево([], nil).
список_в_дерево([H | L], Бд):- список_в_дерево(L, Бд1),
вкл_бд(H, Бд1, Бд).
3. Построение отсортированного списка из упорядоченного дерева.
Отсортированный список для упорядоченного бинарного дерева бд(Лд,K,Пд), где Лд имеет отсортированный список СЛ, а Пд – отсортированный список СП, получается слиянием списков СЛ и [К | СП].
дерево_в_список(nil,[]).
дерево_в_список (бд(Лд,K,Пд),С):- дерево_в_список(Лд,СЛ),
дерево_в_список(Пд,СП),
слияние(СЛ,[К|СП],С).
7.6 Управление ходом выполнения программы
Встроенный механизм поиска с возвратом может привести к поиску ненужных решений, в результате чего теряется эффективность, например, когда желательно найти только единственное решение. В других случаях необходимо продолжать поиск дополнительных решений, даже если целевое утверждение уже согласовано. В подобных ситуациях необходимо управлять процессом поиска с возвратом.
Пpолог обеспечивает два инструментальных средства, которые дают возможность управлять механизмом поиска с возвратом: предикаты fail - используется для поддержания поиска с возвратом, и cut, или отсечение (обозначается «!»), - используется для предотвращения поиска с возвратом.
В определенных ситуациях бывает необходимо выполнить поиск с возвратом, чтобы найти другие решения. Встроенный предикат fail вызывает состояние неудачи при доказательстве целевого утверждения и, следовательно, инициирует поиск с возвратом. Действие предиката fail равносильно эффекту от сравнения 2 = 3 или другой невозможной подцели.
Обратное действие - прерывание поиска с возвратом - дает вызов предиката cut, позволяющего выполнить отсечение всех альтернатив. Доказательство цели-отсечения всегда заканчивается успешно, и после этого не могут быть передоказаны цели, стоящие в утверждении до отсечения, включая головную цель.
Отсечение применяется для устранения бесконечных циклов, при программировании взаимоисключающих утверждений и при необходимости неудачного завершения доказательства цели.
Рассмотрим несколько вариантов правил определения абсолютного значения Y для некоторого числа X.
1 вариант. abs(X,Y) :- X>=0, Y is X;
Y is –X.
Для целевого утверждения
?- abs(5,X).
попытка сопоставления с первой альтернативой будет успешна: X = 5. Если продолжить поиск решений, то система выдаст неверный ответ X = -5, полученный при сопоставлении целевого утверждения со второй альтернативой.
2 вариант. Ограничим область применения второй альтернативы:
abs(X,Y) :- X>=0, Y is X;
X=0, !, Y is X;
Y is –X.
Предикат «!» запрещает проверку последующих альтернатив данного определения. После его удовлетворения невозможен выбор других альтернатив.
Выполнение программы на Прологе можно представить как построение И‑ИЛИ дерева поиска решения и обход этого дерева. В И-ИЛИ дереве различают дав типа вершин И и ИЛИ. Ветви, сходящиеся к вершине И, считаются связанными конъюнктивно (логическое И), а ветви, сходящиеся к вершине ИЛИ – дизъюнктивно (логическое ИЛИ). Обход И-ИЛИ дерева осуществляется с крайней левой ветви (первого условия). Обнаружив определение с тем же именем, что и условие, Пролог достраивает дерево, используя те же правила, что и при интерпретации целевого утверждения: альтернативные варианты представляются ветвями, сходящимися к вершинам ИЛИ, а конъюнкция условий – ветвями, сходящимися к вершинам И. Поскольку факты условий не содержат, они интерпретируются в виде листьев дерева, тип их вершин не существенен.
На рис.12 представлено И-ИЛИ дерево поиска решений для 1 варианта определения.
рис. 12
На рис.13 показана последовательность согласования целевых утверждений для различных вариантов программы. Сравнивая процессы выполнения программы, видно, что вторая альтернатива при X 0 исключается из рассмотрения, при X
Например, дерево, представленное на рис.10, можно представить следующим термом: бд(бд((бд(nil, d, nil), b, бд(nil, e, nil))), a, бд(nil, c, nil)). Атом nil используется для представления пустого дерева.
Рис. 10 Бинарное дерево.
Для эффективного использования бинарное дерево должно быть упорядочено таким образом, чтобы любой элемент в левом поддереве был меньше, чем значение корня, а любой элемент в правом поддереве – больше (рис. 11).
Рис. 11 Упорядоченное бинарное дерево.
Пример 7.4
1. Добавление элемента в упорядоченное бинарное дерево.
При добавлении если элемент меньше корневого элемента, то он добавляется к левому поддереву, если же больше, то – к правому. Для проверки порядка следования использованы операторы @< и @>.
вкл_бд(nil, X, бд (nil, X, nil)).
вкл_бд(бд(Лд,K,Пд), X, бд(Лд1,K,Пд)):- X @< K,
вкл_бд (Лд,X,Лд1).
вкл_бд(бд(Лд,K,Пд), X, бд(Лд,K,Пд1)):- X @> K,
вкл_бд (Пд,X,Пд1).
2. Построение упорядоченного дерева из списка (в общем случае, неупорядоченного).
список_в_дерево([], nil).
список_в_дерево([H | L], Бд):- список_в_дерево(L, Бд1),
вкл_бд(H, Бд1, Бд).
3. Построение отсортированного списка из упорядоченного дерева.
Отсортированный список для упорядоченного бинарного дерева бд(Лд,K,Пд), где Лд имеет отсортированный список СЛ, а Пд – отсортированный список СП, получается слиянием списков СЛ и [К | СП].
дерево_в_список(nil,[]).
дерево_в_список (бд(Лд,K,Пд),С):- дерево_в_список(Лд,СЛ),
дерево_в_список(Пд,СП),
слияние(СЛ,[К|СП],С).
7.6 Управление ходом выполнения программы
Встроенный механизм поиска с возвратом может привести к поиску ненужных решений, в результате чего теряется эффективность, например, когда желательно найти только единственное решение. В других случаях необходимо продолжать поиск дополнительных решений, даже если целевое утверждение уже согласовано. В подобных ситуациях необходимо управлять процессом поиска с возвратом.
Пpолог обеспечивает два инструментальных средства, которые дают возможность управлять механизмом поиска с возвратом: предикаты fail - используется для поддержания поиска с возвратом, и cut, или отсечение (обозначается «!»), - используется для предотвращения поиска с возвратом.
В определенных ситуациях бывает необходимо выполнить поиск с возвратом, чтобы найти другие решения. Встроенный предикат fail вызывает состояние неудачи при доказательстве целевого утверждения и, следовательно, инициирует поиск с возвратом. Действие предиката fail равносильно эффекту от сравнения 2 = 3 или другой невозможной подцели.
Обратное действие - прерывание поиска с возвратом - дает вызов предиката cut, позволяющего выполнить отсечение всех альтернатив. Доказательство цели-отсечения всегда заканчивается успешно, и после этого не могут быть передоказаны цели, стоящие в утверждении до отсечения, включая головную цель.
Отсечение применяется для устранения бесконечных циклов, при программировании взаимоисключающих утверждений и при необходимости неудачного завершения доказательства цели.
Рассмотрим несколько вариантов правил определения абсолютного значения Y для некоторого числа X.
1 вариант. abs(X,Y) :- X>=0, Y is X;
Y is –X.
Для целевого утверждения
?- abs(5,X).
попытка сопоставления с первой альтернативой будет успешна: X = 5. Если продолжить поиск решений, то система выдаст неверный ответ X = -5, полученный при сопоставлении целевого утверждения со второй альтернативой.
2 вариант. Ограничим область применения второй альтернативы:
abs(X,Y) :- X>=0, Y is X;
X=0, !, Y is X;
Y is –X.
Предикат «!» запрещает проверку последующих альтернатив данного определения. После его удовлетворения невозможен выбор других альтернатив.
Выполнение программы на Прологе можно представить как построение И‑ИЛИ дерева поиска решения и обход этого дерева. В И-ИЛИ дереве различают дав типа вершин И и ИЛИ. Ветви, сходящиеся к вершине И, считаются связанными конъюнктивно (логическое И), а ветви, сходящиеся к вершине ИЛИ – дизъюнктивно (логическое ИЛИ). Обход И-ИЛИ дерева осуществляется с крайней левой ветви (первого условия). Обнаружив определение с тем же именем, что и условие, Пролог достраивает дерево, используя те же правила, что и при интерпретации целевого утверждения: альтернативные варианты представляются ветвями, сходящимися к вершинам ИЛИ, а конъюнкция условий – ветвями, сходящимися к вершинам И. Поскольку факты условий не содержат, они интерпретируются в виде листьев дерева, тип их вершин не существенен.
На рис.12 представлено И-ИЛИ дерево поиска решений для 1 варианта определения.
рис. 12
На рис.13 показана последовательность согласования целевых утверждений для различных вариантов программы. Сравнивая процессы выполнения программы, видно, что вторая альтернатива при X 0 исключается из рассмотрения, при X