Integrantes:
Jorge
Corona Pineda 1164397
Salvador
Aguilar 967057
Arturo
Ramírez Morales 1165819
MINIPROYECTO #1 BÚSQUEDAS CIEGAS Y BÚSQUEDAS HEURÍSTICAS
Sistemas
Inteligentes
Lenguaje:
ActionScript 3.
Dispositivo:
Playbook.
Descripción
formal del problema:
Espacio de estados:
Conjunto de tableros posibles de 3x3 donde cada casilla puede contener sólo
un valor entre 1 y 8 sin repetición
dejando una casilla vacía.
Espacio de inicial:
Conjunto
de tableros posibles de 3x3 donde cada
casilla puede contener sólo un valor entre 1 y 8 sin repetición dejando una casilla vacía.
Espacio de final:
Conjunto
de tableros posibles de 3x3 donde cada
casilla puede contener sólo un valor entre 1 y 8 sin repetición dejando una casilla vacía.
Conjunto de reglas:
El valor de una casilla solo se
puede mover hacia arriba, abajo, a la
derecha y a la Izquierda si y solo si ese movimiento está dirigido hacia el
espacio vacío.
Búsqueda
ciega implementada y probada
En
esta búsqueda se diseño un algoritmo que va recorriendo el árbol de nodos posible en anchura para
encontrar el camino más rápido a la solución pero es importante mencionar que
ya que se expanden muchos nodos es un método muy tardado y que consume mucha
memoria.
Las búsquedas
heurísticas implementadas y probadas.
En
esta búsqueda utilizamos el método Hill Climbing donde se calcula la posibilidad
que tiene cada nodo con respecta a un valor que generamos por medio de cada
heurística para informar cuál podría ser el nodo que tiene la posibilidad de
llevarnos hacia la respuesta que deseamos obtener. Y en el caso de que no
encontremos dicho nodo el método de Hill Climbing termina regresando el camino actual
hasta donde logró llegar.
La
primera heurística se basa en contar las casillas que no se encuentran en su
lugar con respecto al estado final que se le ha indicado
La
segunda heurística se basa en sumar la distancia Manhattan que existe entre
cada casilla y el valor que se especificó en el estado final.
Comparación
|
Búsqueda
|
Número de movimientos
|
memoria
|
Tiempo
|
|
Hill Climbing
Heurística 2
|
3
|
7
|
172 milisegundos
|
|
Hill Climbing
Heurística 1
|
3
|
7
|
513 milisegundos
|
|
Búsqueda Ciega
|
29
|
55
|
700 milisegundos
|
*Nota:
los tiempos mostrados en el video no son los tiempos reales ya que el video se
creó en el emulador y no directamente en la PlayBook
Búsqueda ciega
Memoria: 55
Movimientos: 29
Estado inicial
|
1
|
2
|
3
|
|
|
5
|
6
|
|
4
|
7
|
8
|
Estado
final
|
1
|
2
|
3
|
|
4
|
5
|
6
|
|
7
|
8
|
|
Hill
Climbing Heurística 1
Memoria: 7
Movimientos: 3
Estado inicial
|
1
|
2
|
3
|
|
|
5
|
6
|
|
4
|
7
|
8
|
Estado
final
|
1
|
2
|
3
|
|
4
|
5
|
6
|
|
7
|
8
|
|
Hill
Climbing Heurística 2
Memoria: 7
Movimientos: 3
Estado inicial
|
1
|
2
|
3
|
|
|
5
|
6
|
|
4
|
7
|
8
|
Estado
final
|
1
|
2
|
3
|
|
4
|
5
|
6
|
|
7
|
8
|
|
