Laboratorio 1.ipynb

Kernel: Python 3 (Ubuntu Linux)

Laboratorio: Algoritmos de búsqueda

Grupo 2

• Diego Fernandez García

• Sol Roman

• Javier de la Rosa Fernández

• Aritz Beraza Garayalde

from copy import deepcopy
import time
import math

# Estado inicial. Cada 'torre' de bloques se representa por un array donde el primer elemento es 
# la base de la torre y el último la cima

MESA = ["C", "B"]
TORRE = ["E", "D", "A"]

Clase Estado

# Cada estado guarda información de
#  * Cajas en la torre (de abajo a arriba)
#  * Cajas en la mesa
#  * Movimientos hasta llegar a el.
class Estado:
    META = ["E", "D", "C", "B", "A"]
    def __init__(self, t, m, p):
        self.torre = t
        self.mesa = m
        self.solucion = p
        # para A*
        self.coste = math.inf # infinito por defecto

    def isMeta(self):
        return Estado.META == self.torre

    # MoverCaja. Como una puede realizar máximo un movimiento, con señalar
    # la caja a mover es suficiente para conocer el movimiento.
    def moverCaja(self, caja, log=False):
        # Si la caja se encuentra en la mesa, la añadimos a la torre
        if caja in self.mesa:
            self.torre.append(caja)
            self.mesa.remove(caja)
            if log:
                print("Mover la caja [{}] de la mesa a la torre".format(caja))
        # Si la caja es la última en la torre, la ponemos en la mesa
        elif caja == self.torre[-1]:
            self.mesa.append(self.torre.pop())
            if log:
                print("Mover a caja [{}] de la torre a la mesa".format(caja))

        #self.estado[mov[1]].append(self.estado[mov[0]].pop())
        self.solucion.append(caja)
        return self

    # Espandir Nodo para generar el siguiente nivel del árbol
    def expandirNodo(self):
        expandedNodes = []
        # Para cada caja en la mesa, expandimos moviendo las cajas a la torre
        for caja in self.mesa:
            expandedNodes.append(deepcopy(self).moverCaja(caja))
        # También se expande la última caja de la torre moviendola a la mesa
        if len(self.torre) > 0:
            expandedNodes.append(deepcopy(self).moverCaja(self.torre[-1]))
        return expandedNodes
    
    def set_coste(self, coste):
        self.coste = coste
        return self

    def print(self):
        print("--Estado---------")
        print("TORRE :: {}".format(self.torre))
        print("MESA  :: {}".format(self.mesa))


# Tests:
# Almacena info de 3 torres y una lista de acciones
#e1 = Estado(["E", "C"],["B", "D", "A"], ["A", "E"])
#print(e1.torre)
#print(e1.isMeta())
# Si estado es meta, isMeta() devuelve True
#e2=Estado(["E", "D", "C", "B", "A"],[],[])
#e3=Estado([],["E", "D", "C", "B", "A"],[])
#print(e2.isMeta())
#print(e3.isMeta())

Búsqueda en Amplitud

# Búsqueda de amplitud
# Implementación del algoritmo de búsqueda de amplitud.
# Iterativamente, partiendo del estado inicial realizamos:
# A. Para cada uno de los estados posibles en un punto
#   1. Es este estado el estado Meta? 
#        1a. SI: Parar ejecución, hemos llegado a la meta.
#        1b. NO: Continuar ejecución
#   2. Expandimos el nodo y añadimos a la lista de nodos del siguiente nivel
#   3. Iterar el proceso para cada uno de los nodos del siguiente nivel
# B. Tras encontrar una solución: Partiendo del estado inicial, reproducir
#    la solución paso a paso y llegar a la meta.
def busquedaAmplitud():
    NODOS_EXPANDIDOS = 0
    HISTORIA = [] # Guardaremos aquí disposiciones ya exploradas de la TORRE, el orden de la mesa es indiferente

    def iterar(estados):
        print("Evaluando un nivel")
        nonlocal NODOS_EXPANDIDOS, HISTORIA
        next_estados = []

        for estado in estados:
            if estado.torre in HISTORIA:
                #do nothing
                print("Nodo repetido")
            elif estado.isMeta():
                return estado;
            else:
                HISTORIA.append(estado.torre)
                next_estados += estado.expandirNodo()
        NODOS_EXPANDIDOS += len(next_estados)
        return iterar(next_estados)

    start_time = time.time()

    solucion = iterar([Estado(TORRE, MESA, [])])

    end_time = time.time()
    print("SOLUCIÓN {} ENCONTRADA EN {}s.\nNODOS EXPANDIDOS: {}\nOrden de movimientos: {}".format(solucion.torre, end_time - start_time, NODOS_EXPANDIDOS, solucion.solucion))
    acciones = solucion.solucion
    estado = Estado(TORRE, MESA, [])
    estado.print()
    for accion in acciones:
        estado.moverCaja(accion, True)
        estado.print()

        
# Nota, sin revisar loops, expande 98 nodos
# Evitando loops: 49

busquedaAmplitud()

