Prolog Ejercicio 4: El Mono y la Banana (Solución de Problemas)

El problema del mono y la banana se utiliza como un ejemplo sencillo de solución de problemas. El siguiente programa en Prolog mostrará como se pueden utilizar los mecanismos de 'matching' y 'backtracking'.

Utilizaremos la siguiente versión del problema:

1. Existe un mono en la puerta de un cuarto.
2. Enmedio del cuarto cuelga una banana del techo.
3. El mono está hambriento y desea capturar la banana pero no puede alcanzarla desde el piso.
4. En la ventana del cuarto hay una caja que el mono puede usar.

El mono puede realizar solamente las siguientes acciones:

1. Caminar sobre el piso
2. Subir a la caja
3. Empujar la caja (Si el mono está junto a la caja)
4. Agarrar la banana (Si el mono está sobre la caja y bajo la banana).

¿Cómo puede el mono llegar a capturar la banana?

Análisis del problema.

Una tarea importante en programación es encontrar una representación del problema en términos del lenguaje de programación utilizado.
En este caso podemos pensar del 'mundo del mono' en términos de 'estados' que cambian con el tiempo. El estado actual se determina por la posición actual de los objetos.

Por ejemplo, el estado inicial del mundo está determinado por:

1). El mono está en la puerta.
2). El mono está sobre el piso.
3). La caja está en la ventana.
4). El mono no tiene la banana.

El estado final es una situación en que el mono tiene la banana, es decir, cualquier estado en cuyo componente último sea : estado( _, _, _, silatiene)

Las transiciones permitidas que cambian el mundo de un estado a otro son
las siguientes :
Agarrar la banana.
Subir a la caja.
Empujar la caja.
Caminar en el cuarto.

No todas las transiciones son posibles en cada estado posible del mundo del mono. Por ejemplo, la transición 'agarrar la banana' es solamente posible si el mono está sobre la caja y bajo la banana y si no tiene todavía la banana. Estas transiciones ó reglas se pueden formalizar en Prolog como una relación de tres componentes que llamaremos 'mover':

mover( Estado1, M, Estado2) 

Los tres argumentos de la relación especifican un movimiento tal que:
Estado1 ----- M -----> Estado2

'Estado1' es el estado antes del movimiento 'M'; 'M' es el movimiento realizado, y 'Estado2' es el estado del mundo del mono después de haberse realizado el movimiento 'M'.

Podemos expresar el hecho de que el mono estando sobre el piso puede caminar de la posición P1 a cualquier posición P2. El mono puede realizar esta acción sin importar la posición de la caja y si tiene ó no la banana:

          mover( estado( P1, sobreelpiso, B, H),
          caminar( P1, P2 ),
          estado( P2, sobreelpiso, B, H)).

El programa completo es el siguiente:

Consideremos la siguiente pregunta al programa anterior:
?- puedetener( estado( enlapuerta,sobreelpiso,enlaventana,nolatiene)).
Prolog contestará: 'yes'.

El proceso llevado a cabo por Prolog para alcanzar ésta respuesta involucra una serie de búsquedas de movimientos válidos entre una serie de movimientos alternativos posibles. En algún punto de la búsqueda existirá un movimiento equivocado y válido que conducirá a una hoja del árbol de búsquedas, en tal situación, un proceso de 'backtracking' (vuelta atrás) se llevará a cabo para continuar con el proceso.

Árbol de búsqueda para el problema del mono y la banana. El proceso de backtracking se realiza una sola vez. Las búsquedas se realizan de arriba a abajo y de izquierda a derecha.

Fuente: Prolog.pdf (By. Edgar Altamirano C.)

Prolog Ejercicio 3: Significado Procedural

Significado Procedural de un Programa Prolog

El significado procedural especifica el cómo contesta Prolog a las preguntas. Responder a una pregunta significa tratar de satisfacer una lista de metas. Estas pueden satisfacerse si las variables que existen en las metas pueden instanciarse de tal modo que las metas se sigan lógicamente del programa. Así el significado procedural de Prolog es un procedimiento para ejecutar una lista de metas con respecto a un programa dado.  Ejecutar las metas significa tratar de satisfacerlas.

Las entradas y salidas a este procedimiento son:

• Entrada : Un programa y una lista de metas.
• Salida : Un indicador de éxito / falla y una instanciación particular de las variables.

El significado procedural determina cómo se vá a obtener esta salida, es decir, como evalúa Prolog sucesivamente las relaciones definidas en el programa.   Ejemplo.  En el siguiente ejemplo se hace una traza de la ejecución para ilustrar el significado procedural de Prolog :

Pregunta: 

