Java Brauchen Sie Hilfe eines Algorithmus Implementierung

Question

Diese Algorithmus für meine grundlegenden Programmierkenntnisse so weit fortgeschritten ist, dass ich nicht nur sehen, wie ich es umsetzen konnte. Ich poste diese in einer neuen Frage, weil ich nicht halten kann den Kerl stört, der mir den Algorithmus allein darüber im Kommentarbereich in der vorherigen Frage gab.

MaxSet(node) = 1 if "node" is a leaf
MaxSet(node) = Max(1 + Sum{ i=0..3: MaxSet(node.Grandchildren[i]) },  
                       Sum{ i=0..1: MaxSet(node.Children[i])      })

Danke zu mehrdad für den Algorithmus.

Das Problem für mich ist es, den Teil der beiden Summenleitungen zu implementieren, wie ich das tun kann? Und ich brauche jeden Knoten, dass dieser Algorithmus wählt zu markieren. Es ist nur ein „markiert“ Variable in der Knotenklasse auf true eingestellt. Ich verstehe nicht, waren sie eine Entscheidung trifft, einen Knoten zu wählen?

EDIT meinen Code enthalten, so weit:

public int maxSet(Posisjon<E> bt){
        if (isExternal(bt)){
            return 1; 
        }
        return Math.max(1 + helper1(bt), helper2(bt));
    }

private int helper1(Posisjon<E> node){
    int tmp = 0; 
    if (hasLeft(node)){
        if(hasLeft((Position<E>)node.leftChild())){
            tmp += maxSet(node.leftChild().leftChild());
        }
        if(hasRight((Position<E>)node.leftChild())){
            tmp += maxSet(node.leftChild().rightChild());
        }
    }
    if(hasRight(node)){
        if(hasLeft((Position<E>)node.rightChild())){
            tmp += maxSet(node.leftChild().leftChild());
        }
        if(hasRight((Position<E>)node.rightChild())){
            tmp += maxSet(node.leftChild().rightChild());
        }
    }
    return tmp; 
}
private int helper2(Posisjon<E> node){
    int tmp = 0; 
    if(hasLeft(node)){
        tmp +=maxSet(node.leftChild());
    }
    if(hasRight(node)){
        tmp +=maxSet(node.rightChild());
    }
    return tmp; 
}

Dies scheint zu funktionieren, was jetzt bleibt. Ist tatsächlich die Knoten zu markieren, wie gewählt? Wäre, würde ich das tun?

---

Aktualisiert mit Code:

public ArrayList<Posisjon<E>> getSelectionSet(Posisjon<E> bt, ArrayList<Posisjon<E>> s){
        if(bt.marked){
            s.add(bt);
        }
        if(hasLeft(bt)){
            if(hasLeft(bt.leftChild())){
                getSelectionSet(bt.leftChild().leftChild(),s);
            }
            if(hasRight(bt.leftChild())){
                getSelectionSet(bt.leftChild().rightChild(),s);
            }
        }
        if(hasRight(bt)){
            if(hasLeft(bt.rightChild())){
                getSelectionSet(bt.rightChild().leftChild(),s);
            }
            if(hasRight(bt.rightChild())){
                getSelectionSet(bt.rightChild().rightChild(),s);
            }
        }
        return s; 
    }

public int maxSet(Posisjon<E> bt){
        if (bt.visited){
            return bt.computedMax; 
        }
        bt.visited = true; 
        int maxIfCurrentNodeIsSelected = 1 + helper1(bt);
        int maxIfCurrentNodeIsNotSelected = helper2(bt);
        if (maxIfCurrentNodeIsSelected > maxIfCurrentNodeIsNotSelected){
            bt.marked = true; 
            bt.computedMax = maxIfCurrentNodeIsSelected; 
        }else{
            bt.marked = false; 
            bt.computedMax = maxIfCurrentNodeIsNotSelected; 
        }
        return maxSet(bt);
    }

Nach Vorlage, werde ich den gesamten Code für diesen Beitrag!

Answer 1

Sie haben noch nicht den Rückgabewert der Funktion jedes Mal hat memoize. Jedes Mal, wenn Sie maxSet anrufen, sollten Sie überprüfen, ob Sie bereits das Ergebnis oder nicht berechnet worden. Wenn Sie haben, schicken Sie es einfach. Wenn Sie berechnen es nicht und speichern Sie es irgendwo. Andernfalls wird Ihr Algorithmus ineffizient sein. (Dieser Ansatz wird als "Dynamic Programming". Erfahren Sie mehr über sie.)

// pseudocode:
public int maxSet(Posisjon<E> bt){
    if (visited[bt])
        return computedMax[bt];

    visited[bt] = true;        

    // You don't need to manually check for being a leaf
    // For leaves 'maxIfCurrentNodeIsSelected' is always larger.
    int maxIfCurrentNodeIsSelected = 1 + helper1(bt);
    int maxIfCurrentNodeIsNotSelected = helper2(bt);

    if (maxIfCurrentNodeIsSelected > maxIfCurrentNodeIsNotSelected) {
         shouldSelect[bt] = true;
         computedMax[bt] = maxIfCurrentNodeIsSelected;
    } else {
         shouldSelect[bt] = false;
         computedMax[bt] = maxIfCurrentNodeIsNotSelected;
    }
}

public Set getSelectionSet(Posisjon<E> bt, Set s) {
    if (shouldSelect[bt]) {
        s.Add(bt);

        // You should check for nulls, of course
        getSelectionSet(bt.leftChild.leftChild, s);
        getSelectionSet(bt.leftChild.rightChild, s);
        getSelectionSet(bt.rightChild.leftChild, s);
        getSelectionSet(bt.rightChild.rightChild, s);
    } else {
        getSelectionSet(bt.leftChild, s);
        getSelectionSet(bt.rightChild, s);
    }
    return s;
}

Aufruf getSelectionSet mit dem Wurzelknoten und einem leeren Set als Argument, nachdem Sie genannt maxSet.