temas programacion logica ia

7/29/2019 Temas Programacion Logica IA

1/262

Temas de Programacin lgica e I.A.

Jos A. Alonso Jimnez

Grupo de Lgica Computacional

Dpto. de Ciencias de la Computacin e Inteligencia Artificial

Universidad de Sevilla

Sevilla, 21 de febrero de 2013
http://www.cs.us.es/~jalonsohttp://www.cs.us.es/glchttp://www.cs.us.es/http://www.us.es/http://www.us.es/http://www.cs.us.es/http://www.cs.us.es/glchttp://www.cs.us.es/~jalonso


2/262

Esta obra est bajo una licencia ReconocimientoNoComercialCompartirIgual 2.5 Spainde Creative Commons.

Se permite:

copiar, distribuir y comunicar pblicamente la obra

hacer obras derivadas

Bajo las condiciones siguientes:

Reconocimiento. Debe reconocer los crditos de la obra de la manera espe-cificada por el autor.

No comercial. No puede utilizar esta obra para fines comerciales.

Compartir bajo la misma licencia. Si altera o transforma esta obra, o generauna obra derivada, slo puede distribuir la obra generada bajo una licencia

idntica a sta.

Al reutilizar o distribuir la obra, tiene que dejar bien claro los trminos de la licen-cia de esta obra.

Alguna de estas condiciones puede no aplicarse si se obtiene el permiso del titular

de los derechos de autor.

Esto es un resumen del texto legal (la licencia completa). Para ver una copia de esta

licencia, visiteh t t p : / / c r e a t i v e c o m m o n s . o r g / l i c e n s e s / b y - n c - s a / 2 . 5 / e s /

o envie unacarta a Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.
http://creativecommons.org/licenses/by-nc-sa/2.5/es/http://creativecommons.org/licenses/by-nc-sa/2.5/es/


3/262

ndice general

1. El sistema deductivo de Prolog 5

2. Introduccin a la programacin lgica con Prolog 21

3. Programacin con Prolog 55

4. Resolucin de problemas de espacios de estados 77

5. Procesamiento del lenguaje natural 103

6. Ingeniera del conocimiento y metaintrpretes 133

7. Razonamiento por defecto y razonamiento abductivo 165

8. Programacin lgica con restricciones 177

9. Formalizacin en Prolog de la lgica proposicional 193

10. Programacin lgica y aprendizaje automtico 219

Bibliografa 261

3


4/262

4 ndice general


5/262

Captulo 1

El sistema deductivo de Prolog

5


6/262

PD Tema 1: El sistema deductivo de Prolog

Programacin lgica (200809)Tema 1: El sistema deductivo de Prolog


Grupo de Lgica ComputacionalDepartamento de Ciencias de la Computacin e I.A.


1 / 27


1. IntroduccinObjetivos del cursoDeclarativo vs. imperativoHistoria de la programacin lgica

2. Deduccin PrologDeduccin Prolog en lgica proposicionalDeduccin Prolog en lgica relacionalDeduccin Prolog en lgica funcional

2 / 27

6 Captulo 1. El sistema deductivo de Prolog


7/262


Introduccin

Objetivos del curso

Tema 1: El sistema deductivo de Prolog


2. Deduccin Prolog

3 / 27


Introduccin

Objetivos del curso

Objetivos del curso

Lgica como: sistema de especificacin y lenguaje de programacin

Principios: Programas = Teoras Ejecucin = Bsqueda de pruebas Programacin = Modelizacin

Prolog = Programming in Logic Relaciones con otros campos:

Inteligencia artificial Sistemas basados en el conocimiento Procesamiento del lenguaje natural

4 / 27

Programacin lgica e I.A. 7


8/262


Introduccin

Declarativo vs. imperativo



2. Deduccin Prolog

5 / 27


Introduccin



Paradigmas Imperativo: Se describe cmo resolver el problema Declarativo: Se describe qu es el problema

Programas Imperativo: Una sucesin de instrucciones Declarativo: Un conjunto de sentencias

Lenguajes Imperativo: Pascal, C, Fortran Declarativo: Prolog, Lisp puro, ML, Haskell

Ventajas Imperativo: Programas rpidos y especializados Declarativo: Programas generales, cortos y legibles

6 / 27



9/262


Introduccin

Historia de la programacin lgica



2. Deduccin Prolog

7 / 27


Introduccin



1960: Demostracin automtica de teoremas

1965: Resolucin y unificacin (Robinson) 1969: QA3, obtencin de respuesta (Green)

1972: Implementacin de Prolog (Colmerauer) 1974: Programacin lgica (Kowalski)

1977: Prolog de Edimburgo (Warren) 1981: Proyecto japons de Quinta Generacin

1986: Programacin lgica con restricciones 1995: Estndar ISO de Prolog

8 / 27



10/262


Deduccin Prolog

Deduccin Prolog en lgica proposicional


1. Introduccin


9 / 27


Deduccin Prolog



Base de conocimiento y objetivo: Base de conocimiento:

Regla 1: Si un animal es ungulado y tiene rayas negras, entonces

es una cebra. Regla 2: Si un animal rumia y es mamfero, entonces es ungulado. Regla 3: Si un animal es mamfero y tiene pezuas, entonces es

ungulado. Hecho 1: El animal es mamfero. Hecho 2: El animal tiene pezuas. Hecho 3: El animal tiene rayas negras.

Objetivo: Demostrar a partir de la base de conocimientos que elanimal es una cebra.

10 / 27



11/262


Deduccin Prolog



Programa:

e s _ c e b r a : - e s _ u n g u l a d o , t i e n e _ r a y a s _ n e g r a s . % R 1

e s _ u n g u l a d o : - r u m i a , e s _ m a m f e r o . % R 2

e s _ u n g u l a d o : - e s _ m a m f e r o , t i e n e _ p e z u a s . % R 3

e s _ m a m f e r o . % H 1

t i e n e _ p e z u a s . % H 2

t i e n e _ r a y a s _ n e g r a s . % H 3

Sesin:> p l

W e l c o m e t o S W I - P r o l o g ( M u l t i - t h r e a d e d , V e r s i o n 5 . 6 . 2 0 )

C o p y r i g h t ( c ) 1 9 9 0 - 2 0 0 6 U n i v e r s i t y o f A m s t e r d a m .

? - [ a n i m a l e s ] .

Y e s

? - e s _ c e b r a .

Y e s

11 / 27


Deduccin Prolog



rbol de deduccin:

12 / 27



12/262


Deduccin Prolog



Demostracin por resolucin SLD:

13 / 27


Deduccin Prolog

Deduccin Prolog en lgica relacional


1. Introduccin


14 / 27



13/262


Deduccin Prolog



Base de conocimiento: Hechos 1-4: 6 y 12 son divisibles por 2 y por 3. Hecho 5: 4 es divisible por 2. Regla 1: Los nmeros divisibles por 2 y por 3 son divisibles por 6.

Programa:

d i v i d e ( 2 , 6 ) . % H e c h o 1

d i v i d e ( 2 , 4 ) . % H e c h o 2

d i v i d e ( 2 , 1 2 ) . % H e c h o 3

d i v i d e ( 3 , 6 ) . % H e c h o 4

d i v i d e ( 3 , 1 2 ) . % H e c h o 5

d i v i d e ( 6 , X ) : - d i v i d e ( 2 , X ) , d i v i d e ( 3 , X ) . % R e g l a 1

15 / 27


Deduccin Prolog



Smbolos: Constantes: 2, 3, 4, 6, 12 Relacin binaria: divide Variable: X

Interpretaciones de la Regla 1: divide(6,X) :- divide(2,X), divide(3,X).

Interpretacin declarativa:(X)[divide(2, X) divide(3, X) divide(6, X)]

Interpretacin procedimental.

Consulta: Cules son los mltiplos de 6?

? - d i v i d e ( 6 , X ) .

X = 6 ;

X = 1 2 ;

N o

16 / 27



14/262


Deduccin Prolog



rbol de deduccin:

Comentarios: Unificacin. Clculo de respuestas. Respuestas mltiples.

17 / 27


Deduccin Prolog

Deduccin Prolog en lgica funcional


1. Introduccin


18 / 27



15/262


Deduccin Prolog



Representacin de los nmeros naturales:0, s(0), s(s(0)), . . .

Definicin de la suma:

0 + Y = Y

s ( X ) + Y = s ( X + Y )

Programa

s u m a ( 0 , Y , Y ) . % R 1

s u m a ( s ( X ) , Y , s ( Z ) ) : - s u m a ( X , Y , Z ) . % R 2

Consulta: Cul es la suma de s(0) y s(s(0))?? - s u m a ( s ( 0 ) , s ( s ( 0 ) ) , X ) .

X = s ( s ( s ( 0 ) ) )

Y e s

19 / 27


Deduccin Prolog



rbol de deduccin:

20 / 27



16/262


Deduccin Prolog



Consulta: Cul es la resta de s(s(s(0))) y s(s(0))? Sesin:

? - s u m a ( X , s ( s ( 0 ) ) , s ( s ( s ( 0 ) ) ) ) .

X = s ( 0 ) ;

N o

21 / 27


Deduccin Prolog



rbol de deduccin:

22 / 27



17/262


Deduccin Prolog



Consulta: Pregunta: Cules son las soluciones de la ecuacin

X + Y = s(s(0))? Sesin:

? - s u m a ( X , Y , s ( s ( 0 ) ) ) .

X = 0 Y = s ( s ( 0 ) ) ;

X = s ( 0 ) Y = s ( 0 ) ;

X = s ( s ( 0 ) ) Y = 0 ;

N o

23 / 27


Deduccin Prolog



rbol de deduccin:

24 / 27



18/262


Deduccin Prolog



Consulta: Pregunta: resolver el sistema de ecuaciones

1 + X = YX+ Y = 1

