Semestre 2014-212/09/2014

Tema:

Recursividad en Prolog

Ing. José Espinal

FACULTAD DE INGENIERÍA

ESCUELA ACADEMICO PROFESIONAL DE INGENIERIA DE SISTEMAS

Inteligencia Artificial

INTRODUCCION

2

Inteligencia Artificial

RECURSIVIDAD

La Recursividad representa la estructura mas importante en el desarrollo del PROLOG. En la sintaxis del PROLOG, no existen los bucles ni los saltos, ya que las variables solo pueden unificarse una sola vez.La recursividad es el mecanismo de inferencia mas importante en el PROLOG es la función que se invoca a el mismo.

3

Inteligencia Artificial

EJEMPLO: CALCULAR FACTORIAL DE UN NUMERO

factorial(0, 1).factorial(N, M):- N1 is N - 1, factorial(N1, M1), M is N*M1.

Pregunta:? factorial(5,X).X=120

4

Inteligencia Artificial

Como lee PROLOG: 3! =1x2x3=6

F(0, 1).F(N, M):- N1 is N - 1, F(N1, M1), M is N*M1.

F(3, M) :- N1 is 3-1 , F(2 , M1) , M is 3 * M1.F(2, 2).

F(2, M) :- N1 is 2-1 , F(1, M1) , M is 2 * M1.F(1, 1).

F(1. M) :- N1 is 1-1 , F(0, M1) . M is 1 * M1.

F(0, 1). 5

BACKTRACKING

Inteligencia Artificial

APLICACIÓN CON GRAFOS

¿Existe una conexión entre A e I? Con qué nodos está conectado F y cuál es el costo de cada conexión. Construir una regla para determinar si un nodo tiene aristas. Construir una regla para determinar cual es el costo de ir de un nodo X a

un nodo Z pasando por Y.

6

D H

I

A

F G

B

C7

8

10

119

4

2

Inteligencia Artificial

APLICACIÓN CON GRAFOS

¿Existe una conexión entre A e I? Con qué nodos está conectado F y cuál es el costo de cada conexión. Construir una regla para determinar si un nodo tiene aristas. Construir una regla para determinar cual es el costo de ir de un nodo X a

un nodo Z pasando por Y.

7

D H

I

A

F G

B

C7

8

10

119

4

2

conexión(d , h , 4).conexión(h , f , 9).conexión(i , f , 11).conexión(f , g , 10).conexión(f , a , 8).conexión(a , b , 7).conexión(d , i , 2).

Inteligencia Artificial

APLICACIÓN CON GRAFOS

¿Existe una conexión entre A e I? Con qué nodos está conectado F y cuál es el costo de cada conexión. Construir una regla para determinar si un nodo tiene aristas. Construir una regla para determinar cual es el costo de ir de un nodo X a

un nodo Z pasando por Y.

8

D H

I

A

F G

B

C7

8

10

119

4

2

? Conexión (a, i , _ ).False

? Conexión (f, X, Costo).X=G,Costo=10;

X=A,Costo=8;

Inteligencia Artificial

APLICACIÓN CON GRAFOS

¿Existe una conexión entre A e I? Con qué nodos está conectado F y cuál es el costo de cada conexión. Construir una regla para determinar si un nodo tiene aristas. Construir una regla para determinar cual es el costo de ir de un nodo X a

un nodo Z pasando por Y.

9

D H

I

A

F G

B

C7

8

10

119

4

2

tieneArista(X):- conexión(X,_,_).

? tieneArista(a).True

Inteligencia Artificial

APLICACIÓN CON GRAFOS

¿Existe una conexión entre A e I? Con qué nodos está conectado F y cuál es el costo de cada conexión. Construir una regla para determinar si un nodo tiene aristas. Construir una regla para determinar cual es el costo de ir de un nodo X a

un nodo Z pasando por Y.

10

D H

I

A

F G

B

C7

8

10

119

4

2

Llegar(Inicio,Destino,Int,Costo) :- Conexión(Inicio,Int,C1), conexión(Int,Destino,C2),Costo is C1 + C2.

? Llegar (d, f, i, X).X=13

Inteligencia Artificial

RECURSIVIDAD

Como saber si existe un camino entre dos nodos

11

D H

I

A

F G

B

C7

8

10

119

4

2

Inteligencia Artificial

RECURSIVIDAD

Como saber si existe un camino entre dos nodos

12

D H

I

A

F G

B

C7

8

10

119

4

2

CAMINO(X,Y) :- CONEXIÓN(X,Y).

CAMINO(X,Y) :- CONEXIÓN(X,Z), CAMINO(Z,Y).

RECURSIVIDAD

Inteligencia Artificial

APLICACIÓN DE RECURSIVIDAD

Como saber si existe un camino entre dos nodos

13

D H

I

A

F G

B

C7

8 10

119

4

2

Inteligencia Artificial

ACTIVIDAD

14

CALCULE LOS 14 PRIMEROS NUMEROS DE FIBONACCI. EXPLIQUE LOS NIVELES CON LA RECURSIVIDAD Y EL BACKTRACKING

CODIFIQUE EN SWI-PROLOG TODOS LOS CASOS DEL GRAFO ANTERIORY COMPRUEBE.

1

2

Inteligencia Artificial

GRACIAS