Esta aplicación web le permite ver una representación gráfica de una gama de diferentes algoritmos de búsqueda de grafos, mientras resuelve su elección de problemas de 8 puzzles.
Cómo empezar
En la parte izquierda de esta aplicación, verá el Panel de Control. Usando el Panel de Control, puede configurar los siguientes aspectos de la aplicación:
- Estado Inicial y Estado de la Meta
- Qué Algoritmo de Búsqueda usar
- Qué Función Heurística usar, si se usa un Algoritmo de Búsqueda Informada
- Y si se usa el modo de un solo paso o de ráfaga
Cada una de estas opciones se describirá con más detalle a continuación.
Estados inicial y de meta
Para establecer los estados inicial o de meta, puedes hacer clic en el botón «Editar estado» o en la representación gráfica del estado.
Deberías ver una ventana emergente como la siguiente:
Para cambiar una baldosa, simplemente haz clic en la baldosa que quieres reemplazar y luego introduce el nuevo valor con el teclado. Esto cambiará el azulejo con el que anteriormente tenía ese valor.
Algoritmo de Búsqueda
N-Puzzle soporta cinco diferentes Algoritmos de Búsqueda basados en gráficos. Los tres primeros son Algoritmos de Búsqueda No Informada:
- Búsqueda por amplitud
- Búsqueda por profundidad
- Búsqueda por profundización iterativa
Los otros dos son Algoritmos de Búsqueda Informada:
- Búsqueda A*
- Búsqueda Greedy
Si elige un Algoritmo de Búsqueda Informada, entonces también tendrá que seleccionar una Función Heurística.
Función Heurística
N-Puzzle admite tres funciones heurísticas diferentes:
- Distancia Euclidiana
- Distancia Manhattan (distancia ciudad-bloque)
- Asientos fuera de lugar
Modo de un solo paso o ráfaga
N-Puzzle puede utilizarse en dos modos. El predeterminado es el modo de un solo paso, que le permite «rebobinar» una búsqueda, un paso a la vez. Esto es útil para comprender mejor cómo funciona un algoritmo de búsqueda.
El otro modo es el Modo Ráfaga. Una vez iniciado, el Modo Ráfaga continúa ejecutando una búsqueda hasta que se encuentre el estado objetivo. Una búsqueda en Modo Ráfaga puede ser pausada, pero no puede ser «rebobinada».
El Árbol de Búsqueda
Representación del Estado
Mientras una búsqueda está activa, usted podrá ver una representación visual del árbol de búsqueda. Cada nodo en este árbol de búsqueda representa un arreglo de fichas (o estado), y se dibuja como una caja que se divide en 4 secciones.
El siguiente diagrama muestra un nodo tomado de una búsqueda Greedy:
La sección más grande es el estado del rompecabezas. Debajo de eso verás dos secciones más pequeñas.
Debajo del estado de rompecabezas hay dos secciones. La sección de la izquierda es la profundidad del nodo. La sección de la derecha es la puntuación heurística. La puntuación heurística sólo se utiliza con los Algoritmos de Búsqueda Informada, por lo que si está utilizando la Búsqueda de Amplitud-Primera, de Profundidad-Primera o de Profundidad Iterativa, la puntuación heurística se omitirá.
La última sección registra el orden en el que se expandieron los nodos. Por ejemplo, el nodo raíz siempre será el ‘#1’, y el siguiente nodo en expandirse será marcado como ‘#2’.
Colores de los nodos
Para ayudar a que el Árbol de Búsqueda sea más ‘legible’, el borde de cada nodo tiene un código de colores basado en su estado actual.
El siguiente diagrama muestra el algoritmo A* (con la heurística de la distancia euclidiana) aplicado a un problema que puede resolverse en sólo dos movimientos:
Los colores pueden interpretarse como sigue:
| Color | Significado |
|---|---|
| Azul | Si un nodo está en la Lista Abierta entonces se resaltará en azul. |
| Rojo | Después de cada iteración de un algoritmo de búsqueda, el nodo que se expandirá a continuación se resaltará en rojo. Esto se aplica incluso cuando se ha encontrado el nodo meta. |
| Gris | Si un estado ha sido explorado, aparecerá en gris. Por ejemplo, en el paso 2) del diagrama anterior, el estado inicial se ha coloreado en gris para indicar que ha sido explorado. En el paso 3), se redescubre un nodo que representa el estado inicial, pero no se expandirá ya que el estado inicial se ha expandido a través del nodo raíz. |
| Verde | Una vez encontrado el estado meta, se resaltará en verde. |
| Oro | Una vez que se ha encontrado un nodo que representa el estado de meta, cualquier nodo en el camino de vuelta al nodo raíz se resaltará en color oro. |
| Púrpura | Cuando se utiliza la Búsqueda de Profundización Iterativa, los nodos no explorados que exceden la profundidad máxima no se añadirán a la lista abierta. Estos nodos se colorearán en púrpura. |
Listas abiertas y cerradas
Mientras se ejecutan los algoritmos de búsqueda, se mantienen dos listas. La primera es la Lista Abierta – se utiliza para llevar un registro de los nodos que han sido descubiertos, pero aún no explorados.
La segunda es la Lista Cerrada – se utiliza para llevar un registro de los nodos que han sido explorados, o de los nodos que no serán explorados porque representan estados que ya han sido explorados a través de otros nodos.
Cuando una búsqueda está activa, el número de nodos en las Listas Abiertas y Cerradas será visible en la esquina superior izquierda:
