Aplicaciones actuales del Lenguaje PROLOG

TRANSPARENCIAS TEMA 4

Inteligencia Artificial (OCHO REINAS)

ANALOGÍA

COMPILADORES

Miscelánea

Bibliografía

Aplicaciones actuales del Lenguaje PROLOG

Prolog se puede utilizar para resolver, básicamente, cualquier tipo de problema.

Principalmente es útil en la gestión de Juegos, en Inteligencia Artificial y Sistemas Expertos, como lenguaje especialmente pensado para construir bases de conocimientos basados en la lógica que forman parte importante de cualquier agente inteligente, en la construcción de Compiladores e Intérpretes, en el Reconocimiento del Lenguaje Natural, etc.

[Índice]

Inteligencia Artificial

PROBLEMA DE LAS OCHO REINAS

Problema NP-Completo que no tiene solución para N=2 y N=3. Para N=4 tiene una única solución. Para N=8 hay más de 80 soluciones dependiendo de las restricciones que se impongan.

En Prolog: reinas(N, Solucion), donde N representa las dimensiones del tablero y el número de reinas y Solucion es una lista que contiene la permutación de la lista de números que resuelven el problema. Los índices de dicha lista representan la columna en la que se encuentra una reina y el número que almacena la posición o índice representa la fila donde la reina está colocada. Así, para el ejemplo mostrado, tenemos que R=[2,4,1,3].

domains

lista=integer*

predicates

rango(integer, integer, lista)

nondeterm dame(integer, lista, lista)

nondeterm permuta(lista, lista)

atacada(integer, integer, lista)

correcta(lista)

nondeterm reina(integer, lista)

clauses

rango(N, N, [N]):-!.

rango(N, M, [N|Cola]):-N<M, Aux=N+1, rango(Aux, M, Cola).

dame(X,[X|Xs],Xs).

dame(X,[Y|Ys],[Y|Zs]):-dame(X,Ys,Zs).

permuta([],[]).

permuta(L,[Z|Zs]):-dame(Z,L,Ys), permuta(Ys,Zs).

atacada(X,N,[Y|Ys]):-X=Y+N, !; X=Y-N, !.

atacada(X,N,[_|Ys]):-N1=N+1, atacada(X,N1,Ys).

correcta([]):-!.

correcta([X|Y]):-correcta(Y), not (atacada(X, 1, Y)).

reina(N, Solucion):-rango(1,N,L1), permuta(L1,Solucion), correcta(Solucion).

goal

write("Tamaño tablero = "), readint(N),

nl,

write("Soluciones: "), nl,

reina(N, Solucion),

write(Solucion),nl, fail.

Para N, obtenemos una lista de números comprendidos entre 1 y N: [1,2,3,4,...,N].

Obtenemos una permutación del conjunto de números de la lista.

Comprobamos que la permutación es correcta.

Si la permutación no es correcta, lo que debemos hacer es volver al paso 2 para generar una permutación nueva.

[Índice]

ANALOGÍA

SOLUCIÓN

A debe ser el inverso de B.

Eso implica que debemos calcular el inverso de C.

Si el inverso de C está en la lista de respuestas, hemos encontrado la respuesta.

En caso contrario, volvemos al paso 2 para encontrar otra solución.

domains

disposicion= dentro(symbol, symbol);

fuera(symbol, symbol)

lista=disposicion*

test=determ (integer, disposicion) - (i, o)

predicates

figuras(integer, disposicion, disposicion, disposicion)

respuestas(integer, lista)

esta(disposicion, lista)

casar(disposicion, disposicion)

analogia(disposicion, disposicion, disposicion, disposicion, lista)

test_analogia: test

clauses

figuras(1, dentro(cuadro, triangulo), dentro(triangulo, cuadro), dentro(circulo, cuadro)):-!.

figuras(2, dentro(cuadro, triangulo), dentro(triangulo, cuadro), dentro(circulo, cuadro)).

respuestas(1, [dentro(circulo, triangulo), dentro(cuadro, circulo), dentro(triangulo, cuadro)]):-!.

respuestas(2, [dentro(circulo, triangulo), dentro(circulo, cuadro), dentro(triangulo, cuadro)]).

esta(X, [X|_]):-!.

esta(X, [_|Y]):-esta(X,Y).

casar(dentro(F1, F2), dentro(F2, F1)):-!.

casar(fuera(F1, F2), fuera(F2, F1)).

analogia(A, B, C, X, Respuestas):-casar(A, B),

casar(C, X),

esta(X, Respuestas).

test_analogia(Numero, X):-figuras(Numero, A, B, C),

respuestas(Numero, Respuestas),

analogia(A, B, C, X, Respuestas).

goal

write("Dame número de test: [1,2]: "),

readint(N),

test_analogia(N, X),

write(X).

analogia(es_a(A, B), como_es_a(C, X), Respuestas):-casar(A, B),

casar(C, X),

esta(X, Respuestas).

[Índice]

COMPILADORES

domains

lista=char*

predicates

inicial(symbol)

final(symbol)

delta(symbol, char, symbol)

aceptar(lista, symbol)

acepto(lista)

clauses

inicial(q0).

final(q0).

delta(q0, 'a', q1).

delta(q1, 'b', q0).

acepto(L):-inicial(Q), aceptar(L,Q).

aceptar([X|Y], Q):-delta(Q, X, Q1), aceptar(Y, Q1).

aceptar([],Q):-final(Q).

goal

write("Dame lista de símbolos: "), readterm(lista, L),

acepto(L),

nl,

write("Pertenece al lenguaje").

[Índice]

Miscelánea

TORRES DE HANOI

El problema de las torres de Hanoi consiste en mover un conjunto de discos de un palo a otro palo utilizando un palo auxiliar situado en medio. Las reglas para mover los discos son las siguientes:

No se puede mover más de un disco en cada ocasión.

No puede quedar un disco de menor radio debajo de un disco de mayor radio.

Mover el conjunto de discos se puede ver como: mover N-1 discos del palo izquierdo al palo del medio, mover el disco sobrante del palo izquierdo al palo derecho y mover N-1 discos del palo del medio al palo derecho.

Pseudocódigo:

hanoi(N)<-mover(N,izquierda,medio,derecha).

mover(1,A,_,C)<-Pasar disco de A a C.

mover(N,A,B,C)<-mover(N-1,A,C,B), mover(1,A,C), mover(N-1,B,A,C).

[Índice]

Bibliografía

[Russell, 1996]

Russell, Stuart. Norvig, Peter. "Inteligencia Artificial. Un enfoque moderno". Editorial Prentice Hall. 1996.

[Shapiro, 1986]

E. Shapiro y L. Sterling. "The art of Prolog". The MIT Press, 1986

[Índice]