1

这个算法对于我的基本编程技能来说是如此先进，以至于我只是不知道如何实现它。我将其发布在一个新问题中，因为我不能一直打扰在上一个问题的评论部分中单独给我算法的人。

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

也感谢mehrdad的算法。

对我来说，这里的问题是实现两条总和线的一部分，我该怎么做？我需要标记这个算法选择的每个节点。它只是节点类中设置为 true 的“标记”变量。我不明白它是否也做出了选择节点的决定？

编辑以包括我的代码到目前为止：

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

这似乎有效，现在还剩下什么。是否实际上将节点标记为已选择？我会那样做吗？

更新了代码：

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

提交后，我将发布整个代码！

4

1 回答 1

3

你目前没有记住每次函数的返回值。每次调用时maxSet，都应该检查是否已经计算了结果。如果有，就退货吧。如果您还没有计算它并将其存储在某个地方。否则，您的算法将效率低下。（这种方法称为“动态编程”。了解一下。）

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

调用getSelectionSet后使用根节点和一个空Set作为参数调用maxSet.

于 2009-10-15T12:01:04.283 回答