Sesin:

? - s u m a ( s ( 0 ) , X , Y ) , s u m a ( X , Y , s ( 0 ) ) .

X = 0

Y = s ( 0 ) ;

N o

25 / 27


Deduccin Prolog



rbol de deduccin:

26 / 27



19/262


Bibliografa

Bibliografa

1. J.A. Alonso (2006) Introduccin a la programacin lgica conProlog. Cap. 0: Introduccin.

2. I. Bratko (1990) Prolog Programming for Artificial Intelligence(2nd ed.) Cap. 1: An overview of Prolog. Cap. 2: Syntax and meaning of Prolog programs.

3. W.F. Clocksin y C.S. Mellish (1994) Programming in Prolog(Fourth Edition). Cap. 1: Tutorial introduction. Cap. 2: A closer look.

27 / 27



20/262



21/262

Captulo 2

Introduccin a la programacin lgica

con Prolog

21


22/262

PD Tema 2: Prolog

Programacin lgica (200809)Tema 2: Prolog




1 / 65

PD Tema 2: Prolog

1. Listas

2. Disyunciones

3. Operadores y aritmtica

4. Corte, negacin y condicional

5. Relaciones sobre trminos

6. Transformacin entre trminos, tomos y listas

7. Procedimientos aplicativos

2 / 65

22 Captulo 2. Introduccin a la programacin lgica con Prolog


23/262

PD Tema 2: Prolog

Listas

Construccin de listas

Tema 2: Prolog

1. ListasConstruccin de listasDefinicin de relaciones sobre listas

Concatenacin de listas

Relacin de pertenencia

2. Disyunciones



5. Relaciones sobre trminos3 / 65

PD Tema 2: Prolog

Listas


Construccin de listas Definicin de listas:

La lista vaca [] es una lista. Si L es una lista, entonces .(a,L) es una lista.

Ejemplos:? - . ( X , Y ) = [ a ] .

X = a

Y = [ ]

? - . ( X , Y ) = [ a , b ] .

X = a

Y = [ b ]

? - . ( X , . ( Y , Z ) ) = [ a , b ] .

X = a

Y = b

Z = [ ]

4 / 65



24/262

PD Tema 2: Prolog

Listas


Escritura abreviada Escritura abreviada:

[ X | Y ] = . ( X , Y )

Ejemplos con escritura abreviada:

? - [ X | Y ] = [ a , b ] .

X = a

Y = [ b ]

? - [ X | Y ] = [ a , b , c , d ] .

X = a

Y = [ b , c , d ]

? - [ X , Y | Z ] = [ a , b , c , d ] .

X = a

Y = b

Z = [ c , d ]

5 / 65

PD Tema 2: Prolog

Listas

Definicin de relaciones sobre listas

Tema 2: Prolog

1. ListasConstruccin de listasDefinicin de relaciones sobre listas

Concatenacin de listas

Relacin de pertenencia

2. Disyunciones



5. Relaciones sobre trminos6 / 65



25/262

PD Tema 2: Prolog

Listas


Definicin de concatenacin (append) Especificacin: conc(A,B,C) se verifica si C es la lista obtenida

escribiendo los elementos de la lista B a continuacin de loselementos de la lista A. Por ejemplo,

? - c o n c ( [ a , b ] , [ b , d ] , C ) .

C = [ a , b , b , d ]

Definicin 1:

c o n c ( A , B , C ) : - A = [ ] , C = B .

c o n c ( A , B , C ) : - A = [ X | D ] , c o n c ( D , B , E ) , C = [ X | E ] .

Definicin 2:

c o n c ( [ ] , B , B ) .

c o n c ( [ X | D ] , B , [ X | E ] ) : - c o n c ( D , B , E ) .

7 / 65

PD Tema 2: Prolog

Listas


Consultas con la relacin de concatenacin Analoga entre la definicin de conc y la de suma, Cul es el resultado de concatenar las listas [a,b] y [c,d,e]?

? - c o n c ( [ a , b ] , [ c , d , e ] , L ) .

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

Qu lista hay que aadirle a la lista [a,b] para obtener[a,b,c,d]?

? - c o n c ( [ a , b ] , L , [ a , b , c , d ] ) .

L = [ c , d ]

Qu dos listas hay que concatenar para obtener [a,b]?? - c o n c ( L , M , [ a , b ] ) .

L = [ ] M = [ a , b ] ;

L = [ a ] M = [ b ] ;

L = [ a , b ] M = [ ] ;

N o

8 / 65



26/262

PD Tema 2: Prolog

Listas


rbol de deduccin de ?- conc(L,M,[a,b]).

9 / 65

PD Tema 2: Prolog

Listas


Definicin de la relacin de pertenencia (member) Especificacin: pertenece(X,L) se verifica si X es un elemento

de la lista L. Definicin 1:

p e r t e n e c e ( X , [ X | L ] ) .

p e r t e n e c e ( X , [ Y | L ] ) : - p e r t e n e c e ( X , L ) .

Definicin 2:

p e r t e n e c e ( X , [ X | _ ] ) .

p e r t e n e c e ( X , [ _ | L ] ) : - p e r t e n e c e ( X , L ) .

10 / 65



27/262

PD Tema 2: Prolog

Listas


Consultas con la relacin de pertenencia

? - p e r t e n e c e ( b , [ a , b , c ] ) .

Y e s

? - p e r t e n e c e ( d , [ a , b , c ] ) .

N o

? - p e r t e n e c e ( X , [ a , b , a ] ) .

X = a ;

X = b ;

X = a ;

N o

? - p e r t e n e c e ( a , L ) .

L = [ a | _ G 2 3 3 ] ;

L = [ _ G 2 3 2 , a | _ G 2 3 6 ] ;

L = [ _ G 2 3 2 , _ G 2 3 5 , a | _ G 2 3 9 ]

Y e s

11 / 65

PD Tema 2: Prolog

Listas


rbol de deduccin de ?- pertenece(a,L).

12 / 65



28/262

PD Tema 2: Prolog

Disyunciones

Disyunciones Definicin de pertenece con disyuncin

p e r t e n e c e ( X , [ Y | L ] ) : - X = Y ; p e r t e n e c e ( X , L ) .

Definicin equivalente sin disyuncin

p e r t e n e c e ( X , [ Y | L ] ) : - X = Y .

p e r t e n e c e ( X , [ Y | L ] ) : - p e r t e n e c e ( X , L ) .

13 / 65

PD Tema 2: Prolog

Operadores y aritmtica

Operadores

Tema 2: Prolog

1. Listas

2. Disyunciones

3. Operadores y aritmticaOperadoresOperadores aritmticos

Definicin de operadores

AritmticaEvaluacin de expresiones aritmticas

Definicin de relaciones aritmticas


14 / 65



29/262

PD Tema 2: Prolog


Operadores

Ejemplos de operadores aritmticos Ejemplos de notacin infija y prefija en expresiones aritmticas:

? - + ( X , Y ) = a + b .

X = a

Y = b

? - + ( X , Y ) = a + b + c .

X = a + b

Y = c

? - + ( X , Y ) = a + ( b + c ) .

X = a

Y = b + c

? - a + b + c = ( a + b ) + c .

Y e s

? - a + b + c = a + ( b + c ) .

N o

15 / 65

PD Tema 2: Prolog


Operadores

Ejemplos de asociatividad y precedencia Ejemplos de asociatividad:

? - X ^ Y = a ^ b ^ c .

X = a Y = b ^ c

? - a ^ b ^ c = a ^ ( b ^ c ) .

Y e s

Ejemplo de precedencia? - X + Y = a + b * c .

X = a Y = b * c

? - X * Y = a + b * c .

N o

? - X * Y = ( a + b ) * c .

X = a + b Y = c

? - a + b * c = ( a + b ) * c .

N o

16 / 65



30/262

PD Tema 2: Prolog


Operadores

Operadores aritmticos predefinidos

Precedencia Tipo Operadores500 yfx +,- Infijo asocia por la izquierda500 fx - Prefijo no asocia400 yfx *, / Infijo asocia por la izquierda200 xfy ^ Infijo asocia por la derecha

17 / 65

PD Tema 2: Prolog


Operadores

Definicin de operadores Definicin (ejemplo_operadores.pl)

: - o p ( 8 0 0 , x f x , e s t u d i a n ) .

: - o p ( 4 0 0 , x f x , y ) .

j u a n y a n a e s t u d i a n l g i c a .

Consultas? - [ e j e m p l o _ o p e r a d o r e s ] .

? - Q u i e n e s e s t u d i a n l g i c a .

Q u i e n e s = j u a n y a n a

? - j u a n y O t r o e s t u d i a n A l g o .

O t r o = a n a

A l g o = l g i c a

18 / 65



31/262

PD Tema 2: Prolog


Aritmtica

Tema 2: Prolog

1. Listas

2. Disyunciones

3. Operadores y aritmticaOperadores

Operadores aritmticos

Definicin de operadores

AritmticaEvaluacin de expresiones aritmticas

Definicin de relaciones aritmticas


19 / 65

PD Tema 2: Prolog


Aritmtica

Evaluacin de expresiones aritmticas Evaluacin de expresiones aritmtica con is.

? - X i s 2 + 3 ^ 3 .

X = 2 9

? - X i s 2 + 3 , Y i s 2 * X .

X = 5 Y = 1 0

Relaciones aritmticas: =, =:= y =/=? - 3 = < 5 .

Y e s

? - 3 > X .

% [ W A R N I N G : A r g u m e n t s a r e n o t s u f f i c i e n t l y i n s t a n t i a t e d ]

? - 2 + 5 = 1 0 - 3 .

N o

? - 2 + 5 = : = 1 0 - 3 .

Y e s

20 / 65



32/262

PD Tema 2: Prolog


Aritmtica

