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にも感謝します。

ここでの問題は、2つの合計行の一部を実装することですが、どうすればそれを実行できますか？そして、このアルゴリズムが選択するすべてのノードにマークを付ける必要があります。これは、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ルート ノードと空を指定して呼び出します。SetmaxSet

于 2009-10-15T12:01:04.283 に答える