Traza de la ejecución. Lista inicial de metas : oscuro(X), enorme(X). Examina el programa de arriba hacia abajo buscando una cláusula cuya cabeza empate con la primera meta : oscuro(X). Se encuentra la cláusula 7 : oscuro( Z) :- negro( Z).   Se reemplaza la primera meta con el cuerpo instanciado de la cláusula 7, dando una nueva lista de metas :  negro(X), enorme(X).  Examina el programa para encontrar un empatamiento de negro(X). Se encuentra la cláusula 5: negro( gato). Esta cláusula no tiene cuerpo, así que la lista de metas, luego de instanciarse se convierte en : enorme(gato).
Examina el programa para buscar la meta enorme(gato), no se encuentra ninguna cláusula. Por lo tanto se realiza un proceso de backtracking al paso 3) y se elimina la instanciación X = gato. Ahora la lista de metas es de nuevo:
negro(X), enorme(X).
Se continúa examinando el programa a partir de la cláusula 5. No se encuentra ninguna cláusula. Por lo tanto se realiza un proceso de backtracking nuevamente al paso (2) y se continúa examinando a partir de la cláusula 7. Se encuentra la cláusula 8:
oscuro(Z) :- cafe(Z).
Se reemplaza la primera meta en la lista de metas por cafe(X), dando:
cafe(X), enorme(X) Examina el programa buscando empatar cafe(X), encuentra cafe(oso). Esta cláusula no tiene cuerpo, así que la lista de metas es ahora: enorme(oso).
Examina el programa y encuentra la cláusula enorme(oso). Esta cláusula no tiene cuerpo, así que la lista de metas se queda vacía. Esto indica una terminación exitosa y la instanciación correspondiente a la variable queda como: X=oso.

Prolog Ejercicio 2: Significado Declarativo

 Significados de un programa Prolog

Los programas Prolog pueden entenderse de dos maneras: declarativa y proceduralmente. Considere la cláusula :          P :- Q, R.          donde P, Q y R tienen la sintaxis de términos.

Algunas interpretaciones declarativas de esta cláusula son :

• P es cierta si Q y R son ambas ciertas.
• De Q y R se sigue P.

Dos interpretaciones procedurales de la misma cláusula son :

• Para resolver el problema P, primero se resuelve el subproblema Q y entonces el subproblema R.
• Para satisfacer P, primero se debe satisfacer Q y entonces R.

Así, las diferencias entre el significado declarativo y procedural es de que en la segunda interpretación no solamente se definen las relaciones lógicas entre la cabeza de la cláusula y las metas en el cuerpo de la cláusula sino además el orden en que las metas deben procesarse.

Significado Declarativo

En un lenguaje declarativo puro, sería de esperar que el orden en el que aparecen los hechos y las reglas en la base fuera independiente de los datos, sin embargo en PROLOG no es así.

El significado declarativo tiene que ver sólo con las relaciones definidas por el programa. De esta manera, el significado declarativo determina cuál será la salida del programa.

La habilidad de PROLOG para calcular de forma procedural es una de las ventajas específicas que tiene el lenguaje. Como consecuencia esto anima al programador a considerar el significado declarativo de los programas de forma relativamente independiente de su significado procedural.

Es decir, las ventajas de la forma declarativa de este lenguaje son claras (es más fácil pensar las soluciones y muchos detalles procedurales son resueltos automáticamente por el propio lenguaje) y podemos aprovecharlas.

Los aspectos declarativos de los programas son, habitualmente, más fáciles de entender que los procedurales. Esta es la principal razón por la que el programador debe concentrarse en el significado declarativo y evitar distraerse por los detalles de cómo se ejecutan los programas.

Ejercicios.

1. Considere el siguiente programa:

¿Cómo contestará Prolog las siguientes preguntas? Cuando sean posibles varias respuestas, dé al menos dos de ellas.

(a). ?- f( s(1), A).
(b). ?- f( s(s(1)), dos).
(c). ?- f( s(s(s(s(s(s(1)))))), C).
(d). ?- f( D, tres).

Fuente: http://mural.uv.es/mijuanlo/PracticasPROLOG.pdf

Prolog Ejercicio 1: Árbol Familiar

¿Como crear un Árbol Genealógico en Prolog?

 Se debe escribir el código utilizando el siguiente formato y siguiendo las reglas que marca el software.
Para el ejemplo de arriba tendremos el siguiente código:

Ahora comenzaremos a realizar preguntas al programa siguiendo la sintaxis definida:

1.- ¿Quién es mi papá?
2.- ¿Quién es mi mamá?
3.- ¿Quién es mi abuelo?
4.- ¿Quién es mi abuela?
5.- ¿Quién es mi hermana?

1.- ¿Quién es mi tío?
2.- ¿Quién es mi tía?
3.- ¿Es hijo René de Darío?
4.- ¿Es hija Guillermina de Darío?
5.- ¿Es hermano René de Guillermina?
6.- ¿Es hermana Socorro de Cornelio?
7. -¿Quiénes son nuestros abuelos?

