Проверка принадлежности дереву (Лабораторная работа № 5)

Министерство образования и науки РФ

Новосибирский государственный технический университет

Кафедра ПСиБД

Лабораторная работа №5

по дисциплине «Введение в искусственный интеллект

и логическое программирование»

Факультет:            ПМИ

Группа:                   ПМ-01

Выполнили:         Гончаренко А.В.

Гладкова А.В.

Федин И.В.

Проверили:          Авдеенко Т.В.

                                    Целебровская М.Ю.

Новосибирск

 2012

1. Текст задания

Проверка принадлежности дереву.

2. Иccледования

domains

  btree = tree(integer, btree, btree); nul

predicates

   inside(integer,btree)

clauses

   inside(X,tree(X,_,_)).

   inside(X,tree(Root,Left,_)):-Root>X,inside(X,Left).

   inside(X,tree(Root, _, Right)):-X>Root,inside(X,Right).

goal

inside(5, tree(10, tree(3,nul,tree(5, nul, nul)), tree(12, nul, tree(15,nul, nul))).

CALL:    inside(5,tree(10,tree(3,nul,tree(5,nul,nul)),tree(12,nul,tree(15,nul,nul))))

         10>5

CALL:    inside(5,tree(3,nul,tree(5,nul,nul)))

REDO:    inside(5,tree(3,nul,tree(5,nul,nul)))

         3>5

FAIL:    inside(5,tree(3,nul,tree(5,nul,nul)))

REDO:    inside(5,tree(3,nul,tree(5,nul,nul)))

         5>3

CALL:    inside(5,tree(5,nul,nul))

RETURN:  *inside(5,tree(5,nul,nul))

RETURN:  inside(5,tree(3,nul,tree(5,nul,nul)))

RETURN:  *inside(5,tree(10,tree(3,nul,tree(5,nul,nul)),tree(12,nul,tree(15,nul,nul))))

3.  Вывод по исследованию

Добавление предиката "!" не повлияло на получаемое решение,  не нарушая логический смысл программы, значит отсечения являются

“зелеными”.

4.  Индивидуальное задание

Определите отношение ex_tree(Tree,Ex) выполненное, если число Ex является значением выражения, представленного в виде двоичного дерева. Допустимыми операциями в арифметическом выражении являются: +,-,*,/.

5.  Текст программы

domains

btree = tree(symbol, btree, btree); nul

predicates

nondeterm ex_tree(btree, integer)

clauses

ex_tree(tree("/", tree(A, nul, nul),tree(B, nul, nul)),C):- str_int(A,A1),

str_int(B, B1), A1/B1=C.

ex_tree(tree("*", tree(A, nul, nul),tree(B, nul, nul)),C):- str_int(A,A1),

str_int(B, B1), A1*B1=C.

ex_tree(tree("-", tree(A, nul, nul),tree(B, nul, nul)),C):- str_int(A,A1),

str_int(B, B1), A1-B1=C.

ex_tree(tree("+", tree(A, nul, nul),tree(B, nul, nul)),C):- str_int(A,A1),

str_int(B, B1), A1+B1=C.

ex_tree(tree("/", tree(A, nul, nul),T2),C):- ex_tree(T2,B), str_int(A,A1), A1/B=C.

ex_tree(tree("*", tree(A, nul, nul),T2),C):- ex_tree(T2,B), str_int(A,A1), A1*B=C.

ex_tree(tree("-", tree(A, nul, nul),T2),C):- ex_tree(T2,B), str_int(A,A1), A1-B=C.

ex_tree(tree("+", tree(A, nul, nul),T2),C):- ex_tree(T2,B), str_int(A,A1), A1+B=C.

ex_tree(tree("/", T1,tree(B, nul, nul)),C):- ex_tree(T1,A), str_int(B,B1), A/B1=C.

ex_tree(tree("*", T1,tree(B, nul, nul)),C):- ex_tree(T1,A), str_int(B,B1), A*B1=C.

ex_tree(tree("-", T1,tree(B, nul, nul)),C):- ex_tree(T1,A), str_int(B,B1), A-B1=C.

ex_tree(tree("+", T1,tree(B, nul, nul)),C):- ex_tree(T1,A), str_int(B,B1), A+B1=C.

ex_tree(tree("/", T1,T2),C):- ex_tree(T1,A), ex_tree(T2,B), A/B=C.

ex_tree(tree("*", T1,T2),C):- ex_tree(T1,A), ex_tree(T2,B), A*B=C.

ex_tree(tree("-", T1,T2),C):- ex_tree(T1,A), ex_tree(T2,B), A-B=C.

ex_tree(tree("+", T1,T2),C):- ex_tree(T1,A), ex_tree(T2,B), A+B=C.

9.  Тесты

Goal	Solution
ex_tree(tree("*",tree("5",nul,nul),tree("+",tree("1",nul,nul),tree("2",nul,nul))),X).	X=15
ex_tree(tree("-",tree("4",nul,nul),tree("/",tree("8",nul,nul),tree("2",nul,nul))),X).	X=0
ex_tree(tree("*", tree("+", tree("7", nul, nul), tree("3", nul, nul)), tree("/",  tree("-", tree("4", nul, nul), tree("12", nul, nul)),tree("8", nul, nul) )),X).	X=-10