Construí un árbol que consta de nodos con cada nodo que tiene un atributo y una lista de sucesores. Estoy tratando de implementar una función recursiva que comienza a atravesar el árbol en un nodo dado (en este ejemplo en el nodo "Método"). La función contará el número de nodos anidados con un atributo dado. Al final, quiero devolver el número más alto encontrado dentro de una sola rama. Hablando del ejemplo dado, me gustaría encontrar la cantidad máxima de nodos anidados con el atributo "Loop" que sería 3 (la rama correspondiente está marcada en naranja).

Ejemplo: ingrese la descripción de la imagen aquí Actualmente, mi enfoque se ve así:

private static int getLNDforMethod(DirectedNodeInterface curNode, int currentLND) {

    NodeIterator successors = curNode.getSuccessors();
    while(successors.hasNext())
    {
        successors.next();
        DirectedNodeInterface curSuc = (DirectedNodeInterface) successors.getNode();

        // isLoop returns true if the given node is a loop
        if(isLoop(curSuc))
        {
            ++currentLND;
        }

        currentLND = getLNDforMethod(curSuc, currentLND);
    }

    return currentLND;
}

El problema con este enfoque es que está contando todos los bucles dentro de un árbol determinado en lugar de simplemente devolver el número máximo de una rama anidada. Entonces, en lugar de devolver 3 (que sería lo que quiero), devuelve 7 para el ejemplo dado que equivale al número total de "Loops" en todo el árbol.

Aparentemente, tengo algunos problemas para pensar en métodos recursivos. Alguien puede ayudarme?

4
MRE 17 oct. 2017 a las 18:58

3 respuestas

La mejor respuesta

Una muy buena estrategia para pensar algoritmos recursivos es asumir que ya ha implementado su algoritmo. En su caso, significa asumir que ya tiene una función que encuentra max para una sola ruta. Su implementación se reduce a llamar a la función para cada hijo (recuerde, asumimos que ya está implementada), seleccionando el máximo entre ellos, y luego devolver ese máximo o devolver el máximo más uno si nuestro nodo actual cumple la condición.

El algoritmo para encontrar el recuento máximo para una sola ruta es el siguiente:

  • Establezca max, el valor de retorno de su método, en 0
  • Establezca own, el valor agregado por el nodo actual, en 0 si el atributo deseado está ausente o en 1 si el atributo está presente en el nodo actual
  • Llame a getLNDforMethod por cada niño y obtenga childMax
  • Establezca max al máximo de max y own+childMax
  • Regresar max

Esto es más fácil de expresar en código Java:

private static int getLNDforMethod(DirectedNodeInterface curNode) {
    int max = 0;
    int own = isLoop(curNode) ? 1 : 0;
    NodeIterator successors = curNode.getSuccessors();
    while(successors.hasNext()) {
        successors.next();
        DirectedNodeInterface curSuc = (DirectedNodeInterface) successors.getNode();
        max = Math.max(max, own + getLNDforMethod(curSuc));
    }
    return max;
}
5
dasblinkenlight 17 oct. 2017 a las 16:14

Su problema es que está haciendo una búsqueda amplia sin molestarse en considerar su propio enunciado del problema. Lo que desea es la cantidad máxima de ocurrencias de LOOP en cualquier rama, pero lo que está haciendo es contar todas las ocurrencias de LOOP en todo su árbol. Puede solucionar esto transformando su búsqueda de amplitud en una búsqueda de profundidad o solo devolviendo el máximo del resultado de sus llamadas sub-recursivas.

private static int GetLNDForMethod(DirectedNodeInterface curNode) {
    NodeIterator successors = curNode.getSuccessors();
    unsigned int numLnds = 0;
    while (successors.hasNext()) {
        successors.next();
        DirectedNodeInterface curSuc = (DirectedNodeInterface) successors.getNode();

        unsigned int curLnds = GetLNDForMethod(curSuc);
        if (isLoop(curSuc))
            curLnds++;
        if (numLnds < curLnds)
            numLnds = curLnds;
    }

    return numLnds;
}

Lo que hice aquí no fue una gran modificación de su código, simplemente inserté otra variable y verifiqué si era mayor que el valor actual y configuré la primera si lo era.

Tenga en cuenta que dado que usted (y yo) solo consideramos sucesores y no examina el nodo actual, este resultado será uno inferior al resultado real si el nodo raíz es un LOOP

2
Woody1193 17 oct. 2017 a las 16:09
private static int getLNDforMethod(DirectedNodeInterface curNode) {

    int maxChild = 0;
    NodeIterator successors = curNode.getSuccessors();
    while(successors.hasNext())
    {
        successors.next();
        DirectedNodeInterface curSuc = (DirectedNodeInterface) successors.getNode();
        maxChild = Math.max(maxChild, getLNDforMethod(curSuc));
    }

    return maxChild + (isLoop(curNode) ? 1 : 0);
}
3
DAle 17 oct. 2017 a las 16:23