<jupyter_start><jupyter_text>Grupo 10<NAME>  <NAME>  <NAME>    Problema de cruzar el puenteUn grupo de 5 personas quiere cruzar un viejo y estrecho puente. Es una noche cerrada y se necesita llevar una linterna para cruzar. El grupo solo dispone de una linterna, a la que le quedan 5 minutos de batería.Cada persona tarda en cruzar 10, 30, 60, 80 y 120 segundos, respectivamente.El puente solo resiste un máximo de 2 personas cruzando a la vez, y cuando cruzan dos personas juntas, caminan a la velocidad del más lento.No se puede lanzar la linterna de un extremo a otro del puente, así que cada vez que crucen dos personas, alguien tiene que volver a cruzar hacia atrás con la linterna a buscar a los compañeros que falten, y así hasta que hayan cruzado todos.<jupyter_code># Cargamos el módulo con los algoritmos de búsqueda.
import sys
sys.path.append('aima-python/')
import search
from search import *
from search import breadth_first_tree_search, depth_first_tree_search, depth_first_graph_search, breadth_first_graph_search
   class Problem(object):

    """The abstract class for a formal problem. You should subclass
    this and implement the methods actions and result, and possibly
    __init__, goal_test, and path_cost. Then you will create instances
    of your subclass and solve them with the various search functions."""

    def __init__(self, initial, goal=None):
        """The constructor specifies the initial state, and possibly a goal
        state, if there is a unique goal. Your subclass's constructor can add
        other arguments."""
        self.initial = initial
        self.goal = goal

    def actions(self, state):
        """Return the actions that can be executed in the given
        state. The result would typically be a list, but if there are
        many actions, consider yielding them one at a time in an
        iterator, rather than building them all at once."""
        raise NotImplementedError

    def result(self, state, action):
        """Return the state that results from executing the given
        action in the given state. The action must be one of
        self.actions(state)."""
        raise NotImplementedError

    def goal_test(self, state):
        """Return True if the state is a goal. The default method compares the
        state to self.goal or checks for state in self.goal if it is a
        list, as specified in the constructor. Override this method if
        checking against a single self.goal is not enough."""
        if isinstance(self.goal, list):
            return is_in(state, self.goal)
        else:
            return state == self.goal

    def path_cost(self, c, state1, action, state2):
        """Return the cost of a solution path that arrives at state2 from
        state1 via action, assuming cost c to get up to state1. If the problem
        is such that the path doesn't matter, this function will only look at
        state2.  If the path does matter, it will consider c and maybe state1
        and action. The default method costs 1 for every step in the path."""
        return c + 1

    def value(self, state):
        """For optimization problems, each state has a value.  Hill-climbing
        and related algorithms try to maximize this value."""
        raise NotImplementedError

    def coste_de_aplicar_accion(self, estado, accion):
        """Hemos incluido está función que devuelve el coste de un único operador (aplicar accion a estado). Por defecto, este
        coste es 1. Reimplementar si el problema define otro coste """ 
        return 1<jupyter_output><empty_output><jupyter_text>PRUEBASSe han realizado definido 3 heurísticas diferentes y se han realizado pruebas con diferentes heurísticas, algoritmos y configuraciones del problema (más personas, diferente tiempo de bateria, etc.)Todas esas pruebas se irán detallando a lo largo del notebook.   Planteamiento del problema (clase problema, estados...)En primer lugar contamos con un diccionario "Personas" donde a cada persona se le asigna el tiempo que tarda en cruzar el puente. Esta variable será fija y no forma parte del estado.El estado lo formamos con 3 tuplas, una primera con la posicion de la linterna y el tiempo de batería restante en segundos, una segunda con una lista de las personas que se encuentran a la izquierda del puente, y una última tupla con las personas que se encuentran a la derecha del puente Acciones        Para generar las opciones posibles con un estado, contamos con que si el movimiento se produce desde la izquierda del puente, siempre cruzarán 2 personas (acción "mover") y si se produce desde la derecha, siempre será 1 persona la cruce (accion "volver").Con esto, una acción se compone del tipo de movimiento, y la personas o personas que se desplazan. Resultados        Al realizar una accion, comprobamos el tipo de movimiento (mover o volver) y cambiamos a la persona o personas de la lista en la que estaban (izquierda o derecha del puente) a la lista contraria. Además, cambiamos de posición a la linterna y restamos el tiempo consumido y devolvemos el estado resultante. HeurísticaHemos realizado pruebas con 3 heurísticas diferentes. Heurística 1:La primera heurística que realizamos devuelve valores que tienen que ver con la longitud del vector de personas que se encuentran a la izquierda del puente, siendo longitud*2-1 si la linterna se encuentra a la izquierda o longitud*2 si la linterna se encuentra a la derecha Heurística 2:Esta heurística recorre el vector ordenado de personas disponibles en el lado izquierdo del puente y lo recorre cogiendo personas en parejas, sumando al valor a devolver el tiempo del que más tarda de la pareja. Heurística 3:Esta última heurística, devuelve la suma de los n/2 personas del vector de longitud n que más tardan en cruzar el puente.<jupyter_code>Personas = {1:10, 2:30, 3:60, 4:80, 5:120}

