Implementación del 8-Puzzle en Python: acciones, heurísticas h1 y h2 y comparativa de búsqueda
Resumen
Este documento muestra cómo implementar en Python el problema del 8-puzzle, definiendo las acciones aplicables al hueco (0) del tablero 3x3 y la función que aplica cada movimiento. Después presenta dos heurísticas clásicas, las piezas fuera de lugar (h1) y la distancia de Manhattan (h2), y termina con un código para comparar el rendimiento de las búsquedas en anchura, en profundidad y primero el mejor. Está pensado para estudiantes de inteligencia artificial o programación que quieran entender cómo se resuelven puzzles mediante búsqueda en espacio de estados.
Puntos clave
- El hueco se representa con el valor 0 y sus movimientos posibles son arriba, abajo, izquierda y derecha, según su posición en el tablero.
- La función aplicar intercambia el hueco con la casilla destino y devuelve un nuevo estado como tupla, porque las tuplas no se pueden modificar.
- h1 cuenta el número de piezas que no están en su posición final, ignorando el hueco.
- h2 suma, para cada pieza, la distancia de Manhattan entre su posición actual y la objetivo.
- El estado final de referencia usado es (1, 2, 3, 8, 0, 4, 7, 6, 5).
- El ejercicio 5 compara las estrategias de anchura, profundidad, primero el mejor con h1 y primero el mejor con h2, mostrando la longitud de la solución (L) y los nodos analizados (NA).
Implementación del Problema del 8-Puzzle en Python
Ejercicio 1: Definición de Acciones Aplicables y Transiciones
En esta sección se define la lógica para identificar los movimientos válidos del hueco (representado por el valor 0) dentro de un tablero de 3x3, así como la función para aplicar dichos movimientos.
def acciones_aplicables(self, estado):
pos_hueco = estado.index(0)
accs = list()
if pos_hueco not in (0, 1, 2): # Fila de arriba
accs.append("Mover hueco arriba")
if pos_hueco not in (6, 7, 8): # Fila de abajo
accs.append("Mover hueco abajo")
if pos_hueco not in (0, 3, 6): # Columna izquierda
accs.append("Mover hueco izquierda")
if pos_hueco not in (2, 5, 8): # Columna derecha
accs.append("Mover hueco derecha")
return accs
def aplicar(self, estado, accion):
pos_hueco = estado.index(0)
if accion == "Mover hueco arriba":
nueva_pos = pos_hueco - 3
elif accion == "Mover hueco abajo":
nueva_pos = pos_hueco + 3
elif accion == "Mover hueco izquierda":
nueva_pos = pos_hueco - 1
elif accion == "Mover hueco derecha":
nueva_pos = pos_hueco + 1
tablero = list(estado) # Las tuplas no se pueden modificar
tablero[pos_hueco], tablero[nueva_pos] = tablero[nueva_pos], tablero[pos_hueco]
return tuple(tablero)Ejercicio 3: Funciones Heurísticas (h1 y h2)
Para optimizar la búsqueda, implementamos dos heurísticas clásicas: la cantidad de piezas fuera de su lugar (h1) y la distancia de Manhattan (h2).
def h1_ocho_puzzle(estado):
estado_final = (1, 2, 3, 8, 0, 4, 7, 6, 5)
contador = 0
for i in range(9):
if estado[i] != 0 and estado[i] != estado_final[i]:
contador += 1
return contador
def h2_ocho_puzzle(estado):
estado_final = (1, 2, 3, 8, 0, 4, 7, 6, 5)
distancia_total = 0
for pieza in range(1, 9):
pos_actual = estado.index(pieza)
pos_objetivo = estado_final.index(pieza)
fila_actual, columna_actual = pos_actual // 3, pos_actual % 3
fila_objetivo, columna_objetivo = pos_objetivo // 3, pos_objetivo % 3
distancia_total += abs(fila_actual - fila_objetivo) + abs(columna_actual - columna_objetivo)
return distancia_totalEjercicio 5: Comparativa de Algoritmos de Búsqueda
El siguiente bloque de código permite realizar una comparativa de rendimiento entre diferentes estrategias de búsqueda: Anchura, Profundidad y Primero el Mejor.
def ejercicio_5(recalcular=False):
combinaciones = [
("Anchura", búsqueda_en_anchura, None),
("Profundidad", búsqueda_en_profundidad, None),
("Primero_h1", búsqueda_primero_el_mejor, h1_ocho_puzzle),
("Primero_h2", búsqueda_primero_el_mejor, h2_ocho_puzzle), ]Continuación del Ejercicio 5
A continuación, se detalla el proceso de iteración sobre los estados y la impresión de resultados formateados:
print("{0:6} | {1:22} | {2:>6} | {3:>6}".format("Estado", "Algoritmo", "L", "NA"))
print("-" * 52)
for nombre_estado, estado in ESTADOS.items():
for nombre_algoritmo, algoritmo, h in combinaciones:
referencia = RESULTADOS_DE_REFERENCIA[(nombre_estado, nombre_algoritmo)]
if referencia is None and not recalcular:
print("{0:6} | {1:22} | {2:>6} | {3:>6} (no termina en tiempo razonable)".format(
nombre_estado, nombre_algoritmo, "--", "--"))
continue
if referencia is not None and not recalcular:
L, NA = referencia
else:
p8p = Problema_con_Analizados(Ocho_Puzzle(estado))
sol = (algoritmo(p8p, h).solucion() if h else algoritmo(p8p).solucion())
L, NA = len(sol), p8p.analizados
print("{0:6} | {1:22} | {2:6d} | {3:6d}".format(nombre_estado, nombre_algoritmo, L, NA))Descargar
PDF Word HTMLPreguntas frecuentes
¿Qué representa el valor 0 en el 8-puzzle de este código?
El valor 0 representa el hueco del tablero. Las acciones se calculan a partir de su posición, y al aplicar un movimiento se intercambia con la casilla vecina.
¿Qué diferencia hay entre h1 y h2?
h1 cuenta cuántas piezas están fuera de su lugar, mientras que h2 suma las distancias de Manhattan de cada pieza a su posición objetivo, por lo que suele ofrecer una estimación más informativa.
Ponte a prueba
Tarjetas de repaso
Pulsa una tarjeta para ver la respuesta.
Test
Preguntas generadas con IA a partir del documento: comprueba las respuestas con el texto.