Download subárbol

Uso de estructuras y
control de backtracking.
Tema 3. Programación Lógica
Temas
Introducción
Uso de estructuras
Familias
Árboles binarios
Diccionarios
Binarios
Control del backtracking
Bibliografía:
Bratko, Programming in Prolog for Artificial
Intellligence, pp. 84-103, 120 - 129 .
Objetivos
Que los estudiantes se familiaricen y
trabajen con estructuras de datos
Simples
como caso familia, persona...
Árboles y Diccionarios Binarios
Que
conozcan
cómo
controlar
el
backtracking y su importancia para la
rapidez y eficiencia de programas.
Objetos de Datos
simples
estructuras
constantes variables
átomos números
términos
Estructuras
Son
objetos
que
tienen
varios
componentes, las que, a su vez, pueden
ser estructuras.
Tratadas como un solo objeto a través de
la selección de un functor
Ejemplo:
fecha
oracion
fecha(dia, mes, año)
sujeto
fraseverbal
20
oct 2008
oracion(sujeto,fraseverbal(verbo,nombre))
fecha(20, oct, 2008)
verbo
nombre
functor
argumentos
Uso de Estructuras
Ejemplo 1
Buscar el sinónimo de una palabra dentro
de un conjunto de palabras representado
por una lista. Sea el caso de buscar el
sinónimo de aroma:
palabras([mueca(gesto), presagio(augurio),
rapido(veloz), aroma(perfume)]).
Solución Ejemplo 1
Buscar el sinónimo de aroma
palabras([mueca(gesto), presagio(augurio),
rapido(veloz), aroma(perfume)]).
Solución Prolog:
sinonimo(X): palabras(L),
- miembro(X,L).
miembro(X, [X | L]
).
miembro(X, [Y | miembro(X,
?- sinonimo(aroma(X)).
Se recorre la lista hasta que se
L]):- L).
X = perfume ;
encuentra X o el final de la lista
Relaciones de Progenitor
Juan
Ana
Maria
Pedro
José
Lupe
prog(juan,pedro).
prog(juan,ana).
prog(maria,pedro).
prog(pedro,lupe).
prog(pedro,jose).
hombre(juan).
hombre(pedro).
hombre(jose).
mujer(maria).
mujer(ana).
mujer(lupe).
Uso de estructuras
padre
familia (
madre
,
,
persona
,
nombre
Lista de personas
,
apellidos
,
día
).
persona
persona (
fecha (
hijos
,
mes
).
fecha nacimiento
).
año
Con estructura familia
Juan
Ana
Maria
Pedro
José
Lupe
familia(persona(juan, perez, fecha(26, julio, 1953)),
persona(maria, diaz, fecha(1, enero, 1959)),
[persona(pedro, perez, fecha(1, mayo, 1980))]).
Ejemplo 2
familia(persona(juan, perez, fecha(26, julio, 1953)),
persona(ana, diaz, fecha(1, enero, 1959)),
[persona(pedro, perez, fecha(2, mayo, 1980)),
persona(eva, perez, fecha(3, abril, 1985))]).
padre(X):- familia(X, _, _).
madre(X):- familia(_, X, _).
hijo(X):- familia(_, _, Hijo),
miembro(X, Hijo).
existe(X):- padre(X);madre(X);hijo(X).
miembro(X, [X | L] ).
miembro(X, [Y | L]):- miembro(X, L).
% X es padre
% X es madre
% X es un hijo
% Hay persona
% Miembro de una
lista
?- existe(persona(N, A, _)).
%N y A de las personas
?- madre(persona(N, diaz,_)). %Madre de apellido diaz
Árboles Binarios
Representación de Árbol Binario
Árbol binario es un árbol vacío o consta de:
una
raíz
un subárbol izquierdo (binario)
un subárbol derecho (binario)
Gráficamente el conjunto {m, p, r, a}
Raíz
Subárbol izquierdo
m
Subárbol derecho
p
r
a
Representación Prolog de Árbol Binario
Convenciones:
Símbolo
especial para representar un árbol
vacío (nil).
functor (t) para construir un árbol no vacío a
partir de sus tres componentes: raíz, subárbol
Raíz
izquierdo y subárbol derecho.
En PROLOG la estructura:
t
(Izq, X, Der)
Izq
m
p
Der
r
X
Izq
Ejemplo:
Der
a
t(t(nil, p, nil),m,t( t(nil, a, nil),r,nil))
Pertenencia a un Árbol Binario
Un hecho: arbol(T).
Y la relación: esta(X, T) que es verdadera
si X es un nodo de T. Se cumple si:
La
raíz de T es X
X está en el subárbol izquierdo de T
X está en el subárbol derecho de T
En PROLOG:
esta(X, t(_, X, _)).
esta(X, t(Izq, _, _)):- esta(X, Izq).
esta(X, t(_, _, Der)):- esta(X, Der).
Pertenencia a un Árbol Binario
(ejecución)
En PROLOG:
arbol(t(t(nil,p,nil),m,t(t(nil,a,nil),r,nil))). % hecho
esta(X, t(_, X, _)).
esta(X, t(Izq, _, _)):- esta(X, Izq).
esta(X, t(_, _, Der)):- esta(X, Der).
% regla 1
% regla 2
% regla 3
?-arbol(T), esta(X, T).
%pegunta
X
X
X
X
=
=
=
=
m;
p;
r;
a
Diccionario Binario
Todos los nodos del subárbol izquierdo
(Izq), son menores que X
Todos los nodos del subárbol derecho
(Der), son mayores que X
Ambos subárboles también son
ordenados.
8
Ejemplo
5
3
15
7
10
20
12
Búsqueda en Diccionario Binario
En Prolog:
enD(X,t(_,X,_)):enD(X,t(Izq,R,_)):5
!.
8
mayor(R,X),!,
15
enD(X,Izq).
3
7 10
20
enD(X,t(_,R,Der)):- enD(X,Der).
12
mayor( X, Y) :- X > Y.
% es la
Raiz
% Raiz >
X
% X > Raiz
Para hallar un elemento X en un diccionario D:
Si
X es la raíz de D entonces X se encuentra
Si X es menor que la raíz de D entonces buscar
X en el subárbol izquierdo de D
En otro caso, buscar X en el subárbol derecho
de D.
Control de Backtraking.
Corte (!)
Backtracking
Al procesar una pregunta con más de una
meta puede suceder que el Prolog logre
satisfacer algunas de ellas y no consigue
satisfacer la meta que sigue en orden.
En ese caso, el interprete regresa a la
meta anterior y trata de buscar otra
solución posible para esa meta que le
permita avanzar en la siguiente
Este
retroceso
pudiera
tener
profundidad que sea requerida.
la
Backtracking
padre(jose, ana).
padre(jose, pepe).
padre(juan, eva).
padre(juan, pedro).
padre(mario, juan).
Observaciones:
hijo(X, Y) :- padre(Y, X).
Las
respuestas se obtienen buscando en la
La pregunta
BD los hechos en el orden en que fueron
?- hijo( _, Y).
dados.
Respuestas:
Y = jose ;
Y = joserealiza
;
Prolog
el backtracking a ciegas
Y = juan ; otras soluciones.
buscando
Y = juan ;
Y = mario
Backtracking
hombre(juan).
hombre(jose).
hombre(pedro).
mujer(ada).
mujer(eva).
posiblepareja( X, Y) :- hombre( X), mujer( Y).
Funcionamiento Prolog
Pregunta
1.Busca
posiblepareja(_,_,_).
?- posiblepareja(X,
Y).
2.Satisface el objetivo I-hombre(X).
Respuestas:
3.Pasa
a satisfacer objetivo II-mujer(Y) .
X = juan
= ada
;
4.Trata
de ,Y
volver
a satisfacer
mujer(Y).
X = juan
= eva
;
5.Trata
de ,Y
volver
a satisfacer
mujer(Y) y falla.
6.Trata
de ,volver
a satisfacer
el objetivo hombre(X),
X = jose
Y = ada
;
… ;
Xretrocediendo.
= jose , Y = eva
Situaciones al Satisfacer Objetos
1.
Ajuste o matching con un hecho. De ser
necesario se instancian variables y el sistema
marca la posición en la BD.
2.
Ajuste con la cabeza de una regla.
a)
b)
Intentan satisfacer los objetivos introducidos
por la regla, de izquierda a derecha. Si el
primero de la izquierda se satisface, se
intenta satisfacer el que le sigue a la derecha
y así sucesivamente.
Si alguno de ellos no se satisface se dice que
el objetivo falla y se intenta resatisfacer
explorando otra opción de ajuste para el
objetivo anterior (a la izquierda).
Corte (cut). Control del backtracking
Ejemplo:
R1:
R2:
R3:
Y
4
2
Si X < 3 entonces Y = 0
Si 3 ≤ X y X < 6 entonces Y = 2
Si 6 ≤ X entonces Y = 4
En Prolog:
3
6
f( X, 0) :- X < 3.
% Regla 1
X f( X, 2) :- 3 =< X, X < 6. % Regla 2
f( X, 4) :- 6 =< X.
% Regla 3
¿Cómo funcionaria Prolog para la pregunta?
?- f( 1, Y), 2 < Y.
Corte (cut). Control del backtracking
f( 1, Y)
2<Y
regla 1
Y=0
1<3
2<0
corte
2<0
no
regla 2
Y=2
1<3
2<0
no
regla 1
Y=4
Backtracking
innecesarios
1<3
2<0
no
Se puede lograr con corte:
f( X, 0) :- X < 3.
3, !.
f( X, 2) :- 3 =< X, X < 6.
6, !.
f( X, 4) :. 6 =< X.
Conclusiones
Uso de estructuras.
Instanciar estructura completa.
Elementos
Árboles Binarios
Representación y Pertenencia
Diccionario Binario y Búsqueda
Control del backtracking
!
Valor en rapidez y eficiencia
Clase Práctica 1
1.Agregar al menos 2 familias a la BD y
formular las siguientes preguntas:
a.¿Qué personas nacieron antes de 70?
b.Apellidos de los padres de familia que
no tienen hijos.
3.Teniendo una BD con relaciones entre un
país y su población (poblacion(pais, Hab)),
y entre un país y su área (area(Pais,
Sup)). Elabore un programa Prolog que
calcule la densidad de población de un país
(densidad(Pais, Hab)).
Clase Práctica 1
3. Elaborar
un programa Prolog que permita:
Determinar si una persona estudiaba el
preuniversitario en un año particular.
Considerar un predicado de la forma
estudio(X, Y, Z), que es verdadero si la
persona X estudió el preuniversitario entre
los años Y y Z.
Construir una base que contenga hechos
tales como: estudio(juan, 2001, 2004).
Verificar su funcionamiento en un sistema
Prolog.
Clase Práctica 2
4.
Modificar el programa de búsqueda en
diccionario binario para el caso en que los
nodos del árbol sean letras. Verificar con
un árbol de ejemplo. (Sugerencia: tener
en cuenta el predicado predefinido
name(Atomic, List)).
5.
Elaborar un programa que permita
agregar un elemento X a un diccionario
binario T para obtener otro T1. (agregar(
T, X, T1)).
Clase Práctica 2
6.
Utilizando
el
corte,
elaborar
un
procedimiento Prolog para:
a) Calcular el mínimo de 2 números, con
la relación minimo( X, Y, Min).
b) Determinar sólo la primera ocurrencia
de un elemento en una lista.
7.
Analizar la segunda y última versión del
programa para la pregunta ?- f( 8, Y). y
comprobar que el sistema Prolog
generará 2 ramas en el árbol de
ejecución.