HSE-96: practica-02.txt
 Búsqueda sin información.
============================================================================

****************************************************************************
* ENUNCIADO:                                                               *
****************************************************************************

 Consideremos la siguiente versión del problema de las torres de Hanoi:
   - Existen tres postes que llamaremos A, B y C.
   - Hay N discos de distintos tama\~nos en el poste A, de forma que no
       hay un disco situado sobre otro de menor tama\~no.
   - Los postes B y C están vacíos.
   - Sólo puede moverse un disco a la vez y todos los discos deben de
       estar ensartados en algún poste.
   - Ningún disco puede situarse sobre otro de menor tama\~no.
   - El problema consiste en colocar los N discos en el poste C.
 Este problema es el mismo que el de la práctica 1, pero para una cantidad
   cualquiera de discos.

 Se usarán los ficheros hanoi.lsp y busqueda-ciega.lsp.

****************************************************************************
* APARTADOS:                                                               *
****************************************************************************

 (1) Modificar hanoi.lsp para que se admita una cantidad cualquiera de
     discos en los postes; para ello, crear la función
        (INICIA-HANOI N)
     que plantee el problema para cierto valor de N. Por ejemplo,
        > (load "busqueda-ciega")
	T
	> (load "hanoi")
	T
	> (inicia-hanoi 2)
	((1 2) NIL NIL)
	> (busqueda-en-anchura)
	#S(NODO 
	   :ESTADO (NIL NIL (1 2))
	   :CAMINO (MOVER-DE-B-A-C MOVER-DE-A-A-C MOVER-DE-A-A-B))
     Calcular el tiempo y el espacio consumido para N igual a 3 y a 4,
     utilizando el método de búsqueda en anchura y escribir los
     resultados en la siguiente tabla:
     +-------------+-------------+----------------+
     | Número de | Tiempo      | Espacio        |
     |   discos    | (segundos)  | (bytes)        |
     +-------------+-------------+----------------+
     |      3      |             |                |
     |      4      |             |                |
     +-------------+-------------+----------------+

 (2) Modificar en busqueda-ciega.lsp la implementación del método de
     búsqueda en anchura para que devuelva, además de la solución
     encontrada, el número total de nodos analizados, el número máximo
     de nodos abiertos simultáneamente y la profundidad de la
     solución. Aplicar este nuevo método al problema de las torres de Hanoi
     para valores de N iguales a 1, 2, 3, 4 y 5 y completar la siguiente tabla:
     +-------------+-------------+------------+----------------+
     | Número de | Profundidad |   Nodos    |  Máximo de   |
     |   discos    |  solución | analizados | nodos abiertos |
     +-------------+-------------+------------+----------------+
     |      1      |             |            |                |
     |      2      |             |            |                |
     |      3      |             |            |                |
     |      4      |             |            |                |
     |      5      |             |            |                |
     +-------------+-------------+------------+----------------+

 (3) Modificar en busqueda-ciega.lsp la implementación del método de
     búsqueda en profundidad para que devuelva, además de la solución
     encontrada, el número total de nodos analizados, el número máximo de
     nodos abiertos simultáneamente y la profundidad de la
     solución. Aplicar este nuevo método al problema de las torres de Hanoi
     para valores de N iguales a 1, 2, 3, 4 y 5 y completar la siguiente tabla:
     +-------------+-------------+------------+----------------+
     | Número de | Profundidad |   Nodos    |  Máximo de   |
     |   discos    |  solución | analizados | nodos abiertos |
     +-------------+-------------+------------+----------------+
     |      1      |             |            |                |
     |      2      |             |            |                |
     |      3      |             |            |                |
     |      4      |             |            |                |
     |      5      |             |            |                |
     +-------------+-------------+------------+----------------+

 (4) Modificar en busqueda-ciega.lsp la implementación del método de
     búsqueda en profundidad acotada para que devuelva, además de la
     solución encontrada, el número total de nodos analizados, el número
     máximo de nodos abiertos simultáneamente y la profundidad de la
     solución. Aplicar este nuevo método al problema de las torres de Hanoi
     para valores de N iguales a 1, 2, 3, 4 y 5 y completar la siguiente tabla,
     donde "cota utilizada" es la menor cota para la que se obtiene solución
     con el método de búsqueda en profundidad acotada.
     +-------------+-----------+-------------+------------+----------------+
     | Número de |   cota    | Profundidad |   Nodos    |  Máximo de   |
     |   discos    | utilizada |  solución | analizados | nodos abiertos |
     +-------------+-----------+-------------+------------+----------------+
     |      1      |           |             |            |                |
     |      2      |           |             |            |                |
     |      3      |           |             |            |                |
     |      4      |           |             |            |                |
     |      5      |           |             |            |                |
     +-------------+-----------+-------------+------------+----------------+

 (5) Definir al final de hanoi.lsp la función
        (RESUELVE :HANOI N :POR '<METODO> :CON-COTA C)
     que resuelva el problema de las torres de Hanoi para N discos,
     aplicando el <METODO> indicado, (BUSQUEDA-EN-ANCHURA,
     BUSQUEDA-EN-PROFUNDIDAD y BUSQUEDA-EN-PROFUNDIDAD-ACOTADA) y con la
     cota C proporcionada para aquellos métodos que la precisen. El valor
     de la cota por defecto ha de ser 5. 

 (6) Definir al final de hanoi.lsp la función
        (EXPERIMENTOS N M)
     que calcule todos los datos asociados a las soluciones del problema de
     las torres de Hanoi (los que se piden en el apartado 3), cuando el
     número de discos en el problema va desde N hasta M (0 < N <= M) y se
     utilizan los métodos de busqueda citados en el apartado 5.

 (7) OPCIONAL:
     Repetir el apartado 2 de la práctica pero para el método de
     búsqueda en profundidad iterativa, y hacer las modificaciones
     necesarias para que se pueda utilizar dicho método con la función
     RESUELVE del apartado 5.

 (8) Una vez finalizados todos los apartados anteriores, envía por correo
     electrónico a tu profesor los ficheros 
       "practica-02.txt"      (con Subject: Practica 2 (practica-02.txt))
       "hanoi.lsp"            (con Subject: Practica 2 (hanoi.lsp))
       "busqueda-ciega.lsp"   (con Subject: Practica 2 (busqueda-ciega.lsp))
     Recuerda, las direcciones son:
        fmartin@cs.us.es si tu profesor es F. J. Martín.
        jalonso@cs.us.es si tu profesor es J. A. Alonso.