Java 需要帮助实现算法

Question

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

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

提交后，我会贴出整个代码!

Answer 1

您目前没有每次都记住函数的返回值。每次调用 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;
}

在调用 maxSet 之后，使用根节点和一个空的 Set 作为参数调用 getSelectionSet。