FACULTAD DE CIENCIAS INFORMTICAS
QUINTO SEMESTRE INFORMTICA
TEMA:
AND/OR representacin grfica de los problemas
AUTORES:
MEDINA GONZALEZ JORGE ANDRES
VILLACRESES LUCAS JEFFRI
CEDEO CEDEO BRYAN ALEXANDER
DOCENTE:
ING. FABRICIO RIVADENEIRA
MANTA ECUADOR
2014 - 2015
Introduccin
Prolog es un lenguaje de programacin hecho para representar y utilizar el conocimiento
que se tiene sobre un determinado dominio. Ms exactamente, el dominio es un conjunto de
objetos y el conocimiento se representa por un conjunto de relaciones que describen las
propiedades de los objetos y sus interrelaciones. Un conjunto de reglas que describa estas
propiedades y estas relaciones es un programa Prolog.
Prolog es un lenguaje de programacin que es usado para resolver problemas que
envuelven objetos y las relaciones entre ellos.
Hechos
Expresan relaciones entre objetos. Supongamos que queremos expresar el hecho de que "un
coche tiene ruedas". Este hecho, consta de dos objetos, "coche" y "ruedas", y de una
relacin llamada "tiene". La forma de representarlo en PROLOG es:
tiene(coche,ruedas).
* Los nombres de objetos y relaciones deben comenzar con una letra
minscula.
* Primero se escribe la relacin, y luego los objetos separados por
comas y encerrados entre parntesis.
Al final de un hecho debe ir un punto (el carcter ".").
El orden de los objetos dentro de la relacin es arbitrario, pero debemos
ser coherentes a lo largo de la base de hechos.
Variables
Representan objetos que el mismo PROLOG determina. Una variable puede estar
instanciada o no instanciada. Esta instanciada cuando existe un objeto determinado
representado por la variable. De este modo, cuando preguntamos "Un coche tiene X ?",
PROLOG busca en los hechos cosas que tiene un coche y respondera:
X = ruedas.
instanciando la variable X con el objeto ruedas.
* Los nombres de variables comienzan siempre por una letra mayscula.
Un caso particular es la variable annima, representada por el carcter subrayado ("_"). Es
una especie de comodn que utilizaremos en aquellos lugares que debera aparecer una
variable, pero no nos interesa darle un nombre concreto ya que no vamos a utilizarla
posteriormente.
Reglas
Las reglas se utilizan en PROLOG para significar que un hecho depende de uno o ms
hechos. Son la representacin de las implicaciones lgicas del tipo p ---> q (p implica q).
* Una regla consiste en una cabeza y un cuerpo, unidos por el signo ":-".
* La cabeza esta formada por un nico hecho.
* El cuerpo puede ser uno o ms hechos (conjuncin de hechos), separados
por una coma (","), que acta como el "y" lgico.
* Las reglas finalizan con un punto (".").
La cabeza en una regla PROLOG corresponde al consecuente de una implicacin lgica, y
el cuerpo al antecedente. Este hecho puede conducir a errores de representacin.
Supongamos el siguiente razonamiento lgico:
tiempo(lluvioso) ----> suelo(mojado)
suelo(mojado)
Que el suelo esta mojado, es una condicin suficiente de que el tiempo
sea lluvioso, pero no necesaria. Por lo tanto, a partir de ese hecho, no
podemos deducir mediante la implicacin, que esta lloviendo (pueden haber
regado las calles). La representacin *correcta* en PROLOG, sera:
suelo(mojado) :- tiempo(lluvioso).
suelo(mojado).
Cabe sealar que la regla esta "al revs". Esto es as por el mecanismo
de deduccin hacia atrs que emplea PROLOG. Si cometiramos el *error* de
representarla como:
tiempo(lluvioso) :- suelo(mojado).
suelo(mojado).
PROLOG, partiendo del hecho de que el suelo esta mojado, deducira
incorrectamente que el tiempo es lluvioso.
Para generalizar una relacin entre objetos mediante una regla,
utilizaremos variables. Por ejemplo:
Representacin lgica | Representacin PROLOG
Es un coche(X) ----> | tiene(X,ruedas) :
tiene(X,ruedas) | es un coche(X).
Con esta regla generalizamos el hecho de que cualquier objeto que sea un coche, tendr
ruedas. Al igual que antes, el hecho de que un objeto tenga ruedas, no es una condicin
suficiente de que sea un coche. Por lo tanto la representacin inversa sera incorrecta.
El mbito de las variables.
Cuando en una regla aparece una variable, el mbito de esa variable es
nicamente esa regla. Supongamos las siguientes reglas:
(1) hermana_de(X,Y) :- hembra(X), padres(X,M,P), padres(Y,M,P).
(2) puede_robar(X,P) :- ladron(X), le_gusta_a(X,P), valioso(P).
Aunque en ambas aparece la variable X (y la variable P), no tiene nada que ver la X de la
regla (1) con la de la regla (2), y por lo tanto, la instanciacin de la X en (1) no implica la
instanciacin en (2). Sin embargo todas las X de *una misma regla* si que se instanciaran
con el mismo valor.
Operadores
Son predicados predefinidos en PROLOG para las operaciones matemticas bsicas. Su
sintaxis depende de la posicin que ocupen, pudiendo ser infijos o prefijos. Por ejemplo el
operador suma ("+"), podemos encontrarlo en forma prefija '+(2,5)' o bien infija, '2 + 5'.
Tambin dispone de predicados de igualdad y desigualdad.
X = Y igual
X \= Y distinto
X < Y menor
X > Y mayor
X =< Y menor o igual
X >= Y mayor o igual
Al igual que en otros lenguajes de programacin es necesario tener en cuenta la precedencia
y la asociatividad de los operadores antes de trabajar con ellos.
En cuanto a precedencia, es la tpica. Por ejemplo, 3+2*6 se evala como 3+(2*6). En lo
referente a la asociatividad, PROLOG es asociativo por la izquierda. As, 8/4/4 se interpreta
como (8/4)/4. De igual forma, 5+8/2/2 significa 5+((8/2)/2).
El operador 'is'.
Es un operador infijo, que en su parte derecha lleva un termino que se interpreta como una
expresin aritmtica, contrastndose con el termino de su izquierda.
Por ejemplo, la expresin '6 is 4+3.' es falsa. Por otra parte, si la expresin es 'X is 4+3.', el
resultado ser la instanciacin de X:
X = 7
Una regla PROLOG puede ser esta:
densidad(X,Y) :- poblacin(X,P), rea(X,A), Y is P/A.
Algunos comandos bsicos
* consult.
El predicado _consult_ esta pensado para leer y compilar un programa PROLOG o bien
para las situaciones en las que se precise aadir las clusulas existentes en un determinado
fichero a las que ya estn almacenadas y compiladas en la base de datos. Su sintaxis puede
ser una de las siguientes:
consult(fichero).
consult('[Link]').
consult('c:\ia\prolog\fichero').
* recon.
El predicado recon es muy parecido a consult, con la salvedad de que las clusulas
existentes en el fichero consultado, reemplazan a las existentes en la base de hechos. Puede
ser til para sustituir una nica clusula sin consultar todas las dems, situando esa clusula
en un fichero. Su sintaxis es la misma que la de consult.
*forget.
Tiene como fin eliminar de la base de datos actual aquellos
hechos consultados de un fichero determinado. Su sintaxis es:
forget(fichero).
* exitsys.
Este predicado nos devuelve al sistema operativo.
La resolucin de objetivos
Ya hemos creado un programa PROLOG [[Link]] y lo hemos compilado
en nuestro interprete PROLOG [consult(relacion)]. A partir de este
momento podemos interrogar la base de datos, mediante consultas.
Una consulta tiene la misma forma que un hecho.
Consideremos la pregunta:
?-quiere_a(susana,pablo).
PROLOG buscara por toda la base de datos hechos que coincidan con el anterior. Dos
hechos coinciden si sus predicados son iguales, y cada uno de sus correspondientes
argumentos lo son entre si. Si PROLOG encuentra un hecho que coincida con la pregunta,
responder yes. En caso contrario responder no.
Adems, una pregunta puede contener variables. En este caso PROLOG buscara por toda la
base de hechos aquellos objetos que pueden ser representado por la variable. Por ejemplo:
?-quiere_a(maria, Alguien).
El resultado de la consulta es:
Alguien = enrique
More (Y/N):
El hecho 'quiere_a(maria,enrique).' coincide con la pregunta al instanciar la variable
Alguien con el objeto 'enrique'. Por lo tanto es una respuesta valida, pero no la nica. Por
eso se nos pregunta si queremos obtener m s respuestas. En caso afirmativo, obtendramos:
Alguien = susana
More (Y/N):y
Alguien = ana
More (Y/N):y
No.
?-
Las consultas a una base de datos se complican cuando estas estn compuestas por
conjunciones o bien intervienen reglas en su resolucin. Conviene, por lo tanto, conocer
cual es el mecanismo de control del PROLOG, con el fin de comprender el porque de sus
respuestas.
8. El mecanismo de control de PROLOG
El mecanismo empleado por PROLOG para satisfacer las cuestiones que se le plantean, es
el de _razonamiento hacia atrs (backward) complementado con la bsqueda en
profundidad (depth first) y la vuelta atrs o reevaluacin (backtracking).
Razonamiento hacia atrs: Partiendo de un objetivo a probar, busca las aserciones que
pueden probar el objetivo. Si en un punto caben varios caminos, se recorren en el orden que
aparecen en el programa, esto es, de arriba a abajo y de izquierda a derecha.
Reevaluacin: Si en un momento dado una variable se instancia con determinado valor con
el fin de alcanzar una solucin, y se llega a un camino no satisfactorio, el mecanismo de
control retrocede al punto en el cual se instanci la variable, la des-instancia y si es posible,
Busca otra instanciacin que supondr un nuevo camino de bsqueda.
AND/OR representacin grfica de los problemas
En los captulos 11 y 12, la resolucin de problemas se centra en torno a la representacin
en espacio de estado de los problemas. En consecuencia, la resolucin de problemas se
reduce a encontrar un camino en un grfico de espacio de estado. Otra representacin, l y /
o representacin grfica, se adapte de forma ms natural a ciertas categoras de problemas.
Esta representacin se basa en la descomposicin de problemas en subproblemas
Descomposicin en subproblemas es ventajosa, si los subproblemas son mutuamente
independientes, y por lo tanto puede ser resuelto de forma independiente el uno del otro.
En el mapa de la Figura 13.1, tambin hay un ro. Supongamos que hay son slo dos
puentes en el que el ro se puede cruzar, un puente en la ciudad y / la otra en la ciudad de g.
Obviamente, nuestra ruta deber incluir uno de los puentes; por lo que tendr que ir a travs
de / oa travs de g. Tenemos, entonces, dos grandes alternativas:
Para encontrar un camino entre A y Z, encontrar,
(1) una trayectoria de C a Z a travs de F, o
(2) un camino de C a travs de z g.
Cada uno de estos dos problemas alternativos ahora se puede descomponer de la siguiente
manera:
(1) Para encontrar un camino de A a Z a travs de f:
1.1 encontramos un camino de A a F, y
1.2 encontrar un camino de f a z
(2) Para encontrar un camino de A a Z a travs de g:
2.1. Encontrar un camino de A a G y
2.2 encontramos un camino de g a z.
La figura 13.4 ilustra esta definicin. En esta figura, hay costes asociados a los arcos. El
uso de los costos que puede formular un criterio de optimizacin. Podemos, por ejemplo,
definir el costo de un grfico de la solucin como la suma de todos los costes en los arcos
en el grafo "Como somos normalmente interesado en el costo mnimo, se preferir la
grfica solucin en la figura 13.a (c).
13.2.2 La Torre de Hanoi problema
La Torre de Hanoi problema, que se muestra en la Figura 13.6, es otro, clsica ejemplo de
aplicacin efectiva de la Y / O esquema de descomposicin. Para simplicidad,
consideraremos una versin simple de este problema, que contiene tres discos solamente:
Hay tres clavijas, 1, 2 y3, y tres discos, a, b y c (siendo a la c ms pequeo y ser el
ms grande). Inicialmente, todos los discos se apilan en PEG 1. El problema es
transferir todos ellos a clavija 3. Slo uno de los discos se puede mover a la vez, y
ningn disco nunca se puede colocar en la parte superior de un disco ms pequeo.
Este problema puede ser visto como el problema de lograr el siguiente conjunto de los
objetivos:
(1) Disco A en paridad 3.
(2) Disco b en paridad 3.
(3) Disco c en la clavija 3.
Estos objetivos son, por desgracia, no es independiente. Por ejemplo, un disco de inmediato
se puede colocar en la clavija 3, satisfaciendo el primer gol. Esto, sin embargo, impedir el
cumplimiento de los otros dos goles (a menos que nos deshacemos el primer gol de nuevo).
Afortunadamente, hay un orden conveniente de estos objetivos de manera que una solucin
se puede derivar fcilmente de este orden. El pedido se puede encontrar el siguiente
razonamiento: objetivo 3 (disco c en paridad 3) es el ms difcil porque se mueve el disco c
est sujeto a la mayora de las restricciones. Una buena idea que a menudo trabaja en este
tipo de situaciones es: tratar de lograr el objetivo ms difcil primero. La lgica detrs de
este principio es: como otros objetivos son ms fciles (no es tan limitada como la ms
dura) que con suerte se puede lograr sin necesidad de deshacer esta meta ms difcil.
La estrategia de resolucin de problemas que se deriva de este principio en nuestra tarea es:
En primer lugar satisfacer la meta 'disco c en paridad 3 "
A continuacin, satisfacer los objetivos restantes.
Pero el primer objetivo no puede ser alcanzado de inmediato: disco c no se puede mover en
la situacin inicial. Por lo tanto, lo primero que tenemos que preparar este movimiento y
nuestra estrategia se refina para:
(1) Activar movimiento de disco C de 1 a 3.
(2) Mueva el disco C de 1 a 3.
(3) Alcanzar las metas por alcanzar: un da 3, y b en 3.
Disco C slo puede moverse de 1 a 3 si tanto A como B se apilan en PEG 2. Entonces,
nuestro problema inicial de movimiento A, B y C a partir de PEG que al PEG 3 se reduce a
tres subproblemas:
Para mover A, B y C de 1 a 3:
(1) se mueven a y b desde 1 hasta 2, y
(2) se mueven C de 1 a 3, y
(3) mover a y b desde 2 a 3.
Problema 2 es trivial (solucin de un solo paso). Los otros dos subproblemas pueden ser
resueltos de forma independiente de 2 problema porque los discos A y B se pueden mover
independientemente de la posicin del disco c. Para resolver los problemas 1 y 3, el mismo
principio se puede aplicar la descomposicin (disco b es el ms duro esta vez). En
consecuencia, el problema 1 se reduce a tres subproblemas triviales:
Para mover a y b 1-2:
(1) mover una de 1 a 3, y
(2) se mueven b desde 1 a 2, y
(3) mover una de 3 a 2.
Ejercicio de Aplicacin
