Puzzle 8
Juan Ramón Fernández Álvarez (1164922) <A01164922@itesm.mx>
Gerardo Galindez Barreda (1164049) <A01164049@itesm.mx>
A continuación se presenta un reporte del miniproyecto del Puzzle 8. Este reporte fue desarrollado para la clase de Sistemas Inteligentes en el Tecnológico de Monterrey, Campus Estado de México.
Introducción
En este mini proyecto, y para reforzar los conocimientos que hemos aprendido hasta este punto en el semestre se nos pidió que realizaramos un programa que pudiera resolver el problema de puzzle 8 de 3 formas diferentes. Una de ellas debería de ser una búsqueda ciega por anchura primero, mientras que las otras dos deberían de ser resueltas usando el método de Hill Climbing con dos heurísticas diferentes.
El proyecto además debería de tener una interfáz gráfica en la que fácilmente se pudiera cambiar el estado inicial y final deseados, el método por el cual se desea resolver el problema, el camino mediante el cual se resolvió (o aproximó) al problema, entre otras cosas.
Diseño
Se decidió usar Python como lenguaje de programación para la resolución de los algoritmos y después montarlo como un CGI sobre un servidor apache para tener la posibilidad de crear una interfaz web simple.
Descripción formal
Espacio de estados: Las posibles combinaciones de mover la ficha vacía hacia arriba, abajo, izquierda o derecha.
Estados iniciales: Cualquier combinación de números del 0 al 8 donde el 0 representa la casilla vacía y los demás números las casillas con valor. Dicha combinación debe de partir del estado final, haciendo los movimientos permitidos.
Estados finales: Cualquier combinación de números del 0 al 8 donde el 0 representa la casilla vacía y los demás números las casillas con valor.
Conjunto de reglas: En caso de que la casilla vacía esté en una orilla, solo podrá moverse con 3 posiciones diferentes. En caso de que esté en una esquina, sólo podrá moverse con 2 posiciones diferentes.
Búsquedas
A continuación presentamos las búsquedas realizadas, su código, una breve explicación de como funcionan y un par de pruebas.
Breadth First Search
También conocido como anchura primero, esta búsqueda ciega es realiza creando todos los movimientos posibles con la esperanza de que eventualmente se resuelva. Por la naturaleza del algoritmo siempre encontrará una solución si es que existe, sin embargo en nuestro código nos vimos forzados a implementar un limite con el fin de que nuestro algoritmo pudiera terminar en un tiempo razonable y más importante aún, que el cliente no fuera a pensar que el servidor se encontraba muerto a causa de largos tiempos de respuesta.
A continuación presentamos el código de Breadth First Search
'''
Returns an array containing the nodes on the first element and the length
on the second
'''
def comb_plus_length(node):
nodes = generate_combinations(node)
length = len(nodes)
#print [nodes, length]
return [nodes, length]
'''
Solves the 8th puzzle using Breadth First Search
Still needs optimizations, urgently. (I hate thee brute force)
Keep the depths low, else your comp might explode
'''
def look_fat(arr, end, depth, count):
# Caso Base: Ya valió
if depth == 0:
return [arr[0], count, depth, 0]
# Caso Base: Lo encontró
node_num = 0
for node in arr:
count += 1
if node == end:
tree = [node, count, depth, node_num+1]
return tree
node_num += 1
# Default
array, arr_L = [], []
for node in arr:
temp = comb_plus_length(node)
array.extend(temp[0])
arr_L.append(temp[1])
final = look_fat(array, end, depth-1, count)
# Ya de regreso
son, dad = final[3],0
for lens in arr_L:
son -= lens
if son <= 0:
final[0].extend(arr[dad])
final[3] = dad+1
break
dad += 1
return final
'''
Formats things so that you dont need to over use it
'''
def breath_first_search(start_node, end_node, depth):
arr = [start_node]
final = look_fat(arr, end_node, depth, 0)
final[2] = depth - final[2]
temp = final[0]
final[0] = []
for i in range(len(temp)/9):
final[0].append(temp[i*9:i*9+9])
final[0].reverse()
return final
Ahora realizamos un par de pruebas para ver su funcionamiento.
Prueba 1:
Estado Inicial: [1,0,2,4,5,3,7,8,6]
Estado Final: [1,2,3,4,5,6,7,8,0]
Inicio
[ 1 0 2 ]
[ 4 5 3 ]
[ 7 8 6 ]
[ 1 2 0 ]
[ 4 5 3 ]
[ 7 8 6 ]
[ 1 2 3 ]
[ 4 5 0 ]
[ 7 8 6 ]
[ 1 2 3 ]
[ 4 5 6 ]
[ 7 8 0 ]
Fin
Prueba 2:
Estado Inicial: [4,5,8,1,2,7,6,0,3]
Estado Final: [1,2,3,4,5,6,7,8,0]
Inicio
[ 4 5 8 ]
[ 1 2 7 ]
[ 6 0 3 ]
[ 4 5 8 ]
[ 1 0 7 ]
[ 6 2 3 ]
[ 4 0 8 ]
[ 1 5 7 ]
[ 6 2 3 ]
[ 4 5 8 ]
[ 1 0 7 ]
[ 6 2 3 ]
[ 4 0 8 ]
[ 1 5 7 ]
[ 6 2 3 ]
[ 4 5 8 ]
[ 1 0 7 ]
[ 6 2 3 ]
Fin
Como podemos ver, en la primera prueba el algoritmo llego sin problemas a la solucion ya que se encontraba relativamente cerca, sin embargo ya que la segunda prueba presentaba un caso inicial mucho más complejo no pudo llegar en el numero de movimientos al que se había delimitado, y como es una búsqueda ciega regresa el primer nodo de ese nivel como mejor respuesta.
Hill Climbing
Este es un algoritmo en el que con la ayuda de una heurística se pretende llegar a un resultado de una forma más guiada. Por ser hacer uso de una heurística no necesariamente va a llegar al resultado deseado, sin embargo al menos si llegara a una aproximación y en ese caso es lo único que se regresará. Para Hill Climbing se utilizaron dos heurísticas diferentes las cuales se presentan más adelante. A continuación ponemos el código de Hill Climbing.
'''
Generates the heuristic values for each node
'''
def generate_heuristics(combinations, end, heuristic):
nodes = list()
for node in combinations:
pair = list()
pair.append(node)
pair.append(heuristic(node, end))
nodes.append(pair)
return nodes
'''
Chooses the paths that can be followed. If more than one
path can be followed, it chooses the first one
'''
def select_paths(nodes, start, end, heuristic):
paths = list()
current_heuristic = heuristic(start, end)
for node in nodes:
node_heuristic = node[1]
if node_heuristic > current_heuristic:
paths.append(node[0])
return paths
'''
Executes the hill climbing algorithm across the 8-puzzle paths.
Returns a list with the solution's path
'''
def hill_climbing(start, end, heuristic, result, steps, nodes):
combinations = generate_combinations(start) # Generate the four possible squares
heuristics = generate_heuristics(combinations, end, heuristic)
paths = select_paths(heuristics, start, end, heuristic)
if paths:
result.append(paths[0])
return hill_climbing(paths[0], end, heuristic, result, steps+1, nodes+len(heuristics))
else:
final = list()
final.append(result)
final.append(steps)
final.append(nodes)
return final
Heurística 1:
La primera heurística calcula el número de nodos que ya se encuentran en su lugar y entre más grande es la heurística es mejor.
'''
Executes the 8-puzzle heuristic. The square gains 1 heuristic point
for each square in the correct position
NOTE: Prefer the highest score
'''
def by_position(start, end):
n = 0
for index, elem in enumerate(start):
if end[index] == elem:
n += 1
return n
Prueba 1:
Estado Inicial: [1,0,2,4,5,3,7,8,6]
Estado Final: [1,2,3,4,5,6,7,8,0]
Inicio
[ 1 0 2 ]
[ 4 5 3 ]
[ 7 8 6 ]
[ 1 2 0 ]
[ 4 5 3 ]
[ 7 8 6 ]
[ 1 2 3 ]
[ 4 5 0 ]
[ 7 8 6 ]
[ 1 2 3 ]
[ 4 5 6 ]
[ 7 8 0 ]
Fin
Prueba 2:
Estado Inicial: [4,5,8,1,2,7,6,0,3]
Estado Final: [1,2,3,4,5,6,7,8,0]
[ 4 5 8 ]
[ 1 2 7 ]
[ 6 3 0 ]
Heurística 2:
La segunda heurística calcula el la distancia manhatan a la que se encuentra cada uno de los nodos y las suma. Esta heurística prefiere los valores más chicos sin embargo por compatibilidad con la anterior se les resta el resultado al valor máximo teorico, en este caso 36.
'''
You're a wizard Harry.
Recieves the current node(start) and the desired end node(end)
Does some kind of philosophical magic.
'''
def by_magic(start, end):
ind,total,MAX = 0,0,36
for number in start:
desired = end.index(number)
hor = abs(ind%3 - desired%3)
ver = abs(ind/3 - desired/3)
man_hatan = hor + ver
total += man_hatan
ind += 1
return MAX-total
Prueba 1:
Estado Inicial: [1,0,2,4,5,3,7,8,6]
Estado Final: [1,2,3,4,5,6,7,8,0]
[ 1 0 2 ]
[ 4 5 3 ]
[ 7 8 6 ]
[ 1 2 0 ]
[ 4 5 3 ]
[ 7 8 6 ]
[ 1 2 3 ]
[ 4 5 0 ]
[ 7 8 6 ]
[ 1 2 3 ]
[ 4 5 6 ]
[ 7 8 0 ]
Prueba 2:
Estado Inicial: [4,5,8,1,2,7,6,0,3]
Estado Final: [1,2,3,4,5,6,7,8,0]
[ 4 5 8 ]
[ 1 2 7 ]
[ 6 3 0 ]
Salida Comparativa
Finalmente tenemos la salida comparativa en la que se llama a los tres métodos y obtenemos los movimientos, el tiempo y la memoria.
Breadth-First
Node count: 32
Step Count: 3
Time: 0.00040400
Memory: 1536
Hill Climbing by position
Node count: 8
Step Count: 3
Time: 0.000325999
Memory: 384
Hill Climbing by Manhattan
Node count: 8
Step Count: 3
Time: 0.000467999
Memory: 384
No hay comentarios:
Publicar un comentario