3

Estoy creando un árbol, entonces creo un nodo cuyos hijos son un vector. Se agregan unos nodos de ejemplo 0,1,2,3 y luego de ello intento buscar uno de esos nodos.

La raíz es retornada sin problemas y el nodo 1 retorna sin problemas, pero al intentar buscar el 2 o el 3 no se encuentran por que el for no es capaz de continuar.

El for solo entra 1 vez y nunca más vuelve a entrar (En el método print(t.searchForEuristicID(3)))

class Node(object):
    def __init__(self, data, childrens, euristic) -> None:
        """
        The first node by 0 the song of 0 by 1 and the new son by 3...
        """
        self.euristic = euristic # This is a numberOrder to resolve a púzzle 
        self.data = data # contain information
        self.childrens = childrens # []

class Three:
    def __init__(self) -> None:
        """
        data = puzzle status example [321875649]
        the childrens if you can mouve
        never save 2 equals childern
        childers = [<MovRight><MovDown><MovLeft><MovUP>]
        """
        self.controlList = [] # I never save 2 equal children 
        self.idControl = 0 # Unique id for every node
        self.pivot  = None # Main node 

    def addData(self, father, data):
        if self.pivot == None:
            self.pivot = Node(data, [], self.idControl)
            self.controlList.append(data)
            self.idControl = self.idControl + 1
        else:
            if data not in self.controlList:
                self._addData(self.pivot, father, data)

    def _addData(self, pivot, father, data):
        if father == pivot.data:
            pivot.childrens.append(Node(data, [], self.idControl))
            self.controlList.append(data)
            self.idControl = self.idControl + 1
        else:
            for i in pivot.childrens:
                self._addData(i, father, data)

    def searchForEuristicID(self, id):
        """
        Return a node with id
        """
        return self._searchForEuristicID(self.pivot, id)

    def _searchForEuristicID(self, node, id):
        if node.euristic == id:
            return node
        else:
            for i in node.childrens:
                return self._searchForEuristicID(i, id)

    def showThree(self):
        """
        Show all data nodes
        """
        self._showThree(self.pivot)

    def _showThree(self, pivot):
        if pivot != None:
            print("Data>",pivot.data, "Eur>",pivot.euristic, "Childs: ", len(pivot.childrens))
            for i in pivot.childrens:
                self._showThree(i)

oneShoot = [1,2,3,4,5,6,7,9,8]
t = Three()
t.addData(None, oneShoot)
t.addData(oneShoot, [1,2,3,4,5,6,9,7,8])
t.addData(oneShoot, [1,2,3,4,9,6,7,5,8])
t.addData(oneShoot, [1,2,3,4,5,6,7,8,9])

t.showThree()

print(t.searchForEuristicID(3))

El problema está en las siguiente líneas de código:

No se como hacer que el ciclo continúe y encuentre el nodo con el ID=3 ... solo entra 1 vez.

def _searchForEuristicID(self, node, id):
    if node.euristic == id:
        return node
    else:
        for i in node.childrens:
            return self._searchForEuristicID(i, id)

¿Alguien seria tan amable de explicarme?

5
  • No queda claro cual es tu dificultad: 1) No entiendes como funciona la recursión, o 2) Si entiendes la recursión, sólo te falla este código en particular. Aclara eso para poder redactar una respuesta apropiada. Edita tu pregunta para clarificarlo.
    – Candid Moe
    Commented el 12 ago. 2021 a las 19:53
  • Yo entiendo que es la recursividad... lo que no entioendo es por que el for no sigue funcionando... Para mi la solución fue la siguiente: "Que no retorne y busque por todo el arbol y al final se guarda en una variable global" Commented el 12 ago. 2021 a las 20:18
  • Para poder replicar tu ejemplo falta ver cómo inicializas oneShoot
    – abulafia
    Commented el 12 ago. 2021 a las 20:33
  • Listo... oneShoot = [1,2,3,4,5,6,7,9,8] Commented el 12 ago. 2021 a las 20:36
  • Lo que me gustaria es que me explicaran como retornar un nodo mediante un metodo recursivo. Commented el 12 ago. 2021 a las 20:36

1 respuesta 1

3

El problema, como bien has diagnosticado, se debe a que en este fragmento de código:

            for i in node.childrens:
                return self._searchForEuristicID(i, id)

el for sólo se ejecuta una vez. Claro, no puede ser de otra forma porque has puesto un return en el cuerpo del bucle. Si olvidas la recursividad, simplemente estás evaluando dentro del bucle "otra" función, y retornando inmediatamente lo que esa "otra" función te haya retornado. Esto lo haces en la primera iteración del bucle por lo que ya no iterará más.

La solución consiste en recoger el valor devuelto por esa "otra" función (aunque sea una llamada a sí misma) en una variable temporal, para después examinar esa variable. Si es diferente de None, es que esa "otra" función ha encontrado el elemento buscado, y en ese caso puedes hacer ya el return de ese resultado. En caso contrario seguirá iterando.

Para mayor claridad puedes escribir también un return None explícito si agotas el bucle sin haber encontrado nada (pues eso implica que el elemento buscado no existe). Ese return None es opcional, ya que es lo que de todas formas hará Python al llegar al final de la función sin haber retornado otra cosa.

En definitiva, queda así:

    def _searchForEuristicID(self, node, id):
        if node.euristic == id:
            return node
        else:
            for i in node.childrens:
                result = self._searchForEuristicID(i, id)
                if result is not None: 
                    return result
            return None

He probado este código y creo que ya hace lo que buscabas (aunque no estoy del todo seguro porque no comprendo bien la finalidad de este árbol y sus nodos).

5
  • Gracias por tu respuesta: Este codigo solo funciona para los ID 0 y 1... No es posible buscar 2,3... y eso ocurre por que solo busca por la izquierda. >>Lo que yo deseo hacer es crear un metodo recursivo que me retorne un nodo, y el nodo que retorna depende de un ID. Commented el 12 ago. 2021 a las 20:51
  • Entonces tendrás que explicar mejor qué se pretende. Yo he probado a buscar con ID 2 y 3 y sí que me retorna un resultado aunque debo confesar que no entiendo bíen qué se está haciendo. Si busco con id 4 no retorna ninguno, pero creo que eso es lo correcto porque en el ejemplo dado no hay ningún nodo con euristic=4 (y la búsqueda que haces se basa en comparar el id con el euristic)
    – abulafia
    Commented el 12 ago. 2021 a las 20:53
  • Si funciona... tengo que poner el return none El error fue mio... El return none es obligatorio... Si lo quito no me funciona correctamente: El programa es facil: los nodos se etiquetan por orden de entrada... y el objetivo del programa es recuperar un nodo deacuerdo al ID. Muchas gracias. Commented el 12 ago. 2021 a las 20:58
  • 2
    No entiendo qué relevancia puede tener poner o quitar ese return None, salvo que tu código no sea exactamente igual al que estamos discutiendo, sino que haga más cosas después del bucle. Si no hace nada más, la función terminará de todas formas al salir del bucle, y python siempre usa un return None implícito cuando la función finaliza. En todo caso, si esta respuesta ha resuelto tu problema, puedes marcarla como aceptada para que la pregunta aparezca como resuelta.
    – abulafia
    Commented el 12 ago. 2021 a las 21:01
  • Hola :) Gracias por ayudarme a encontrar ese nodo... ando haciendo mi primera inteligencia artificial entonces tiene muchas más cosas... el codigo que publique solo es un minimo ejemplo :) github.com/felipedelosh/ImgToPuzzleByLoko Commented el 12 ago. 2021 a las 21:14

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.