Rompecabezas Numerico

...

[1 0 3]

[4 2 6]

[7 5 8]

Con el algoritmo de búsqueda a lo ancho se obtuvo un total de 27 nodos expandidos, la solución se encontró en la profundidad 3 y se tardó 5 segundos en resolverlo.

Con el algoritmo de búsqueda en profundidad le tomo 6 segundos, expandiendo un total de 6811 nodos y encontrando la solución en la profundidad 2338 este resultado fue tomando en cuenta que la prioridad de las acciones para expandir nodos fueran primero con el cero hacia abajo, luego hacia la derecha, seguido hacia la izquierda y finalmente hacia arriba, utilizando el mismo algoritmo pero cambiando la prioridad de las acciones siendo ahora primero a la derecha, seguido de la izquierda, después hacia abajo y finalmente hacia arriba, le tomó 25 minutos y 4 segundos encontrar la solución, expandió un total de 475364 nodos, encontrando la solución en la profundidad 52914.

Utilizando el algoritmo A* se obtuvo un total de nodos de 13, encontró la solución en la profundidad 3 y se tardó 6 segundos. Encontró la solución en la misma profundidad que usando el algoritmo de anchura, se tardó 1 segundo más pero expandió un menor número de nodos.

En los de 4x4 se utilizó como ejemplo el siguiente estado inicial:

[9 1 6 2]

[5 0 3 4]

[13 11 12 8]

[10 14 7 15]

Utilizando los métodos de anchura y profundidad llevaban más de 3 horas en ejecución y habían gastado casi toda la memoria con la que se contaba por lo que se decidió terminar con la búsqueda ya que es una matriz muy compleja para resolver, sin embargo, utilizando el algoritmo A* le tomó únicamente 8 segundos resolverlo, expandiendo un total de nodos de 10519 encontrando la solución en la profundidad 114.

[1 2 3 0]

[5 6 7 4]

[9 10 11 8]

[13 14 15 12]

Utilizando un estado inicial más simple utilizando el método de anchura se resolvió en 5 segundos, expandiendo 23 nodos y encontrando la solución en 3 pasos.

[5 1 3 4]

[9 2 6 8]

[13 11 17 12]

[0 10 14 15]

Si tomamos el estado anterior como el inicial, utilizando anchura genera un total de 23657 nodos y encuentra la solución en una profundidad de 12, tomándole 11 segundos hacerlo, utilizando el algoritmo de profundidad se determinó que es muy complejo como para solucionarlo rápidamente.

El algoritmo A* expandió 44 nodos para encontrar la solución, en una profundidad de 11, le tomo 3 segundos resolverlo. El tener una heurística ayuda mucho a evitar la expansión innecesaria de nodos dando una ventaja muy efectiva comparada con los otros métodos.

[1 3 4 5 10]

[6 2 8 9 15]

[12 7 13 14 0]

[11 17 18 19 20]

[16 21 22 23 24]

Teniendo un estado de 5x5 utilizando el algoritmo A* se resolvió en tan solo 4 segundos expandiendo un total de 48 nodos y encontrando la solución en una profundidad de 14.

Debido a la complejidad que se va sumando mientras los rompecabezas se estén haciendo cada vez más grandes es muy recomendable que se utilicen algoritmos con heurísticas y se evite lo mayor posible utilizar algoritmos de búsqueda ciega ya que la mayoría de las veces vuelven mucho más complejo el problema en vez de solucionarlo.

Conclusiones

Se puede concluir que para resolver el problema del rompecabezas de números mediante estos 3 algoritmos se deben tener en cuenta algunos factores en el caso del algoritmo de profundidad en algunos casos funciona de mejor manera cambiando la prioridad de las acciones ya que si no se tiene definida la prioridad de las acciones de una manera adecuada, terminará haciendo cada vez más complejo el rompecabezas de números lo que resultara en una mayor cantidad de nodos y se ejecutara por un tiempo indefinido hasta acabarse la memoria.

El algoritmo A* es una mejor opción para solucionar este tipo de rompecabezas, ya que al tener una heurística (Número de fichas fuera de su lugar) que le ayude a encontrar el mejor camino que se pueda tomar le da una gran ventaja comparado a los otros dos, que buscan la solución a ciegas, expandiendo la mayor cantidad de nodos posibles para así encontrar una solución.

Expande los nodos que cuenten con un valor de función menor evitando así expandir nodos que solo volverían más complejo el rompecabezas.

Los algoritmos de anchura y profundidad se pueden utilizar en rompecabezas simples que no requieran de tantos movimientos para encontrar la solución, o que estén lo suficientemente acomodados para no caer en un bucle que tarda demasiado en encontrar una solución, hay casos en los que se tardan mucho en un rompecabezas de 3x3 ya que son muy complejos como para resolverlos solo expandiendo los posibles movimientos sin elegir cual es el mejor.

---------------------------------------------------------------