Podemos realizar más combinaciones de preguntas al Prolog utilizando éste código, lo dejaré por aquí para que hagan sus consultas, observen la sintaxis del programa y les pueda servir de algo.
__________________________________________________________________________________

__________________________________________________________________________________

Descarga e Instalación de Prolog

En este apartado veremos la forma de descargar e instalar SWI-Prolog, un software gratuito del cual hemos hablado antes:

1.- Vamos a este enlace: http://www.swi-prolog.org/download/stable y elegimos en la tabla la versión de Prolog que es compatible con nuestro sistema, en mi caso fué de 64 bits (Segunda opción), si tu sistema operativo es de 32 bits, elige la primera.

2.- Se descarga un archivo de aproximadamente 13 mb, lo ejecutamos, si la pc pide permiso para ejecutar el archivo, damos que sí.

  Presionamos: I Agree

 Presionamos Next

 Ora vez Next

Presionamos Install

Una vez que halla terminado, presionamos Finiseh y Abrimos Prolog desde Todos los Programas.

Nos aparecerá una venana así:

¿Cómo cargar un Archivo en Prolog?

Vamos al Menú: File, después Consult y Examinamos en la PC el archivo que deseamos consultar. Listo.

Heurística

¿Qué es la Heurísica?

Es la ciencia que estudia los procesos de decisión respecto a un campo de conocimiento concreto, como son las estrategias cognitivas. Su contrapartida formal en computación es el algoritmo. 

La palabra heurística proviene de la palabra griega heuriskein que significa descubrir, encontrar. Por heurística entendemos una estrategia, método, criterio o truco usado para hacer más sencilla la solución de problemas difíciles. El conocimiento heurístico es un tipo especial de conocimiento usado por los humanos para resolver problemas complejos. En este caso el adjetivo heurístico significa medio para descubrir.

Debido a la existencia de algunos problemas importantes con un gran interés práctico difíciles de resolver, comienzan a surgir algoritmos capaces de ofrecer posibles soluciones que aunque no consiguen el resultado óptimo, si que se acercan en un tiempo de cálculo razonable. Estos algoritmos están basados en el conocimiento heurístico y por lo tanto reciben el nombre de algoritmos heurísticos.

Por lo general, los algoritmos heurísticos encuentran buenas soluciones, aunque a veces no hay pruebas de que la solución pueda hallarse en un tiempo razonablemente corto o incluso de que no pueda ser errónea. Frecuentemente pueden encontrarse casos particulares del problema en los que la heurística obtendrá resultados muy malos o que tarde demasiado en encontrar una solución.

Un método heurístico es un conjunto de pasos que deben realizarse para identificar en el menor tiempo posible una solución de alta calidad para un determinado problema. 

Al principio esta forma de resolver problemas no fue bien vista en los círculos académicos, debido fundamentalmente a su escaso rigor matemático. Sin embargo, gracias a su interés práctico para solucionar problemas reales fue abriendo poco a poco las puertas de los métodos heurísticos, sobre todo a partir de los años 60. Actualmente las versiones matemáticas de métodos heurísticos están creciendo en su rango de aplicaciones, así como en su variedad de enfoques. 

Nuevas técnicas heurísticas son utilizadas a diario por científicos de computación, investigadores operativos y profesionales, para resolver problemas que antes eran demasiado complejos o grandes para las anteriores generaciones de este tipo de algoritmos. 

Ejemplo: Problema del Viajante

“Un vendedor tiene una lista de ciudades cada una de las cuales debe visitar solamente una vez; existen carreteras directas entre cada par de ciudades de la lista. Se debe encontrar la ruta que el vendedor debería seguir para que, siguiendo el camino más corto posible, visitara todas las ciudades, comenzando por cualquiera de ellas y volviendo a la misma."

Se puede resolver éste problema explorando el árbol de todos los caminos posibles y eligiendo aquél que tenga la longitud mínima; pero, si existen n ciudades, el número de caminos diferentes entre ellas es (n-1)!, esto significa que el tiempo requerido para resolver el problema es proporcional a n!.

Por lo tanto, si tenemos once ciudades, (11-1)! = 10*9*8*7*6*5*4*3*2*1 = 3, 628,000 rutas son posibles, es decir, se trata de un problema típico de combinatoria en el que es útil aplicar técnicas heurísticas.

Una técnica heurística de propósito general que es útil para resolver problemas combinatorios es el 'algoritmo del vecino más próximo': 

Paso 1. Seleccionar un nodo inicial.
Paso 2. Identificar al nodo más cercano al último agregado,

siempre que no haya sido agregado.
Paso 3. Repetir el paso 2 hasta incluir todos los nodos.

 

Fuente:

Revista: Hiperenciclopédica de divulgación del Saber

Segunda Época, Año IX

Vol. 8, Num. 2: Abril - Junio de 2014