Evaluando un nivel
Evaluando un nivel
Evaluando un nivel
Nodo repetido
Nodo repetido
Nodo repetido
Evaluando un nivel
Nodo repetido
Nodo repetido
Nodo repetido
Nodo repetido
Nodo repetido
Evaluando un nivel
SOLUCIÓN ['E', 'D', 'C', 'B', 'A'] ENCONTRADA EN 0.004745006561279297s.
NODOS EXPANDIDOS: 49
Orden de movimientos: ['A', 'C', 'B', 'A']
--Estado---------
TORRE :: ['E', 'D', 'A']
MESA  :: ['C', 'B']
Mover a caja [A] de la torre a la mesa
--Estado---------
TORRE :: ['E', 'D']
MESA  :: ['C', 'B', 'A']
Mover la caja [C] de la mesa a la torre
--Estado---------
TORRE :: ['E', 'D', 'C']
MESA  :: ['B', 'A']
Mover la caja [B] de la mesa a la torre
--Estado---------
TORRE :: ['E', 'D', 'C', 'B']
MESA  :: ['A']
Mover la caja [A] de la mesa a la torre
--Estado---------
TORRE :: ['E', 'D', 'C', 'B', 'A']
MESA  :: []

Búsqueda con A*

# Algoritmo A*

def heuristica(estado):
    # Por cada caja en su sitio 0 puntos
    # por cada caja faltante 1 punto
    # Desde la primera caja mal situada: 2 x cajas por encima, ella incluida
    #  Para penalizar el caso en que cajas por encima de ella estén bien
    valor = len(estado.mesa) # Sumo cajas faltantes
    for idx,caja in enumerate(estado.torre):
        # Busco la primera caja mal situada
        # ej: en [e,d,a,b] sería a
        # la penalización será de dos puntos por todas las cajas de a en adelante, incluso si b está en la posición que le toca
        # pues aunque esté bien he de quitarla y volverla a poner
        # penalización sería: 4 en este caso, programáticamente: 2*(long_maxima_torre - idx_primera_caja_max - cajas_en_mesa)
        # 2*(5 - 2 - 1) = 4
        if Estado.META[idx] != caja : 
            valor += 2 * (5 - idx - len(estado.mesa)) 
    return valor

def busquedaA():
    NODOS_EXPANDIDOS = 0
    
    def iterar(estados_exp):
        nonlocal NODOS_EXPANDIDOS
        print("Iterando")
        print(len(estados_exp))
        # Busco el estado con menor valor de función heurística
        minimo = Estado([],[],[]) # Inicializado con un estado vacío (coste es infinito)
        for estado in estados_exp:
            if estado.coste < minimo.coste:
                minimo = estado
        estado_actual = minimo
        
        print("Estado actual {} con coste {}".format(estado_actual.torre, estado_actual.coste))
        #estados_exp.remove(estado_actual)
        
        # Comprobamos si estamos en el estado meta
        if estado_actual.isMeta():
            return estado_actual
        
        #Si no,  Una vez tengo el nodo mínimo lo expando y aplico la funcion heurística
        
        #nuevos_nodos = map(lambda e: (e, heuristica(e)),estado.expandirNodo())
        nuevos_nodos = [e.set_coste(heuristica(e)) for e in estado_actual.expandirNodo()]
        
        NODOS_EXPANDIDOS += len(nuevos_nodos)
        #print(nuevos_nodos + estados)
        # e itero
        return iterar(nuevos_nodos + estados_exp)

    start_time = time.time()
    estado_inicial = Estado(TORRE, MESA, [])
    estado_inicial.set_coste(heuristica(estado_inicial))
    NODOS_EXPANDIDOS+=1
    solucion = iterar([estado_inicial])

    end_time = time.time()
    print("SOLUCIÓN {} ENCONTRADA EN {}s.\nNODOS EXPANDIDOS: {}\nOrden de movimientos: {}".format(solucion.torre, end_time - start_time, NODOS_EXPANDIDOS, solucion.solucion))
    acciones = solucion.solucion
    estado = Estado(TORRE, MESA, [])
    estado.print()
    for accion in acciones:
        estado.moverCaja(accion, True)
        estado.print()
        
        
MESA = ["C", "B"]
TORRE = ["E", "D", "A"]
busquedaA()

# Nota, sin controlar loops expande 13 nodos
#

Iterando
1
Estado actual ['E', 'D', 'A'] con coste 4
Iterando
4
Estado actual ['E', 'D'] con coste 3
Iterando
8
Estado actual ['E', 'D', 'C'] con coste 2
Iterando
11
Estado actual ['E', 'D', 'C', 'B'] con coste 1
Iterando
13
Estado actual ['E', 'D', 'C', 'B', 'A'] con coste 0
SOLUCIÖN ['E', 'D', 'C', 'B', 'A'] ENCONTRADA EN 0.004506111145019531s.
NODOS EXPANDIDOS: 13
Orden de movimientos: ['A', 'C', 'B', 'A']
--Estado---------
TORRE :: ['E', 'D', 'A']
MESA  :: ['C', 'B']
Mover a caja [A] de la torre a la mesa
--Estado---------
TORRE :: ['E', 'D']
MESA  :: ['C', 'B', 'A']
Mover la caja [C] de la mesa a la torre
--Estado---------
TORRE :: ['E', 'D', 'C']
MESA  :: ['B', 'A']
Mover la caja [B] de la mesa a la torre
--Estado---------
TORRE :: ['E', 'D', 'C', 'B']
MESA  :: ['A']
Mover la caja [A] de la mesa a la torre
--Estado---------
TORRE :: ['E', 'D', 'C', 'B', 'A']
MESA  :: []

Conclusión

Como conclusión, se ha podido observar que el algoritmo heurístico de A* necesita expandir un número considerablemente menor de nodos que el algoritmo en amplitud. En concreto, el algoritmo en amplitud necesita expandir 98 nodods para alacanzar la meta (49 si se restingen los nodos hacia estados padre), frente a los 13 nodos expandidos con la heurística del algoritmo A*.