estadoInicial = (("Izq", 300),
                 (1, 2, 3, 4, 5),
                 ())

otroEstado = (("Der", 270),
                 (3, 4, 5),
                 (1, 2))

class ProblemaLinterna(Problem):
    def __init__(self, initial, goal=None):
        Problem.__init__(self, initial, goal)
        
    def actions(self, s):

        linterna, ladoIzq, ladoDer = s
        acciones = []

        if linterna[0] == "Izq":
            for x in ladoIzq:
                for y in ladoIzq:
                    if x != y and linterna[1] >= max([Personas[x], Personas[y]]):
                        acciones.append(("Mover", (x, y)))

        else:
            for x in ladoDer:
                if linterna[1] >= Personas[x]:
                    acciones.append(("Volver", x))

        return acciones
        
    def result(self, s, a):
        linterna, ladoIzq, ladoDer = s
        listaIzq = list(ladoIzq)
        listaDer = list(ladoDer)
        sitio, duracion = linterna
        
        if a[0] == "Mover":
            x, y = a[1]
            listaIzq.remove(a[1][0])
            listaIzq.remove(a[1][1])
            listaDer.append(a[1][0])
            listaDer.append(a[1][1])
            sitio = "Der"
            duracion -= max([Personas[x], Personas[y]])
        else:
            listaIzq.append(a[1])
            listaDer.remove(a[1])
            sitio = "Izq"
            duracion -= Personas[a[1]]
        
        return(sitio, duracion), tuple(listaIzq), tuple(listaDer)
        
    def goal_test(self, s):
        return len(s[1]) == 0 and len(s[2]) == 5

    def h(self, s):
        linterna, a, b = s.state
        sincruzar = len(a)
        if linterna[0] == 'Izq':
            return sincruzar + (sincruzar -1)
        else:
            if sincruzar == 0:
                return 0
            else:
                return sincruzar *2
        """ HEURISTICA 2
        suma = 0
        vector = list(s.state[1])
        vector.sort(reverse=True)
        while len(vector) >= 2:
            aux1 = vector.pop(0)
            aux2 = vector.pop(0)
            suma += max(Personas[aux1], Personas[aux2])
        if len(vector) == 1:
            suma += Personas[vector[0]]
        return suma  
        """
        
        """ HEURISTICA 3
        suma = 0
        vector = list(s.state[1])
        print(vector)
        vector.sort()
        inicio = len(vector)/2
        for i in range(inicio, len(vector)):
            suma += Personas[vector[i]]
        return suma
        """