Definicin del factorial factorial(X,Y) se verifica si Y es el factorial de X. Por ejemplo,

? - f a c t o r i a l ( 3 , Y ) .

Y = 6 ;

N o

Definicin:

f a c t o r i a l ( 1 , 1 ) .

f a c t o r i a l ( X , Y ) : -

X > 1 ,

A i s X - 1 ,

f a c t o r i a l ( A , B ) ,

Y i s X * B .

21 / 65

PD Tema 2: Prolog


Aritmtica

rbol de deduccin de ?- factorial(3,Y).

22 / 65



33/262

PD Tema 2: Prolog

Corte, negacin y condicional

Corte

Tema 2: Prolog

1. Listas

2. Disyunciones


4. Corte, negacin y condicionalCorte

Control mediante corte

Ejemplos usando el corte

Negacin como falloDefinicin de la negacin como fallo

Programas con negacin como fallo

El condicional23 / 65

PD Tema 2: Prolog


Corte

Ejemplo de nota sin corte nota(X,Y) se verifica si Y es la calificacin correspondiente a la

nota X; es decir, Y es suspenso si X es menor que 5, Y esaprobado si X es mayor o igual que 5 pero menor que 7, Y esnotable si X es mayor que 7 pero menor que 9 e Y essobresaliente si X es mayor que 9. Por ejemplo,

? - n o t a ( 6 , Y ) .

Y = a p r o b a d o ;

N o

n o t a ( X , s u s p e n s o ) : - X < 5 .

n o t a ( X , a p r o b a d o ) : - X > = 5 , X < 7 .

n o t a ( X , n o t a b l e ) : - X > = 7 , X < 9 .

n o t a ( X , s o b r e s a l i e n t e ) : - X > = 9 .

24 / 65



34/262

PD Tema 2: Prolog


Corte

Deduccin en el ejemplo sin corte rbol de deduccin de ?- nota(6,Y).

25 / 65

PD Tema 2: Prolog


Corte

Ejemplo de nota con cortes Definicin de nota con cortes

n o t a ( X , s u s p e n s o ) : - X < 5 , ! .

n o t a ( X , a p r o b a d o ) : - X < 7 , ! .

n o t a ( X , n o t a b l e ) : - X < 9 , ! .

n o t a ( X , s o b r e s a l i e n t e ) .

26 / 65



35/262

PD Tema 2: Prolog


Corte

Deduccin en el ejemplo con cortes

Un 6 es un sobresaliente?? - n o t a ( 6 , s o b r e s a l i e n t e ) .

Y e s

27 / 65

PD Tema 2: Prolog


Corte

Uso de corte para respuesta nica Diferencia entre member y memberchk

? - m e m b e r ( X , [ a , b , a , c ] ) , X = a .

X = a ;

X = a ;

N o

? - m e m b e r c h k ( X , [ a , b , a , c ] ) , X = a .

X = a ;

N o

Definicin de member y memberchk:

m e m b e r ( X , [ X | _ ] ) .

m e m b e r ( X , [ _ | L ] ) : - m e m b e r ( X , L ) .

m e m b e r c h k ( X , [ X | _ ] ) : - ! .

m e m b e r c h k ( X , [ _ | L ] ) : - m e m b e r c h k ( X , L ) .

28 / 65



36/262

PD Tema 2: Prolog


Negacin como fallo

Tema 2: Prolog

1. Listas

2. Disyunciones








PD Tema 2: Prolog


Negacin como fallo

Definicin de la negacin como fallo Definicin de la negacin como fallo not:

n o ( P ) : - P , ! , f a i l . % N o 1

n o ( P ) . % N o 2

30 / 65



37/262

PD Tema 2: Prolog


Negacin como fallo

Programa con negacin Programa:

a p r o b a d o ( X ) : - % R 1

n o ( s u s p e n s o ( X ) ) ,

m a t r i c u l a d o ( X ) .

m a t r i c u l a d o ( j u a n ) . % R 2

m a t r i c u l a d o ( l u i s ) . % R 3

s u s p e n s o ( j u a n ) . % R 4

Consultas:? - a p r o b a d o ( l u i s ) .

Y e s

? - a p r o b a d o ( X ) .

N o

31 / 65

PD Tema 2: Prolog


Negacin como fallo

rbol de deduccin de ?- aprobado(luis).

32 / 65



38/262

PD Tema 2: Prolog


Negacin como fallo

rbol de deduccin de ?- aprobado(X).

33 / 65

PD Tema 2: Prolog


Negacin como fallo

Modificacin del orden de los literales Programa:

a p r o b a d o ( X ) : - % R 1

m a t r i c u l a d o ( X ) ,

n o ( s u s p e n s o ( X ) ) .

m a t r i c u l a d o ( j u a n ) . % R 2

m a t r i c u l a d o ( l u i s ) . % R 3

s u s p e n s o ( j u a n ) . % R 4

Consulta:

? - a p r o b a d o ( X ) .

X = l u i s

Y e s

34 / 65



39/262

PD Tema 2: Prolog


Negacin como fallo

rbol de deduccin de ?- aprobado(X).

35 / 65

PD Tema 2: Prolog


Negacin como fallo

Ejemplo de definicin con not y con corte borra(L1,X,L2) se verifica si L2 es la lista obtenida eliminando

los elementos de L1 unificables simultneamente con X. Porejemplo,

? - b o r r a ( [ a , b , a , c ] , a , L ) .

L = [ b , c ] ;

N o

? - b o r r a ( [ a , Y , a , c ] , a , L ) .

Y = a

L = [ c ] ;

N o

? - b o r r a ( [ a , Y , a , c ] , X , L ) .

Y = a

X = a

L = [ c ] ;

N o

36 / 65



40/262

PD Tema 2: Prolog


Negacin como fallo

Ejemplo de definicin con not y con corte Definicin con not:

b o r r a _ 1 ( [ ] , _ , [ ] ) .

b o r r a _ 1 ( [ X | L 1 ] , Y , L 2 ) : -

X = Y ,

b o r r a _ 1 ( L 1 , Y , L 2 ) .

b o r r a _ 1 ( [ X | L 1 ] , Y , [ X | L 2 ] ) : -

n o t ( X = Y ) ,

b o r r a _ 1 ( L 1 , Y , L 2 ) .

37 / 65

PD Tema 2: Prolog


Negacin como fallo

Ejemplo de definicin con not y con corte Definicin con corte:

b o r r a _ 2 ( [ ] , _ , [ ] ) .

b o r r a _ 2 ( [ X | L 1 ] , Y , L 2 ) : -

X = Y , ! ,

b o r r a _ 2 ( L 1 , Y , L 2 ) .

b o r r a _ 2 ( [ X | L 1 ] , Y , [ X | L 2 ] ) : -

% n o t ( X = Y ) ,

b o r r a _ 2 ( L 1 , Y , L 2 ) .

38 / 65



41/262

PD Tema 2: Prolog


Negacin como fallo

Ejemplo de definicin con not y con corte Definicin con corte y simplificada

b o r r a _ 3 ( [ ] , _ , [ ] ) .

b o r r a _ 3 ( [ X | L 1 ] , X , L 2 ) : -

! ,

b o r r a _ 3 ( L 1 , Y , L 2 ) .

b o r r a _ 3 ( [ X | L 1 ] , Y , [ X | L 2 ] ) : -

% n o t ( X = Y ) ,

b o r r a _ 3 ( L 1 , Y , L 2 ) .

39 / 65

PD Tema 2: Prolog


El condicional

Tema 2: Prolog

1. Listas

2. Disyunciones










42/262

PD Tema 2: Prolog


El condicional

Definicin de nota con el condicional Definicin de nota con el condicional:

n o t a ( X , Y ) : -

X < 5 - > Y = s u s p e n s o ; % R 1

X < 7 - > Y = a p r o b a d o ; % R 2

X < 9 - > Y = n o t a b l e ; % R 3

t r u e - > Y = s o b r e s a l i e n t e . % R 4

Definicin del condicional y verdad:

P - > Q : - P , ! , Q . % D e f . - >

P - > Q .

t r u e . % D e f . t r u e

41 / 65

PD Tema 2: Prolog


El condicional

rbol de deduccin de ?- nota(6,Y).

42 / 65



43/262

PD Tema 2: Prolog

Relaciones sobre trminos

Predicados sobre tipos de trmino

Tema 2: Prolog

1. Listas

2. Disyunciones



5. Relaciones sobre trminosPredicados sobre tipos de trminoComparacin y ordenacin de trminos

6. Transformacin entre trminos, tomos y listas43 / 65

PD Tema 2: Prolog



Predicados sobre tipos de trmino var(T) se verifica si T es una variable. atom(T) se verifica si T es un tomo. number(T) se verifica si T es un nmero. compound(T) se verifica si T es un trmino compuesto. atomic(T) se verifica si T es una variable, tomo, cadena o

nmero.? - v a r ( X 1 ) . = > Y e s

? - a t o m ( t o m o ) . = > Y e s

? - n u m b e r ( 1 2 3 ) . = > Y e s

? - n u m b e r ( - 2 5 . 1 4 ) . = > Y e s

? - c o m p o u n d ( f ( X , a ) ) . = > Y e s

? - c o m p o u n d ( [ 1 , 2 ] ) . = > Y e s

? - a t o m i c ( t o m o ) . = > Y e s

? - a t o m i c ( 1 2 3 ) . = > Y e s

44 / 65



44/262

PD Tema 2: Prolog



Programa con predicados sobre tipos de trmino suma_segura(X,Y,Z) se verifica si X e Y son enteros y Z es la

suma de X e Y. Por ejemplo,? - s u m a _ s e g u r a ( 2 , 3 , X ) .

X = 5

Y e s

? - s u m a _ s e g u r a ( 7 , a , X ) .

N o

? - X i s 7 + a .

