1

This algorithm is so advanced for my basic programming skills that I just don't see how I could implement it. I'm posting this in a new question because I can't keep bothering the guy who gave me the algorithm alone about this in the comment section in the previous question. 

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])      })

Thanks too mehrdad for the algorithm.

The problem here for me is to implement the part of the two sum lines, how can I do that? And I need to mark every node that this algorithm chooses. It's just a "marked" variable in the node class set to true. I don't understand were it makes a decision too choose a node?

EDIT to include my code so far: 

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; 
}

This seems to be working, what is left now. Is to actually mark the nodes as chosen? Were would I do that?

Updated with 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);
    }

After submission, I will post the entire code for this!

Improve this question
3
  • 3
    It looks like you're just asking for a complete solution. I think you'll get better responses if you post the code you have tried yourself, and ask a specific question about it. Commented Oct 15, 2009 at 10:38
  • I'll clean up my code an post it later if this doesn't help me out. I just used two helper functions as the Sum functions. They are huge, because I also have to check that the nodes aren't null. And the part about how to store the set, were would I mark the nodes as choosen? You can just point it out in the Pseudo algorithm. Commented Oct 15, 2009 at 10:42
  • Updated with my code so far. It seems to work with counting the max and returning an int. Only tested on a tree with three elements tough. Were would I mark the nodes as chosen? Commented Oct 15, 2009 at 10:59

1 Answer 1

Reset to default
2

You currently have does not memoize the return value of the function each time. Every time you call maxSet, you should check if you have already computed the result or not. If you have, just return it. If you haven't compute it and store it somewhere. Otherwise, your algorithm will be inefficient. (This approach is called "Dynamic Programming." Learn about it.)

// 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;
}

call getSelectionSet with the root node and an empty Set as arguments after you called maxSet.

Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

Okay, I have it working now. But it's missing to add the root element when that should have been added to the set. The problem must be in the maxSet because I found out that the root element is not beeing selected. It is beeing visited. What can this come from? maxSet returns the correct amount.
data_jepp: Are you sure? Note that the result is not unique.
Hmm. For the tree 2(1(4)(5)(3)) it maxSet returns 3, and the elements 4 and 5. If maxSet returns 3, then the root 2 would also be apart of that? Here is the code now pastebin.org/45969
data_jepp: I don't understand your notation for the tree. You mean 2(1(4(5(3)))? Looking at the code...
data_jepp: Just saw your source. Your getSelectionSet is not implemented correctly.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.