pL = ProblemaLinterna(estadoInicial)
pL.initial
pL.actions(pL.initial)
pL.result(pL.initial, ("Mover", (1,2)))<jupyter_output><empty_output><jupyter_text>Pruebas con 5 personasEn primer lugar, probamos la configuración del problema compuesto por 5 personas y 5 minutos de tiempo de batería.Como se puede observar a continuación, el algoritmo A* con la primera heurística definida ha encontrado solución en un tiempo muy reducido.También probamos la búsqueda en anchura, que nos ha dado un buen resultado.Con esto sabemos, que el planteamiento del problema es correcto (acciones, resultados de las acciones, etc.) para poder probar otras configuraciones.<jupyter_code>%%time

astar_search(ProblemaLinterna(estadoInicial)).solution()
%%time

breadth_first_tree_search(ProblemaLinterna(estadoInicial)).solution()
pL = ProblemaLinterna(otroEstado)
pL.initial
pL.actions(pL.initial)<jupyter_output><empty_output><jupyter_text>Planteamiento 2 del problemaEn esta ocasión, configuramos el problema con un tiempo de 25 minutos y 10 personas (el tiempo es más que de sobra) con la segunda heurística<jupyter_code>Personas = {1:10, 2:20, 3:30, 4:40, 5:50, 6:60, 7:70, 8:80, 9:120, 10:120}

estadoInicial = (("Izq", 1500),
                 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10),
                 ())

class ProblemaLinterna2(Problem):
    def __init__(self, initial, goal=None):
        Problem.__init__(self, initial, goal)
        
    def actions(self, s):

        linterna, ladoIzq, ladoDer = s
        acciones = []

        if linterna[0] == "Izq":
            for x in ladoIzq:
                for y in ladoIzq:
                    if x != y and linterna[1] >= max([Personas[x], Personas[y]]):
                        acciones.append(("Mover", (x, y)))

        else:
            for x in ladoDer:
                if linterna[1] >= Personas[x]:
                    acciones.append(("Volver", x))

        return acciones
        
    def result(self, s, a):
        linterna, ladoIzq, ladoDer = s
        listaIzq = list(ladoIzq)
        listaDer = list(ladoDer)
        sitio, duracion = linterna
        
        if a[0] == "Mover":
            x, y = a[1]
            listaIzq.remove(a[1][0])
            listaIzq.remove(a[1][1])
            listaDer.append(a[1][0])
            listaDer.append(a[1][1])
            sitio = "Der"
            duracion -= max([Personas[x], Personas[y]])
        else:
            listaIzq.append(a[1])
            listaDer.remove(a[1])
            sitio = "Izq"
            duracion -= Personas[a[1]]
        
        return(sitio, duracion), tuple(listaIzq), tuple(listaDer)
        
    def goal_test(self, s):
        return len(s[1]) == 0 and len(s[2]) == 5

    def h(self, s):
        """ HEURÍSTICA 1
        linterna, a, b = s.state
        sincruzar = len(a)
        if linterna[0] == 'Izq':
            return sincruzar + (sincruzar -1)
        else:
            if sincruzar == 0:
                return 0
            else:
                return sincruzar *2
        """
        
        """ HEURISTICA 2 """
        suma = 0
        vector = list(s.state[1])
        vector.sort(reverse=True)
        while len(vector) >= 2:
            aux1 = vector.pop(0)
            aux2 = vector.pop(0)
            suma += max(Personas[aux1], Personas[aux2])
        if len(vector) == 1:
            suma += Personas[vector[0]]
        return suma  
        
        """ HEURISTICA 3
        suma = 0
        vector = list(s.state[1])
        print(vector)
        vector.sort()
        inicio = len(vector)/2
        for i in range(inicio, len(vector)):
            suma += Personas[vector[i]]
        return suma
        """