% [ W A R N I N G : A r i t h m e t i c : ` a ' i s n o t a f u n c t i o n ]

s u m a _ s e g u r a ( X , Y , Z ) : -

n u m b e r ( X ) ,

n u m b e r ( Y ) ,

Z i s X + Y .

45 / 65

PD Tema 2: Prolog


Comparacin y ordenacin de trminos

Tema 2: Prolog

1. Listas

2. Disyunciones



5. Relaciones sobre trminosPredicados sobre tipos de trminoComparacin y ordenacin de trminos

6. Transformacin entre trminos, tomos y listas46 / 65



45/262

PD Tema 2: Prolog



Relaciones de comparacin de trminos T1 = T2 se verifica si T1 y T2 son unificables.

T1 == T2 se verifica si T1 y T2 son idnticos. T1 \== T2 se verifica si T1 y T2 no son idnticos.

? - f ( X ) = f ( Y ) .

X = _ G 1 6 4

Y = _ G 1 6 4

Y e s

? - f ( X ) = = f ( Y ) .

N o

? - f ( X ) = = f ( X ) .

X = _ G 1 7 0

Y e s

47 / 65

PD Tema 2: Prolog



Programa con comparacin de trminos cuenta(A,L,N) se verifique si N es el nmero de ocurrencias del

tomo A en la lista L. Por ejemplo,? - c u e n t a ( a , [ a , b , a , a ] , N ) .

N = 3

? - c u e n t a ( a , [ a , b , X , Y ] , N ) .

N = 1

c u e n t a ( _ , [ ] , 0 ) .

c u e n t a ( A , [ B | L ] , N ) : -

A = = B , ! ,

c u e n t a ( A , L , M ) ,

N i s M + 1 .

c u e n t a ( A , [ B | L ] , N ) : -

% A \ = = B ,

c u e n t a ( A , L , N ) .

48 / 65



46/262

PD Tema 2: Prolog



Relaciones de ordenacin de trminos T1 @< T2 se verifica si el trmino T1 es anterior que T2 en el

orden de trminos de Prolog.

? - a b @ < a c . = > Y e s

? - 2 1 @ < 1 2 3 . = > Y e s

? - 1 2 @ < a . = > Y e s

? - g @ < f ( b ) . = > Y e s

? - f ( b ) @ < f ( a , b ) . = > Y e s

? - [ a , 1 ] @ < [ a , 3 ] . = > Y e s

sort(+L1,-L2) se verifica si L2 es la lista obtenida ordenandode manera creciente los distintos elementos de L1 y eliminandolas repeticiones.

? - s o r t ( [ c 4 , 2 , a 5 , 2 , c 3 , a 5 , 2 , a 5 ] , L ) .

L = [ 2 , a 5 , c 3 , c 4 ]

49 / 65

PD Tema 2: Prolog

Transformacin entre trminos, tomos y listas

Transformacin entre trminos y listas

Tema 2: Prolog

1. Listas

2. Disyunciones




6. Transformacin entre trminos, tomos y listasTransformacin entre trminos y listasTransformaciones entre tomos y listas

50 / 65



47/262

PD Tema 2: Prolog



Relacin de transformacin entre trminos y listas ?T =.. ?L se verifica si L es una lista cuyo primer elemento es el

functor del trmino T y los restantes elementos de L son losargumentos de T. Por ejemplo,

? - p a d r e ( j u a n , l u i s ) = . . L .

L = [ p a d r e , j u a n , l u i s ]

? - T = . . [ p a d r e , j u a n , l u i s ] .

T = p a d r e ( j u a n , l u i s )

51 / 65

PD Tema 2: Prolog



Programa con transformacin entre trminos y listas alarga(+F1,+N,-F2) se verifica si F1 y F2 son figuras del

mismo tipo y el tamao de F1 es el de F2 multiplicado por N,? - a l a r g a ( t r i n g u l o ( 3 , 4 , 5 ) , 2 , F ) .

F = t r i n g u l o ( 6 , 8 , 1 0 )

? - a l a r g a ( c u a d r a d o ( 3 ) , 2 , F ) .

F = c u a d r a d o ( 6 )

a l a r g a ( F i g u r a 1 , F a c t o r , F i g u r a 2 ) : -

F i g u r a 1 = . . [ T i p o | A r g 1 ] ,

m u l t i p l i c a _ l i s t a ( A r g 1 , F a c t o r , A r g 2 ) ,

F i g u r a 2 = . . [ T i p o | A r g 2 ] .

m u l t i p l i c a _ l i s t a ( [ ] , _ , [ ] ) .

m u l t i p l i c a _ l i s t a ( [ X 1 | L 1 ] , F , [ X 2 | L 2 ] ) : -

X 2 i s X 1 * F , m u l t i p l i c a _ l i s t a ( L 1 , F , L 2 ) .

52 / 65



48/262

PD Tema 2: Prolog



Las relaciones functor y arg functor(T,F,A) se verifica si F es el functor del trmino T y A

es su aridad.

arg(N,T,A) se verifica si A es el argumento del trmino T queocupa el lugar N.

? - f u n c t o r ( g ( b , c , d ) , F , A ) .

F = g

A = 3

? - f u n c t o r ( T , g , 2 ) .

T = g ( _ G 2 3 7 , _ G 2 3 8 )

? - a r g ( 2 , g ( b , c , d ) , X ) .

X = c

? - f u n c t o r ( T , g , 3 ) , a r g ( 1 , T , b ) , a r g ( 2 , T , c ) .

T = g ( b , c , _ G 4 0 5 )

53 / 65

PD Tema 2: Prolog


Transformaciones entre tomos y listas

Tema 2: Prolog

1. Listas

2. Disyunciones




6. Transformacin entre trminos, tomos y listasTransformacin entre trminos y listasTransformaciones entre tomos y listas

54 / 65



49/262

PD Tema 2: Prolog



Relacin de transformacin entre tomos y listas: name name(A,L) se verifica si L es la lista de cdigos ASCII de los

caracteres del tomo A. Por ejemplo,

? - n a m e ( b a n d e r a , L ) .

L = [ 9 8 , 9 7 , 1 1 0 , 1 0 0 , 1 0 1 , 1 1 4 , 9 7 ]

? - n a m e ( A , [ 9 8 , 9 7 , 1 1 0 , 1 0 0 , 1 0 1 , 1 1 4 , 9 7 ] ) .

A = b a n d e r a

55 / 65

PD Tema 2: Prolog



Programa con transformacin entre tomos y listas concatena_tomos(A1,A2,A3) se verifica si A3 es la

concatenacin de los tomos A1 y A2. Por ejemplo,

? - c o n c a t e n a _ t o m o s ( p i , o j o , X ) .

X = p i o j o

c o n c a t e n a _ t o m o s ( A 1 , A 2 , A 3 ) : -

n a m e ( A 1 , L 1 ) ,

n a m e ( A 2 , L 2 ) ,

a p p e n d ( L 1 , L 2 , L 3 ) ,

n a m e ( A 3 , L 3 ) .

56 / 65



50/262

PD Tema 2: Prolog

Procedimientos aplicativos

La relacin apply

Tema 2: Prolog

1. Listas

2. Disyunciones





7. Procedimientos aplicativos57 / 65

PD Tema 2: Prolog


La relacin apply

La relacin apply apply(T,L) se verifica si es demostrable T despus de aumentar

el nmero de sus argumentos con los elementos de L; porejemplo,

p l u s ( 2 , 3 , X ) . = > X = 5

a p p l y ( p l u s , [ 2 , 3 , X ] ) . = > X = 5

a p p l y ( p l u s ( 2 ) , [ 3 , X ] ) . = > X = 5

a p p l y ( p l u s ( 2 , 3 ) , [ X ] ) . = > X = 5

a p p l y ( a p p e n d ( [ 1 , 2 ] ) , [ X , [ 1 , 2 , 3 ] ] ) . = > X = [ 3 ]

n _ a p p l y ( T r m i n o , L i s t a ) : -

T r m i n o = . . [ P r e d | A r g 1 ] ,

a p p e n d ( A r g 1 , L i s t a , A r g 2 ) ,

t o m o = . . [ P r e d | A r g 2 ] ,

t o m o .

58 / 65



51/262

PD Tema 2: Prolog


La relacin maplist

Tema 2: Prolog

1. Listas

2. Disyunciones






PD Tema 2: Prolog


La relacin maplist

La relacin maplist maplist(P,L1,L2) se verifica si se cumple el predicado P sobre

los sucesivos pares de elementos de las listas L1 y L2; porejemplo,

? - s u c c ( 2 , X ) . = > 3

? - s u c c ( X , 3 ) . = > 2

? - m a p l i s t ( s u c c , [ 2 , 4 ] , [ 3 , 5 ] ) . = > Y e s

? - m a p l i s t ( s u c c , [ 0 , 4 ] , [ 3 , 5 ] ) . = > N o

? - m a p l i s t ( s u c c , [ 2 , 4 ] , Y ) . = > Y = [ 3 , 5 ]

? - m a p l i s t ( s u c c , X , [ 3 , 5 ] ) . = > X = [ 2 , 4 ]

n _ m a p l i s t ( _ , [ ] , [ ] ) .

n _ m a p l i s t ( R , [ X 1 | L 1 ] , [ X 2 | L 2 ] ) : -

a p p l y ( R , [ X 1 , X 2 ] ) ,

n _ m a p l i s t ( R , L 1 , L 2 ) .

60 / 65



52/262

PD Tema 2: Prolog

Todas las soluciones

Predicados de todas las soluciones

Tema 2: Prolog

1. Listas

2. Disyunciones






PD Tema 2: Prolog



Lista de soluciones (findall) findall(T,O,L) se verifica si L es la lista de las instancias del

trmino T que verifican el objetivo O.? - a s s e r t ( c l a s e ( a , v o c ) ) , a s s e r t ( c l a s e ( b , c o n ) ) ,

a s s e r t ( c l a s e ( e , v o c ) ) , a s s e r t ( c l a s e ( c , c o n ) ) .

? - f i n d a l l ( X , c l a s e ( X , v o c ) , L ) .

X = _ G 3 3 1 L = [ a , e ]

? - f i n d a l l ( _ X , c l a s e ( _ X , _ C l a s e ) , L ) .

L = [ a , b , e , c ]

? - f i n d a l l ( X , c l a s e ( X , v o c a l ) , L ) .

X = _ G 3 5 5 L = [ ]

? - f i n d a l l ( X , ( m e m b e r ( X , [ c , b , c ] ) , m e m b e r ( X , [ c , b , a ] ) ) , L ) .

X = _ G 3 7 3 L = [ c , b , c ]

? - f i n d a l l ( X , ( m e m b e r ( X , [ c , b , c ] ) , m e m b e r ( X , [ 1 , 2 , 3 ] ) ) , L ) .

X = _ G 3 7 3 L = [ ]

62 / 65



53/262

PD Tema 2: Prolog



Conjunto de soluciones (setof) setof(T,O,L) se verifica si L es la lista ordenada sin repeticiones

de las instancias del trmino T que verifican el objetivo O.? - s e t o f ( X , c l a s e ( X , C l a s e ) , L ) .

X = _ G 3 4 3 C l a s e = v o c L = [ a , e ] ;

X = _ G 3 4 3 C l a s e = c o n L = [ b , c ] ;

N o

? - s e t o f ( X , Y ^ c l a s e ( X , Y ) , L ) .

X = _ G 3 7 9 Y = _ G 3 8 0 L = [ a , b , c , e ]

? - s e t o f ( X , c l a s e ( X , v o c a l ) , L ) .

N o

? - s e t o f ( X , ( m e m b e r ( X , [ c , b , c ] ) , m e m b e r ( X , [ c , b , a ] ) ) , L ) .

X = _ G 3 6 1 L = [ b , c ]

? - s e t o f ( X , ( m e m b e r ( X , [ c , b , c ] ) , m e m b e r ( X , [ 1 , 2 , 3 ] ) ) , L ) .

N o

63 / 65

PD Tema 2: Prolog



Multiconjunto de soluciones (bagof) bagof(T,O,L) se verifica si L es el multiconjunto de las

instancias del trmino T que verifican el objetivo O.? - b a g o f ( X , c l a s e ( X , C l a s e ) , L ) .

X = _ G 3 4 3 C l a s e = v o c L = [ a , e ] ;

X = _ G 3 4 3 C l a s e = c o n L = [ b , c ] ;

N o

? - b a g o f ( X , Y ^ c l a s e ( X , Y ) , L ) .

X = _ G 3 7 9 Y = _ G 3 8 0 L = [ a , b , e , c ]

? - b a g o f ( X , c l a s e ( X , v o c a l ) , L ) .

N o

? - b a g o f ( X , ( m e m b e r ( X , [ c , b , c ] ) , m e m b e r ( X , [ c , b , a ] ) ) , L ) .

X = _ G 3 6 1 L = [ c , b , c ]

? - b a g o f ( X , ( m e m b e r ( X , [ c , b , c ] ) , m e m b e r ( X , [ 1 , 2 , 3 ] ) ) , L ) .

N o

64 / 65



54/262

PD Tema 2: Prolog

Bibliografa

Bibliografa

1. J.A. Alonso Introduccin a la programacin lgica con Prolog.

2. I. Bratko Prolog Programming for Artificial Intelligence (3 ed.)

3. T. Van Le Techniques of Prolog Programming

4. W.F. Clocksin y C.S. Mellish Programming in Prolog (FourthEdition) (Springer Verlag, 1994)

65 / 65



55/262

Captulo 3

Programacin con Prolog

55


56/262

PD Tema 3: Programacin con Prolog

Programacin lgica (200809)Tema 3: Programacin con Prolog




1 / 41


1. Acumuladores

2. Combinatoria

3. Generacin y prueba

4. Autmatas no deterministas

5. Problemas de grafos

2 / 41

56 Captulo 3. Programacin con Prolog


57/262


Acumuladores

Acumuladores

inversa(+L1,-L2), reverse(L1,L2), se verifica si L2 es lalista inversa de L1. Por ejemplo,

? - i n v e r s a ( [ a , b , c ] , L ) .

L = [ c , b , a ]

Definicin de inversa con append (no recursiva final):

i n v e r s a _ 1 ( [ ] , [ ] ) .

i n v e r s a _ 1 ( [ X | L 1 ] , L 2 ) : -

i n v e r s a _ 1 ( L 1 , L 3 ) ,

a p p e n d ( L 3 , [ X ] , L 2 ) .

3 / 41


Acumuladores

Acumuladores

Definicin de inversa con acumuladores (recursiva final):

i n v e r s a _ 2 ( L 1 , L 2 ) : -

i n v e r s a _ 2 _ a u x ( L 1 , [ ] , L 2 ) .

i n v e r s a _ 2 _ a u x ( [ ] , L , L ) .

i n v e r s a _ 2 _ a u x ( [ X | L ] , A c u m , L 2 ) : -

i n v e r s a _ 2 _ a u x ( L , [ X | A c u m ] , L 2 ) .

4 / 41



58/262


Acumuladores

Comparacin de eficiencia

? - f i n d a l l ( _ N , b e t w e e n ( 1 , 1 0 0 0 , _ N ) , _ L 1 ) ,

t i m e ( i n v e r s a _ 1 ( _ L 1 , _ ) ) , t i m e ( i n v e r s a _ 2 ( _ L 1 , _ ) ) .

5 0 1 , 5 0 1 i n f e r e n c e s i n 0 . 4 0 s e c o n d s

1 , 0 0 2 i n f e r e n c e s i n 0 . 0 0 s e c o n d s



2 , 0 0 3 , 0 0 1 i n f e r e n c e s i n 1 . 5 9 s e c o n d s






5 / 41


Combinatoria

Combinaciones

combinacin(+L1,+N,-L2) se verifica si L2 es una combinacinNaria de L1. Por ejemplo,

? - c o m b i n a c i n ( [ a , b , c ] , 2 , L ) .

L = [ a , b ] ; L = [ a , c ] ; L = [ b , c ] ; N o

c o m b i n a c i n _ 1 ( L 1 , N , L 2 ) : -

s u b c o n j u n t o ( L 2 , L 1 ) ,

l e n g t h ( L 2 , N ) .

c o m b i n a c i n _ 2 ( L 1 , N , L 2 ) : -

l e n g t h ( L 2 , N ) ,

s u b c o n j u n t o ( L 2 , L 1 ) .

c o m b i n a c i n ( L 1 , N , L 2 ) : -

c o m b i n a c i n _ 2 ( L 1 , N , L 2 ) .

6 / 41



59/262


Combinatoria

Combinaciones

combinaciones(+L1,+N,-L2) se verifica si L2 es la lista de lascombinaciones Narias de L1. Por ejemplo,

? - c o m b i n a c i o n e s ( [ a , b , c ] , 2 , L ) .

L = [ [ a , b ] , [ a , c ] , [ b , c ] ]

c o m b i n a c i o n e s _ 1 ( L 1 , N , L 2 ) : -

f i n d a l l ( L , c o m b i n a c i n _ 1 ( L 1 , N , L ) , L 2 ) .

c o m b i n a c i o n e s _ 2 ( L 1 , N , L 2 ) : -

f i n d a l l ( L , c o m b i n a c i n _ 2 ( L 1 , N , L ) , L 2 ) .

c o m b i n a c i o n e s ( L 1 , N , L 2 ) : -

c o m b i n a c i o n e s _ 2 ( L 1 , N , L 2 ) .

7 / 41


Combinatoria

Comparacin de eficiencia de combinaciones

? - f i n d a l l ( _ N , b e t w e e n ( 1 , 6 , _ N ) , _ L 1 ) ,

t i m e ( c o m b i n a c i o n e s _ 1 ( _ L 1 , 2 , _ L 2 ) ) ,

t i m e ( c o m b i n a c i o n e s _ 2 ( _ L 1 , 2 , _ L 2 ) ) .

4 2 9 i n f e r e n c e s i n 0 . 0 0 s e c o n d s

9 2 i n f e r e n c e s i n 0 . 0 0 s e c o n d s

? - f i n d a l l ( _ N , b e t w e e n ( 1 , 1 2 , _ N ) , _ L 1 ) ,



2 8 , 5 5 1 i n f e r e n c e s i n 0 . 0 1 s e c o n d s

4 5 7 i n f e r e n c e s i n 0 . 0 0 s e c o n d s

? - f i n d a l l ( _ N , b e t w e e n ( 1 , 2 4 , _ N ) , _ L 1 ) ,



1 1 7 , 4 3 9 , 9 7 1 i n f e r e n c e s i n 5 7 . 5 9 s e c o n d s

2 , 9 1 5 i n f e r e n c e s i n 0 . 0 0 s e c o n d s 8 / 41



60/262


Combinatoria

Permutaciones

select(?X,?L1,?L2) se verifica si X es un elemento de la listaL1 y L2 es la lista de los restantes elementos. Por ejemplo,

? - s e l e c t ( X , [ a , b , c ] , L ) .

X = a L = [ b , c ] ;

X = b L = [ a , c ] ;

X = c L = [ a , b ] ;

N o

? - s e l e c t ( a , L , [ b , c ] ) .

L = [ a , b , c ] ;

L = [ b , a , c ] ;

L = [ b , c , a ] ;

N o

9 / 41


Combinatoria

Permutaciones

permutacin(+L1,-L2) se verifica si L2 es una permutacin deL1. Por ejemplo,

? - p e r m u t a c i n ( [ a , b , c ] , L ) .

L = [ a , b , c ] ; L = [ a , c , b ] ;

L = [ b , a , c ] ; L = [ b , c , a ] ;

L = [ c , a , b ] ; L = [ c , b , a ] ;

N o

p e r m u t a c i n ( [ ] , [ ] ) .

p e r m u t a c i n ( L 1 , [ X | L 2 ] ) : -

s e l e c t ( X , L 1 , L 3 ) ,

p e r m u t a c i n ( L 3 , L 2 ) .

Predefinida permutation.

10 / 41



61/262


Combinatoria

Variaciones

variacin(+L1,+N,-L2) se verifica si L2 es una variacinNaria de L1. Por ejemplo,

? - v a r i a c i n ( [ a , b , c ] , 2 , L ) .

L = [ a , b ] ; L = [ a , c ] ; L = [ b , a ] ; L = [ b , c ] ; L = [ c , a ] ; L = [ c , b ] ; N o

v a r i a c i n _ 1 ( L 1 , N , L 2 ) : -

c o m b i n a c i n ( L 1 , N , L 3 ) , p e r m u t a c i n ( L 3 , L 2 ) .

v a r i a c i n _ 2 ( _ , 0 , [ ] ) .

v a r i a c i n _ 2 ( L 1 , N , [ X | L 2 ] ) : -

N > 0 , M i s N - 1 ,

s e l e c t ( X , L 1 , L 3 ) ,

v a r i a c i n _ 2 ( L 3 , M , L 2 ) .

v a r i a c i n ( L 1 , N , L 2 ) : - v a r i a c i n _ 2 ( L 1 , N , L 2 ) .

11 / 41


Combinatoria

Variaciones

variaciones(+L1,+N,-L2) se verifica si L2 es la lista de lasvariaciones Narias de L1. Por ejemplo,

? - v a r i a c i o n e s ( [ a , b , c ] , 2 , L ) .

L = [ [ a , b ] , [ a , c ] , [ b , a ] , [ b , c ] , [ c , a ] , [ c , b ] ]

v a r i a c i o n e s _ 1 ( L 1 , N , L 2 ) : -

s e t o f ( L , v a r i a c i n _ 1 ( L 1 , N , L ) , L 2 ) .

v a r i a c i o n e s _ 2 ( L 1 , N , L 2 ) : -

s e t o f ( L , v a r i a c i n _ 2 ( L 1 , N , L ) , L 2 ) .

v a r i a c i o n e s ( L 1 , N , L 2 ) : -

v a r i a c i o n e s _ 2 ( L 1 , N , L 2 ) .

12 / 41



62/262


Combinatoria

Comparacin de eficiencia de variaciones

? - f i n d a l l ( N , b e t w e e n ( 1 , 1 0 0 , N ) , L 1 ) ,

t i m e ( v a r i a c i o n e s _ 1 ( L 1 , 2 , L 2 ) ) ,

t i m e ( v a r i a c i o n e s _ 2 ( L 1 , 2 , L 2 ) ) .


4 0 , 1 1 9 i n f e r e n c e s i n 0 . 1 1 s e c o n d s









1 1 , 5 4 5 , 2 2 0 i n f e r e n c e s i n 1 9 . 0 2 s e c o n d s

6 4 0 , 4 1 9 i n f e r e n c e s i n 2 . 5 1 s e c o n d s 13 / 41


Generacin y prueba

Ordenacin

Tema 3: Programacin con Prolog

1. Acumuladores

2. Combinatoria

3. Generacin y pruebaOrdenacinCuadrado mgico



14 / 41



63/262


Generacin y prueba

Ordenacin

Ordenacin por generacin y prueba

ordenacin(+L1,-L2) se verifica si L2 es la lista obtenidaordenando la lista L1 en orden creciente. Por ejemplo,

? - o r d e n a c i n ( [ 2 , 1 , a , 2 , b , 3 ] , L ) .

L = [ a , b , 1 , 2 , 2 , 3 ]

o r d e n a c i n ( L , L 1 ) : -

p e r m u t a c i n ( L , L 1 ) ,

o r d e n a d a ( L 1 ) .

o r d e n a d a ( [ ] ) .

o r d e n a d a ( [ _ ] ) .

o r d e n a d a ( [ X , Y | L ] ) : -

X @ = < Y ,

o r d e n a d a ( [ Y | L ] ) .

15 / 41


Generacin y prueba

Ordenacin

Ordenacin por seleccin

o r d e n a c i n _ p o r _ s e l e c c i n ( L 1 , [ X | L 2 ] ) : -

s e l e c c i o n a _ m e n o r ( X , L 1 , L 3 ) ,

o r d e n a c i n _ p o r _ s e l e c c i n ( L 3 , L 2 ) .

o r d e n a c i n _ p o r _ s e l e c c i n ( [ ] , [ ] ) .

s e l e c c i o n a _ m e n o r ( X , L 1 , L 2 ) : -

s e l e c t ( X , L 1 , L 2 ) ,

n o t ( ( m e m b e r ( Y , L 2 ) , Y @ < X ) ) .

16 / 41



64/262


Generacin y prueba

Ordenacin

Ordenacin por divide y vencers

o r d e n a c i n _ r p i d a ( [ ] , [ ] ) .

o r d e n a c i n _ r p i d a ( [ X | R ] , O r d e n a d a ) : -

d i v i d e ( X , R , M e n o r e s , M a y o r e s ) ,

o r d e n a c i n _ r p i d a ( M e n o r e s , M e n o r e s _ o r d ) ,

o r d e n a c i n _ r p i d a ( M a y o r e s , M a y o r e s _ o r d ) ,

a p p e n d ( M e n o r e s _ o r d , [ X | M a y o r e s _ o r d ] , O r d e n a d a ) .

d i v i d e ( _ , [ ] , [ ] , [ ] ) .

d i v i d e ( X , [ Y | R ] , [ Y | M e n o r e s ] , M a y o r e s ) : -

Y @ < X , ! ,

d i v i d e ( X , R , M e n o r e s , M a y o r e s ) .

d i v i d e ( X , [ Y | R ] , M e n o r e s , [ Y | M a y o r e s ] ) : -

\ % Y @ > = X ,

d i v i d e ( X , R , M e n o r e s , M a y o r e s ) .

17 / 41


Generacin y prueba

Ordenacin

Ordenacin: comparacin de eficiencia

Comparacin de la ordenacin de la lista [N,N-1,N-2,...,2,1]

N ordena seleccin rpida

1 5 inf 0.00 s 8 inf 0.00 s 5 inf 0.00 s2 10 inf 0.00 s 19 inf 0.00 s 12 inf 0.00 s

4 80 inf 0.00 s 67 inf 0.00 s 35 inf 0.00 s

8 507,674 inf 0.33 s 323 inf 0.00 s 117 inf 0.00 s16 1,923 inf 0.00 s 425 inf 0.00 s32 13,059 inf 0.01 s 1,617 inf 0.00 s64 95,747 inf 0.05 s 6,305 inf 0.00 s

128 732,163 inf 0.40 s 24,897 inf 0.01 s

256 5,724,163 inf 2.95 s 98,945 inf 0.05 s512 45,264,899 inf 22.80 s 394,497 inf 0.49 s

18 / 41



65/262


Generacin y prueba

Cuadrado mgico


1. Acumuladores

2. Combinatoria

3. Generacin y pruebaOrdenacinCuadrado mgico



19 / 41


Generacin y prueba

Cuadrado mgico

Cuadrado mgico por generacin y prueba

Enunciado: Colocar los nmeros 1,2,3,4,5,6,7,8,9 en un cuadrado3x3 de forma que todas las lneas (filas, columnas y diagonales)sumen igual.

A B C

D E F

G H I

c u a d r a d o _ 1 ( [ A , B , C , D , E , F , G , H , I ] ) : -

p e r m u t a c i n ( [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] ,

[ A , B , C , D , E , F , G , H , I ] ) ,

A + B + C = : = 1 5 , D + E + F = : = 1 5 ,

G + H + I = : = 1 5 , A + D + G = : = 1 5 ,

B + E + H = : = 1 5 , C + F + I = : = 1 5 ,

A + E + I = : = 1 5 , C + E + G = : = 1 5 .

20 / 41



66/262


Generacin y prueba

Cuadrado mgico

Cuadrado mgico por generacin y prueba

Clculo de soluciones:

? - c u a d r a d o _ 1 ( L ) .

L = [ 6 , 1 , 8 , 7 , 5 , 3 , 2 , 9 , 4 ] ;

L = [ 8 , 1 , 6 , 3 , 5 , 7 , 4 , 9 , 2 ]

Y e s

Clculo del nmero soluciones:

? - f i n d a l l ( _ X , c u a d r a d o _ 1 ( _ X ) , _ L ) , l e n g t h ( _ L , N ) .

N = 8

Y e s

21 / 41


Generacin y prueba

Cuadrado mgico

Cuadrado mgico por comprobaciones parciales

Programa 2:

c u a d r a d o _ 2 ( [ A , B , C , D , E , F , G , H , I ] ) : -

s e l e c t ( A , [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] , L 1 ) ,

s e l e c t ( B , L 1 , L 2 ) ,

s e l e c t ( C , L 2 , L 3 ) , A + B + C = : = 1 5 ,

s e l e c t ( D , L 3 , L 4 ) ,

s e l e c t ( G , L 4 , L 5 ) , A + D + G = : = 1 5 ,

s e l e c t ( E , L 5 , L 6 ) , C + E + G = : = 1 5 ,

s e l e c t ( I , L 6 , L 7 ) , A + E + I = : = 1 5 ,

s e l e c t ( F , L 7 , [ H ] ) , C + F + I = : = 1 5 , D + E + F = : = 1 5 .

22 / 41



67/262


Generacin y prueba

Cuadrado mgico

Cuadrado mgico por comprobaciones parciales

Clculo de soluciones:

? - c u a d r a d o _ 2 ( L ) .

L = [ 2 , 7 , 6 , 9 , 5 , 1 , 4 , 3 , 8 ] ;

L = [ 2 , 9 , 4 , 7 , 5 , 3 , 6 , 1 , 8 ]

Y e s

Comprobacin que las dos definiciones dan las mismas soluciones.

? - s e t o f ( _ X , c u a d r a d o _ 1 ( _ X ) , _ L ) ,

s e t o f ( _ X , c u a d r a d o _ 2 ( _ X ) , _ L ) .

Y e s

23 / 41


Generacin y prueba

Cuadrado mgico

Comparacin de eficiencia del cuadrado mgico

? - t i m e ( c u a d r a d o _ 1 ( _ X ) ) .


? - t i m e ( c u a d r a d o _ 2 ( _ X ) ) .


? - t i m e ( s e t o f ( _ X , c u a d r a d o _ 1 ( _ X ) , _ L ) ) .


? - t i m e ( s e t o f ( _ X , c u a d r a d o _ 2 ( _ X ) , _ L ) ) .


24 / 41



68/262


Autmatas no deterministas

Representacin de un autmata no determinista


1. Acumuladores

2. Combinatoria


4. Autmatas no deterministasRepresentacin de un autmata no deterministaSimulacin de los autmatas no deterministasConsultas al autmata


25 / 41




Ejemplo de autmata no determinista (con estado final e3)

26 / 41



69/262




Representacin de un autmata (automata.pl)

final(E) se verifica si E es el estado final.

f i n a l ( e 3 ) .

trans(E1,X,E2) se verifica si se puede pasar del estado E1 alestado E2 usando la letra X.

t r a n s ( e 1 , a , e 1 ) . t r a n s ( e 1 , a , e 2 ) . t r a n s ( e 1 , b , e 1 ) .

t r a n s ( e 2 , b , e 3 ) .

t r a n s ( e 3 , b , e 4 ) .

nulo(E1,E2) se verifica si se puede pasar del estado E1 alestado E2 mediante un movimiento nulo.

n u l o ( e 2 , e 4 ) .

n u l o ( e 3 , e 1 ) .

27 / 41



Simulacin de los autmatas no deterministas


1. Acumuladores

2. Combinatoria




28 / 41



70/262





acepta(E,L) se verifica si el autmata, a partir del estado E

acepta la lista L. Por ejemplo,

a c e p t a ( e 1 , [ a , a , a , b ] ) = > S

a c e p t a ( e 2 , [ a , a , a , b ] ) = > N o

a c e p t a ( E , [ ] ) : -

f i n a l ( E ) .

a c e p t a ( E , [ X | L ] ) : -

t r a n s ( E , X , E 1 ) ,

a c e p t a ( E 1 , L ) .

a c e p t a ( E , L ) : -

n u l o ( E , E 1 ) ,

a c e p t a ( E 1 , L ) .

29 / 41



Consultas al autmata


1. Acumuladores

2. Combinatoria




30 / 41



71/262





Determinar si el autmata acepta la lista [a,a,a,b]

? - a c e p t a ( e 1 , [ a , a , a , b ] ) .

Y e s

Determinar los estados a partir de los cuales el autmata aceptala lista [a,b]

? - a c e p t a ( E , [ a , b ] ) .

E = e 1 ;

E = e 3 ;

N o

Determinar las palabras de longitud 3 aceptadas por el autmataa partir del estado e1

? - a c e p t a ( e 1 , [ X , Y , Z ] ) .

X = a Y = a Z = b ;

X = b Y = a Z = b ;

N o

31 / 41


Problemas de grafos

Representacin de grafos


1. Acumuladores

2. Combinatoria



5. Problemas de grafosRepresentacin de grafosCaminos en un grafoCaminos hamiltonianos en un grafo

32 / 41



72/262


Problemas de grafos


Grafo de Andaluca

33 / 41


Problemas de grafos


Representacin del grafo

arcos(+L) se verifica si L es la lista de arcos del grafo.

a r c o s ( [ h u e l v a - s e v i l l a , h u e l v a - c d i z ,

c d i z - s e v i l l a , s e v i l l a - m l a g a ,

s e v i l l a - c r d o b a , c r d o b a - m l a g a ,

c r d o b a - g r a n a d a , c r d o b a - j a n ,

j a n - g r a n a d a , j a n - a l m e r a ,

g r a n a d a - a l m e r a ] ) .

34 / 41



73/262


Problemas de grafos


Adyacencia y nodos

adyacente(?X,?Y) se verifica si X e Y son adyacentes.

a d y a c e n t e ( X , Y ) : -

a r c o s ( L ) ,

( m e m b e r ( X - Y , L ) ; m e m b e r ( Y - X , L ) ) .

nodos(?L) se verifica si L es la lista de nodos.

n o d o s ( L ) : -

s e t o f ( X , Y ^ a d y a c e n t e ( X , Y ) , L ) .

35 / 41


Problemas de grafos

Caminos en un grafo


1. Acumuladores

2. Combinatoria




36 / 41



74/262


Problemas de grafos

Caminos en un grafo

Caminos

camino(+A,+Z,-C) se verifica si C es un camino en el grafodesde el nodo A al Z. Por ejemplo,

? - c a m i n o ( s e v i l l a , g r a n a d a , C ) .

C = [ s e v i l l a , c r d o b a , g r a n a d a ] ;

C = [ s e v i l l a , m l a g a , c r d o b a , g r a n a d a ]

Y e s

c a m i n o ( A , Z , C ) : -

c a m i n o _ a u x ( A , [ Z ] , C ) .

37 / 41


Problemas de grafos

Caminos en un grafo

Caminos

camino_aux(+A,+CP,-C) se verifica si C es una camino en elgrafo compuesto de un camino desde A hasta el primer elementodel camino parcial CP (con nodos distintos a los de CP) junto CP.

c a m i n o _ a u x ( A , [ A | C 1 ] , [ A | C 1 ] ) .

c a m i n o _ a u x ( A , [ Y | C 1 ] , C ) : -

a d y a c e n t e ( X , Y ) ,

n o t ( m e m b e r ( X , [ Y | C 1 ] ) ) ,

c a m i n o _ a u x ( A , [ X , Y | C 1 ] , C ) .

38 / 41



75/262


Problemas de grafos

Caminos hamiltonianos en un grafo


1. Acumuladores

2. Combinatoria




39 / 41


Problemas de grafos


Caminos hamiltonianos

hamiltoniano(-C) se verifica si C es un camino hamiltoniano enel grafo (es decir, es un camino en el grafo que pasa por todossus nodos una vez). Por ejemplo,

? - h a m i l t o n i a n o ( C ) .

C = [ a l m e r a , j a n , g r a n a d a , c r d o b a , m l a g a , s e v i l l a , h u e l v a , c d i z ]

? - f i n d a l l ( _ C , h a m i l t o n i a n o ( _ C ) , _ L ) , l e n g t h ( _ L , N ) .

N = 1 6

Primera definicin de hamiltoniano

h a m i l t o n i a n o _ 1 ( C ) : -

c a m i n o ( _ , _ , C ) ,

n o d o s ( L ) ,

l e n g t h ( L , N ) ,

l e n g t h ( C , N ) .

40 / 41



76/262


Problemas de grafos


Caminos hamiltonianos

Segunda definicin de hamiltoniano

h a m i l t o n i a n o _ 2 ( C ) : -

n o d o s ( L ) ,

l e n g t h ( L , N ) ,

l e n g t h ( C , N ) ,

c a m i n o ( _ , _ , C ) .

Comparacin de eficiencia

? - t i m e ( f i n d a l l ( _ C , h a m i l t o n i a n o _ 1 ( _ C ) , _ L ) ) .

3 7 , 0 3 3 i n f e r e n c e s i n 0 . 0 3 s e c o n d s ( 1 2 3 4 4 3 3 L i p s )

? - t i m e ( f i n d a l l ( _ C , h a m i l t o n i a n o _ 2 ( _ C ) , _ L ) ) .

1 3 , 0 3 0 i n f e r e n c e s i n 0 . 0 1 s e c o n d s ( 1 3 0 3 0 0 0 L i p s )

41 / 41



77/262

Captulo 4

Resolucin de problemas de espacios de

estados

77


78/262

PD Tema 4: Resolucin de problemas de espacios de estados

Programacin lgica (200809)Tema 4: Resolucin de problemas de espacios de estados




1 / 48


1. Ejemplo de problema de espacios de estados: El 8puzzle

2. Procedimientos de bsqueda en espacios de estados

2 / 48

78 Captulo 4. Resolucin de problemas de espacios de estados


79/262


Ejemplo de problema de espacios de estados: El 8puzzle

Enunciado del problema del 8puzzle

Para el 8puzzle se usa un cajn cuadrado en el que hay situados 8bloques cuadrados. El cuadrado restante est sin rellenar. Cadabloque tiene un nmero. Un bloque adyacente al hueco puededeslizarse hacia l. El juego consiste en transformar la posicin inicialen la posicin final mediante el deslizamiento de los bloques. Enparticular, consideramos el estado inicial y final siguientes:

3 / 48



Desarrollo del problema del 8puzzle

4 / 48



80/262



Solucin del problema del 8puzzle

5 / 48



Especificacin del problema del 8puzzle

Estado inicial: [[2,8,3],[1,6,4],[7,h,5]] Estado final: [[1,2,3],[8,h,4],[7,6,5]] Operadores:

Mover el hueco a la izquierda Mover el hueco arriba Mover el hueco a la derecha Mover el hueco abajo

Nmero de estados = 9! = 362.880.

6 / 48



81/262


Procedimientos de bsqueda en espacios de estados

Bsqueda en profundidad sin ciclos

Tema 4: Resolucin de problemas de espacios de estados1. Ejemplo de problema de espacios de estados: El 8puzzle2. Procedimientos de bsqueda en espacios de estados

Bsqueda en profundidad sin ciclosEl problema del rbol

Procedimiento de bsqueda en profundidad sin ciclos

El problema de las 4 reinas

Bsqueda en profundidad con ciclosProblema del grafo con ciclos

El procedimiento de bsqueda en profundidad con ciclosEl problema de las jarras

Bsqueda en anchuraEl problema del paseo

El procedimiento de bsqueda en anchura

Bsqueda ptimaEl problema del viaje

El procedimiento de bsqueda ptima

2o procedimiento de bsqueda ptima

7 / 48




Enunciado del problema del rbol

rbol

a

/ \

b c

/ \ / \

d e f g/ / \ \

h i j k

Estado inicial: a Estados finales: f y j

8 / 48



82/262




Representacin del problema del rbol

Representacin arbol.pl estado_inicial(?E) se verifica si E es el estado inicial.

e s t a d o _ i n i c i a l ( a ) .

estado_final(?E) se verifica si E es un estado final.

e s t a d o _ f i n a l ( f ) .

e s t a d o _ f i n a l ( j ) .

sucesor(+E1,?E2) se verifica si E2 es un sucesor del estado E1.

s u c e s o r ( a , b ) . s u c e s o r ( a , c ) . s u c e s o r ( b , d ) .

s u c e s o r ( b , e ) . s u c e s o r ( c , f ) . s u c e s o r ( c , g ) .

s u c e s o r ( d , h ) . s u c e s o r ( e , i ) . s u c e s o r ( e , j ) .

s u c e s o r ( f , k ) .

9 / 48




Solucin del problema del rbol

profundidad_sin_ciclos(?S) se verifica si S es una solucindel problema mediante bsqueda en profundidad sin ciclos. Porejemplo,

? - [ a r b o l ] .

? - p r o f u n d i d a d _ s i n _ c i c l o s ( S ) .

S = [ a , b , e , j ]

? - t r a c e ( e s t a d o _ f i n a l , + c a l l ) , p r o f u n d i d a d _ s i n _ c i c l o s ( S ) .

T C a l l : ( 9 ) e s t a d o _ f i n a l ( a )

T C a l l : ( 1 0 ) e s t a d o _ f i n a l ( b )

T C a l l : ( 1 1 ) e s t a d o _ f i n a l ( d )

T C a l l : ( 1 2 ) e s t a d o _ f i n a l ( h )

T C a l l : ( 1 1 ) e s t a d o _ f i n a l ( e )

T C a l l : ( 1 2 ) e s t a d o _ f i n a l ( i )

T C a l l : ( 1 2 ) e s t a d o _ f i n a l ( j )

S = [ a , b , e , j ]

? - n o d e b u g .

10 / 48



83/262





p r o f u n d i d a d _ s i n _ c i c l o s ( S ) : -

e s t a d o _ i n i c i a l ( E ) ,

p r o f u n d i d a d _ s i n _ c i c l o s ( E , S ) .

p r o f u n d i d a d _ s i n _ c i c l o s ( E , [ E ] ) : -

e s t a d o _ f i n a l ( E ) .

p r o f u n d i d a d _ s i n _ c i c l o s ( E , [ E | S 1 ] ) : -

s u c e s o r ( E , E 1 ) ,

p r o f u n d i d a d _ s i n _ c i c l o s ( E 1 , S 1 ) .

11 / 48





Enunciado: Colocar 4 reinas en un tablero rectangular dedimensiones 4 por 4 de forma que no se encuentren ms de unaen la misma lnea: horizontal, vertical o diagonal.

Estados: listas de nmeros que representa las ordenadas de lasreinas colocadas. Por ejemplo, [3,1] representa que se ha

colocado las reinas (1,1) y (2,3).

12 / 48



84/262




Solucin del problema de las 4 reinas por bsqueda enprofundidad sin ciclos

Soluciones:

? - [ ' 4 - r e i n a s ' , ' b - p r o f u n d i d a d - s i n - c i c l o s ' ] .

Y e s

? - p r o f u n d i d a d _ s i n _ c i c l o s ( S ) .

S = [ [ ] , [ 2 ] , [ 4 , 2 ] , [ 1 , 4 , 2 ] , [ 3 , 1 , 4 , 2 ] ] ;

S = [ [ ] , [ 3 ] , [ 1 , 3 ] , [ 4 , 1 , 3 ] , [ 2 , 4 , 1 , 3 ] ] ;

N o

13 / 48




Representacin del problema de las 4 reinas

4-reinas.pl

estado_inicial(?E) se verifica si E es el estado inicial.

e s t a d o _ i n i c i a l ( [ ] ) .


e s t a d o _ f i n a l ( E ) : -

l e n g t h ( E , 4 ) .


s u c e s o r ( E , [ Y | E ] ) : -

m e m b e r ( Y , [ 1 , 2 , 3 , 4 ] ) ,

n o t ( m e m b e r ( Y , E ) ) ,

n o _ a t a c a ( Y , E ) .

14 / 48



85/262




Representacin del problema de las 4 reinas

no_ataca(Y,E) se verifica si E=[Yn,...,Y1], entonces la reinacolocada en (n+1,Y) no ataca a las colocadas en (1,Y1), . . . ,(n,Yn).

n o _ a t a c a ( Y , E ) : -

n o _ a t a c a ( Y , E , 1 ) .

n o _ a t a c a ( _ , [ ] , _ ) .

n o _ a t a c a ( Y , [ Y 1 | L ] , D ) : -

Y 1 - Y = \ = D ,

Y - Y 1 = \ = D ,

D 1 i s D + 1 ,

n o _ a t a c a ( Y , L , D 1 ) .

15 / 48



Bsqueda en profundidad con ciclos

Tema 4: Resolucin de problemas de espacios de estados1. Ejemplo de problema de espacios de estados: El 8puzzle2. Procedimientos de bsqueda en espacios de estados

Bsqueda en profundidad sin ciclosEl problema del rbol



Bsqueda en profundidad con ciclosProblema del grafo con ciclos

El procedimiento de bsqueda en profundidad con ciclos

El problema de las jarras

Bsqueda en anchuraEl problema del paseo

El procedimiento de bsqueda en anchura

Bsqueda ptimaEl problema del viaje

El procedimiento de bsqueda ptima

2o procedimiento de bsqueda ptima

16 / 48



86/262




Enunciado del problema de grafo con ciclos

a

/ \

b c

/ \ / \

d e f g

// / \ \

h i j k

Estado inicial: a Estados finales: f y j

Nota: el arco entre d y h es bidireccional

17 / 48




Representacin del problema de grafo con ciclos

grafo.pl

estado_inicial(?E) se verifica si E es el estado inicial.

e s t a d o _ i n i c i a l ( a ) .


e s t a d o _ f i n a l ( f ) .

e s t a d o _ f i n a l ( j ) .


s u c e s o r ( a , b ) . s u c e s o r ( a , c ) . s u c e s o r ( b , d ) .

s u c e s o r ( b , e ) . s u c e s o r ( c , f ) . s u c e s o r ( c , g ) .

s u c e s o r ( d , h ) . s u c e s o r ( e , i ) . s u c e s o r ( e , j ) .

s u c e s o r ( f , k ) . s u c e s o r ( h , d ) .

18 / 48



87/262




Solucin del problema de grafo con ciclos

Solucin por bsqueda en profundidad con ciclos:? - [ ' g r a f o ' , ' b - p r o f u n d i d a d - s i n - c i c l o s ' ] .

? - t r a c e ( e s t a d o _ f i n a l , + c a l l ) , p r o f u n d i d a d _ s i n _ c i c l o s ( S ) .

T C a l l : ( 1 0 ) e s t a d o _ f i n a l ( a )






. . . .

? - [ ' b - p r o f u n d i d a d - c o n - c i c l o s ' ] .

? - p r o f u n d i d a d _ c o n _ c i c l o s ( S ) .

S = [ a , b , e , j ] ;

S = [ a , c , f ] ;

N o

19 / 48




Solucin del problema de grafo con ciclos

? - t r a c e ( e s t a d o _ f i n a l , + c a l l ) , p r o f u n d i d a d _ c o n _ c i c l o s ( S ) .

T C a l l : ( 1 0 ) e s t a d o _ f i n a l ( a )




T C a l l : ( 1 2 ) e s t a d o _ f i n a l ( e )

T C a l l : ( 1 3 ) e s t a d o _ f i n a l ( i )

T C a l l : ( 1 3 ) e s t a d o _ f i n a l ( j )

S = [ a , b , e , j ] ;

T C a l l : ( 1 1 ) e s t a d o _ f i n a l ( c )

T C a l l : ( 1 2 ) e s t a d o _ f i n a l ( f )

S = [ a , c , f ] ;

T C a l l : ( 1 3 ) e s t a d o _ f i n a l ( k )

T C a l l : ( 1 2 ) e s t a d o _ f i n a l ( g )

N o 20 / 48



88/262




Procedimiento de bsqueda en profundidad con ciclos

(b-profundidad-con-ciclos.pl)

Un nodo es una lista de estados [En, . . . , E1] de forma que E1 esel estado inicial y Ei+1 es un sucesor de Ei.

profundidad_con_ciclos(?S) se verifica si S es una solucindel problema mediante bsqueda en profundidad con ciclos.

p r o f u n d i d a d _ c o n _ c i c l o s ( S ) : -

e s t a d o _ i n i c i a l ( E ) ,

p r o f u n d i d a d _ c o n _ c i c l o s ( [ E ] , S ) .

21 / 48



temas programacion logica ia

Documents