Java Besoin d'aide pour implémenter un algorithme

Question

This algorithm est tellement avancée pour mes compétences de programmation de base que je ne vois pas comment je pourrais l'implémenter. Je poste ceci dans une nouvelle question parce que je ne peux pas continuer à déranger le type qui m'a donné l'algorithme seul à ce sujet dans la section de commentaire dans la question précédente.

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

Merci aussi mehrdad pour l'algorithme.

Le problème ici pour moi est de mettre en œuvre la partie des deux lignes de somme, comment puis-je faire cela? Et je dois marquer chaque noeud que cet algorithme choisit. C'est juste une variable "marquée" dans la classe de noeud définie sur true. Je ne comprends pas si elle prend une décision aussi choisir un nœud?

EDIT pour inclure mon code à ce jour:

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

Cela semble fonctionner, ce qui reste maintenant. Est-ce que pour marquer les noeuds comme choisis? Est-ce que je ferais ça?

---

Mise à jour avec le 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); 
    } 

Après la soumission, je vais poster le code entier pour cela!

Answer 1

Vous n'avez actuellement pas de mémoize la valeur de retour de la fonction à chaque fois. Chaque fois que vous appelez maxSet, vous devez vérifier si vous avez déjà calculé le résultat ou non. Si vous avez, renvoyez-le. Si vous ne l'avez pas calculé et stocké quelque part. Sinon, votre algorithme sera inefficace. (Cette approche est appelée « programmation dynamique. » En savoir à ce sujet.)

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

appel getSelectionSet avec le nœud racine et un Set vide comme arguments après avoir appelé maxSet.