pL2 = ProblemaLinterna2(estadoInicial)
pL2.initial
pL2.actions(pL2.initial)<jupyter_output><empty_output><jupyter_text>Pruebas de diferentes algoritmosAl haber aumentado el número de personas, aumenta el fáctor de ramificación y la profundidad, lo que hace que el problema sea mucho más complejo.Hemos detenido la ejecución cuando cada una de las siguientes llevaba un tiempo superior a 12 horas (el algoritmo A* ha estado ejecutándose durante 22 horas). Sabemos que el problema tiene solución, puesto que el tiempo es más que de sobra para completar el problema y la solución previa con otra configuración era correcta.Un factor que puede ser concluyente de por qué no termina la ejecución puede deberse a que la heurística no sea correcta o no sea eficiente.<jupyter_code>%%time

astar_search(ProblemaLinterna2(estadoInicial)).solution()
breadth_first_tree_search(ProblemaLinterna2(estadoInicial)).solution()
breadth_first_graph_search(ProblemaLinterna2(estadoInicial)).solution()<jupyter_output><empty_output><jupyter_text>Planteamiento 3 del problemaEn esta ocasión, se plantea un problema de 7 personas (para que sea más reducido que la anterior configuración pero aumente la complejidad respecto a la inicial de 5 personas).Probamos nuevamente con la segunda heurísticaAdemás, en los siguientes planteamientos hemos probado únicamente el algoritmo A* ya que será mucho más eficiente que la búsqueda en anchura o la búsqueda en profundidad.Al final del notebook comentamos los resultados.<jupyter_code>Personas = {1:10, 2:20, 3:30, 4:40, 5:50, 6:60, 7:70}

estadoInicial = (("Izq", 500),
                 (1, 2, 3, 4, 5, 6, 7),
                 ())

class ProblemaLinterna3(Problem):
    def __init__(self, initial, goal=None):
        Problem.__init__(self, initial, goal)
        
    def actions(self, s):

        linterna, ladoIzq, ladoDer = s
        acciones = []

        if linterna[0] == "Izq":
            for x in ladoIzq:
                for y in ladoIzq:
                    if x != y and linterna[1] >= max([Personas[x], Personas[y]]):
                        acciones.append(("Mover", (x, y)))

        else:
            for x in ladoDer:
                if linterna[1] >= Personas[x]:
                    acciones.append(("Volver", x))

        return acciones
        
    def result(self, s, a):
        linterna, ladoIzq, ladoDer = s
        listaIzq = list(ladoIzq)
        listaDer = list(ladoDer)
        sitio, duracion = linterna
        
        if a[0] == "Mover":
            x, y = a[1]
            listaIzq.remove(a[1][0])
            listaIzq.remove(a[1][1])
            listaDer.append(a[1][0])
            listaDer.append(a[1][1])
            sitio = "Der"
            duracion -= max([Personas[x], Personas[y]])
        else:
            listaIzq.append(a[1])
            listaDer.remove(a[1])
            sitio = "Izq"
            duracion -= Personas[a[1]]
        
        return(sitio, duracion), tuple(listaIzq), tuple(listaDer)
        
    def goal_test(self, s):
        return len(s[1]) == 0 and len(s[2]) == 5

    def h(self, s):
        """ HEURÍSTICA 1
        linterna, a, b = s.state
        sincruzar = len(a)
        if linterna[0] == 'Izq':
            return sincruzar + (sincruzar -1)
        else:
            if sincruzar == 0:
                return 0
            else:
                return sincruzar *2
        """
        
        """ HEURISTICA 2 """
        suma = 0
        vector = list(s.state[1])
        vector.sort(reverse=True)
        while len(vector) >= 2:
            aux1 = vector.pop(0)
            aux2 = vector.pop(0)
            suma += max(Personas[aux1], Personas[aux2])
        if len(vector) == 1:
            suma += Personas[vector[0]]
        return suma  
        
        """ HEURISTICA 3
        suma = 0
        vector = list(s.state[1])
        print(vector)
        vector.sort()
        inicio = len(vector)/2
        for i in range(inicio, len(vector)):
            suma += Personas[vector[i]]
        return suma
        """
