practica-4.txt (C 151197) (UR 151197)
B\'usqueda en anchura
============================================================================

****************************************************************************
*                              ATENCION                                    *
****************************************************************************

Para esta pr\'actica 4 necesitamos los siguientes ficheros:

- hanoi.lsp : con las definiciones (realizadas en la pr\'actica 2) que
  se usan en la representaci\'on del problema de las torres de Hanoi con 3
  discos.

- busqueda-anchura.lsp : con las definiciones que implementan el
  m\'etodo de b\'usqueda de soluciones en anchura.

- practica-4.txt : este fichero que est\'as leyendo, con el enunciado de
  los ejercicios.

 En este fichero NO vamos a escribir c\'odigo Lisp. Lo debes utilizar
s\'olamente para anotar en las tablas que aparecen a continuaci\'on los
datos que se piden y para leer los enunciados de los ejercicios que se
proponen. Las funciones Lisp que se piden deben ser escritas en los
ficheros hanoi.lsp y busqueda-anchura.lsp que acompa\~nan a esta
pr\'actica. As\'i en esta practica manejaremos cuatro "buffers"
simult\'aneamente: el interprete de lisp y los tres ficheros
practica-4.txt, hanoi.lsp y busqueda-profundidad.lsp.

Recuerda que para cargar un fichero en emacs debes teclear Ctrl-X Ctrl-F
<nombre-de-fichero> ENTER y que para mostrar un buffer en una ventana,
debes hacer (cuando el cursor est\'e situado en la ventana correspondiente) 
Ctrl-X B <nombre-del-buffer> ENTER.


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

 Consideremos la siguiente versi\'on 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\'an vac\'ios.
   - S\'olo puede moverse un disco a la vez y todos los discos deben de
       estar ensartados en alg\'un poste.
   - Ning\'un 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\'actica 2, pero para una cantidad
   cualquiera de discos.


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

 (1) Modificar hanoi.lsp para que se admita una cantidad cualquiera de
     discos en los postes; para ello, crear la funci\'on
        (INICIA-HANOI N)
     que plantee el problema para cierto valor de N. Por ejemplo,
        > (load "busqueda-anchura")
        T
        > (load "hanoi")
        T
        > (inicia-hanoi 2)
        ....
        > (busqueda-en-anchura)
        Estado alcanzado: <Poste A=NIL Poste B=NIL Poste C=(1 2)>
        Movimientos realizados desde el estado inicial: 
               MOVER-DE-A-A-B
               MOVER-DE-A-A-C
               MOVER-DE-B-A-C



 (2) Calcular el tiempo y el espacio consumido para N igual a 3, 4 y 5 
     utilizando el m\'etodo de b\'usqueda en anchura y escribir los
     resultados en la siguiente tabla:
     +-------------+-------------+----------------+
     | N\'umero de | Tiempo      | Espacio        |
     |   discos    | (segundos)  | (bytes)        |
     +-------------+-------------+----------------+
     |      3      |             |                |
     |      4      |             |                |
     |      5      |             |                |
     +-------------+-------------+----------------+

 (3) Modificar en busqueda-anchura.lsp la implementaci\'on del m\'etodo de
     b\'usqueda en anchura para que devuelva, adem\'as de la soluci\'on
     encontrada, el n\'umero total de nodos analizados, el n\'umero m\'aximo
     de nodos abiertos simult\'aneamente y la profundidad de la
     soluci\'on. Aplicar este nuevo m\'etodo 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\'umero de | Profundidad |   Nodos    |  M\'aximo de   |
     |   discos    |  soluci\'on | analizados | nodos abiertos |
     +-------------+-------------+------------+----------------+
     |      1      |             |            |                |
     |      2      |             |            |                |
     |      3      |             |            |                |
     |      4      |             |            |                |
     |      5      |             |            |                |
     +-------------+-------------+------------+----------------+


 (4) Modifica la funci\'on escribe-estado-hanoi en hanoi.lsp para que
     describa  los estados de una manera gr\'afica: por ejemplo, el estado
     #S(estado (1 2) () (3))
     lo debe de escribir como
     1
     2   _   3
     Otro ejemplo: el estado inicial lo debe escribir como
     1
     2
     3   _   _

     Una vez definida, ejecuta (usando la primitiva versi\'on de 
     busqueda-en-anchura):

     > (inicia-hanoi 3)
     > (verifica (reverse (camino (busqueda-en-anchura))))

     y comprueba esta nueva funci\'on de impresi\'on. Trata de mejorarla. 


 (5) Realiza el ejercicio propuesto en la pr\'actica 3. Una vez
     completado, busca una soluci\'on con el procedimiento de b\'usqueda
     en anchura y completa los datos de la siguiente tabla.

          +-------------+------------+----------------+
          | Profundidad |   Nodos    |  M\'aximo de   |
          |  soluci\'on | analizados | nodos abiertos |
          +-------------+------------+----------------+
          |             |            |                |
          +-------------+------------+----------------+