Plataforma
El proyecto fue desarrollado en Java 5 y se utilizó Swing y AWT, las librerías gráficas de Java.
Descripción formal del problema
Espacio de estados: Este problema tiene 9 celdas en las que se podrán acomodar los números en un rango del 1 al 8, un número por casillas. El tener este rango implica que halla una celda vacía que permitirá que las celdas de las cifras se muevan para cambiar de posición.
Estado inicial: cualquier entrada que contenga las cifras del 1 al 8 en cualquier posición y dejando un celda vacía.
Estado final: puede ser cualquier resultado en el que se muestren las cifras del 1 al 8 acomodadas en orden. Ya sea posicionando los números de alrededor del recuadro o posicionándolos por renglón.
Conjunto de reglas:
1. Los números deben moverse sólo adyacentemente, es decir sólo pueden moverse vertical u horizontalmente.
2. Para mover un número es necesario que tenga la celda vacía en una posición adyacente.
Búsqueda ciega implementada
La búsqueda ciega para este problema se realizó en anchura, la cual expande todos los nodos del padre.
En ésta búsqueda, al hacer las pruebas, pudimos percatarnos de que se puede realizar bien el problema para casos sencillos que no requieran demasiados movimientos.
Si el problema requiere de una cantidad considerable de movimientos, que impliquen una anchura elevada, la búsqueda tardará mucho tiempo y memoria en encontrar una solución.
Búsqueda Hill climbing
Heurística 1:
En la heurística uno se obtiene la posición del número y se ve si ya está en su fila o en su columna según el orden del estado final. Se hace una sumatoria dependiendo de la posición de cada número. Si ya está en la posición que debe estar en el estado final suma 0, si no está en su columna o no está en su fila se le suma 1, pero si no está en su fila ni está en su columna se suma 2. Al hacer la sumatoria se escoge la menor de los nodos expandidos.
Nota: para la ésta heurística no se toma en cuenta en la posición del espacio vacío.
Heurística 2:
Nuestra segunda heurística se obtiene a partir del número de movimientos necesarios para llegar a la solución, moviendo los números sin tomar en cuenta las reglas del juego. Esto es, se itera sobre los números del nodo actual y, si se encuentra un número fuera de su posición, se intercambia por aquel número que se encuentre en la posición meta de este número. Una vez que pasa esto, se reinicia la iteración desde el inicio del arreglo, pero ya modificado. El valor de la heurística será, entonces, el número de intercambios necesarios para llegar a la solución.
Nota: para la ésta heurística no se toma en cuenta el espacio vacío.
Comparación entre búsquedas
Búsqueda 1:
4,1,3,0,2,6,7,5,8
Resultados:
- Búsqueda en Anchura
Tiempo: 31 ms
Movimientos(Profundidad): 6
Máximo número de nodos almacenados: 64
Total de nodos visitados: 129
-Búsqueda Hill Climbing, con Heurística 1
Tiempo: 1 ms
Movimientos(Profundidad): 5
Máximo número de nodos almacenados: 1
Total de nodos visitados: 15
-Búsqueda Hill Climbing, con Heurística 2
Tiempo: 2 ms
Movimientos(Profundidad): 5
Máximo número de nodos almacenados: 1
Total de nodos visitados: 15
Búsqueda 2:
2,4,3,1,0,6,7,5,8
Resultados:
- Búsqueda en Anchura
Tiempo: 100 ms
Movimientos(Profundidad): 7
Máximo número de nodos almacenados: 256
Total de nodos visitados: 514
-Búsqueda Hill Climbing, con Heurística 1 (sin encontrar solución)
Tiempo: 1 ms
Movimientos(Profundidad): 3
Máximo número de nodos almacenados: 2
Total de nodos visitados: 9
-Búsqueda Hill Climbing, con Heurística 1 (con solución)
Tiempo: 1 ms
Movimientos(Profundidad): 6
Máximo número de nodos almacenados: 2
Total de nodos visitados: 19
-Búsqueda Hill Climbing, con Heurística 2
NOTA: Con esta heurística, el algoritmo no encontró la solución
Tiempo: 2 ms
Movimientos(Profundidad): 3
Máximo número de nodos almacenados: 1
Total de nodos visitados: 9
No hay comentarios:
Publicar un comentario