pL3 = ProblemaLinterna3(estadoInicial)
pL3.initial
pL3.actions(pL3.initial)
%%time

astar_search(ProblemaLinterna3(estadoInicial)).solution()<jupyter_output><empty_output><jupyter_text>Nuevamente probamos la misma configuración anterior, pero esta vez con la tercera heurística planteada<jupyter_code>#PROBLEMA DE CRUZAR EL PUENTE CON LA LINTERNA

Personas = {1:10, 2:20, 3:30, 4:40, 5:50, 6:60, 7:70}

estadoInicial = (("Izq", 700),
                 (1, 2, 3, 4, 5, 6, 7),
                 ())

class ProblemaLinterna3(Problem):
    def __init__(self, initial, goal=None):
        Problem.__init__(self, initial, goal)
        
    def actions(self, s):

        linterna, ladoIzq, ladoDer = s
        acciones = []

        if linterna[0] == "Izq":
            for x in ladoIzq:
                for y in ladoIzq:
                    if x != y and linterna[1] >= max([Personas[x], Personas[y]]):
                        acciones.append(("Mover", (x, y)))

        else:
            for x in ladoDer:
                if linterna[1] >= Personas[x]:
                    acciones.append(("Volver", x))

        return acciones
        
    def result(self, s, a):
        linterna, ladoIzq, ladoDer = s
        listaIzq = list(ladoIzq)
        listaDer = list(ladoDer)
        sitio, duracion = linterna
        
        if a[0] == "Mover":
            x, y = a[1]
            listaIzq.remove(a[1][0])
            listaIzq.remove(a[1][1])
            listaDer.append(a[1][0])
            listaDer.append(a[1][1])
            sitio = "Der"
            duracion -= max([Personas[x], Personas[y]])
        else:
            listaIzq.append(a[1])
            listaDer.remove(a[1])
            sitio = "Izq"
            duracion -= Personas[a[1]]
        
        return(sitio, duracion), tuple(listaIzq), tuple(listaDer)
        
    def goal_test(self, s):
        return len(s[1]) == 0 and len(s[2]) == 5

    def h(self, s):
        """ HEURÍSTICA 1
        linterna, a, b = s.state
        sincruzar = len(a)
        if linterna[0] == 'Izq':
            return sincruzar + (sincruzar -1)
        else:
            if sincruzar == 0:
                return 0
            else:
                return sincruzar *2
        """
        
        """ HEURISTICA 2
        suma = 0
        vector = list(s.state[1])
        vector.sort(reverse=True)
        while len(vector) >= 2:
            aux1 = vector.pop(0)
            aux2 = vector.pop(0)
            suma += max(Personas[aux1], Personas[aux2])
        if len(vector) == 1:
            suma += Personas[vector[0]]
        return suma  
        """
        """ HEURISTICA 3 """
        suma = 0
        vector = list(s.state[1])
        vector.sort()
        inicio = int(len(vector)/2)
        for i in range(inicio, len(vector)):
            suma += Personas[vector[i]]
        return suma
pL3 = ProblemaLinterna3(estadoInicial)
pL3.initial
pL3.actions(pL3.initial)
%%time

astar_search(ProblemaLinterna3(estadoInicial)).solution()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09668276296451817, 'fraction_numerical': 0.020365315977325216, 'mean_word_length': 2.2647361206305687, 'pattern_counts': {'":': 8, '<': 32, '<?xml version=': 0, '>': 44, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '648538', 'license': 'MIT', 'n_tokens_mistral': 6363, 'n_tokens_neox': 6105, 'n_words': 1931, 'path': 'Practica1/Practica1_IV_Puente.ipynb', 'repo_name': 'gonzalofdv/SI20-21', 'size': '19100'}