Processus de réflexion pour résoudre les problèmes de programmation dynamique basée sur les arbres

cs.stackexchange https://cs.stackexchange.com/questions/119707

Question

J'ai beaucoup de mal à comprendre les problèmes DP basés sur les arbres.Je suis assez à l'aise avec les problèmes DP basés sur les tableaux, mais je n'arrive pas à trouver le processus de réflexion correct pour les problèmes basés sur les arbres et j'espérais que quelqu'un pourrait expliquer son processus de réflexion.

Je parlerai de mon processus de réflexion derrière les problèmes basés sur les tableaux, puis j'expliquerai mes problèmes avec les problèmes DP basés sur les arbres.

Mon processus de réflexion sur les problèmes de tableau

La façon dont je pense à DP dans les problèmes basés sur les tableaux est la suivante.Considérons un problème comme Somme minimale du chemin.Ici, l'objectif est d'obtenir des positions en haut à gauche vers en bas à droite dans une matrice de telle sorte que nous minimisons le coût du chemin.Nous ne pouvons que nous déplacer à gauche et à droite.

La façon dont j'aborderais des problèmes comme celui-ci est la suivante :

  • Je construirais d’abord une récurrence.Dans ce cas la récurrence est la suivante

La récurrence est :

f(i, j) = a[i][j] // if i == m and j == n
f(i, j) = a[i][j] + f(i, j+1) // if i == m
f(i, j) = a[i][j] + f(i+1, j) // if j == n
f(i, j) = a[i][j] + Math.min( f(i, j+1), f(i+1, j) ) // Otherwise

  • Ensuite, je regarde les équations qui me disent que le problème peut être résolu en utilisant DP car il y a des sous-problèmes qui se chevauchent. f(i+1, j) and f(i, j+1).Il existe également une sous-structure optimale.

  • Je peux également déterminer la complexité temps/espace simplement en regardant la récurrence.

    • Parce que nous devons calculer tous les états qui sont tous des paires (i, j) et parce que le temps par état est O(1) (en ajoutant a[i][j] au résultat), la complexité temporelle est O(n^2).
    • En regardant la récurrence, je ne dépend que de i+1 et non de i+2, i+3...de même j ne dépend que de j+1 et non de j+2, j+3...nous pouvons donc nous en sortir en utilisant seulement 1 ligne supplémentaire (soit i+1 ou j+1) au lieu de la matrice entière, donc la complexité spatiale est O(n).

Par conséquent, je proposerais une solution temporelle n ^ 2 et n spatiale.Je peux le faire sans aucun problème.

Mon processus de réflexion pour les problèmes d'arbres

Cependant, j'ai du mal à appliquer le même processus de réflexion aux problèmes DP basés sur les arbres.A titre d'exemple, considérons le problème Diamètre de l'arbre binaire où l'objectif est de trouver le chemin le plus long entre 2 nœuds quelconques de l'arborescence.

Je peux trouver une récurrence pour ce problème qui est la suivante :

f(n) = 0 // if n == null
f(n) = max( 1+height(n.left) + height(n.right),         // longest path passing through root
            f(n.left),                                  // longest path in left subtree
            f(n.right) )                                // longest path in right subtree

Parce que f(n.left) par exemple est calculé en faisant 1+height(n.left.left) + height(n.left.right) Je peux dire que DP doit être utilisé.

Mon approche serait donc de créer un cache de taille « n » qui stocke toutes les hauteurs des nœuds.La complexité spatiale serait donc O(n).

Cependant, la solution optimale de ce problème a une complexité spatiale de O(1) et j'ai du mal à comprendre cela simplement en regardant la récurrence.Comment la récurrence vous indique-t-elle que la complexité de l'espace peut être réduite et que l'espace O(1) est suffisant et que O(n) n'est pas nécessaire ?Comment savoir quelle(s) valeur(s) stocker dans ce cas ?Dans les problèmes basés sur des tableaux, je peux obtenir les réponses à ces deux questions simplement en regardant la récurrence, mais pour les dp basés sur des arbres, ce n'est pas si évident pour moi.

Mes questions:

  1. Que pouvez-vous dire de ce problème simplement en regardant la récurrence du problème de l’arbre ?En mettant de côté ma propre réflexion, si je vous donnais cette récurrence et rien d'autre, à quelles conclusions parviendriez-vous et comment écririez-vous le programme ?Je suis curieux de connaître votre processus de réflexion.

  2. Pour les problèmes basés sur des tableaux, je peux dire simplement en regardant la récurrence à la fois la quantité d'espace dont j'avais besoin pour résoudre le problème ET ce que je devais exactement stocker (je dois stocker les valeurs de la ligne i+1 dans la somme minimale du chemin et rien d'autre).Comment puis-je faire la même chose pour le problème de l'arbre ?

Merci.

Était-ce utile?

La solution

question 1

La raison pour laquelle son espace O(1) et non O(n) se résume de haut en bas par rapport à de bas en haut.

Considérons d'abord le problème basé sur un tableau - somme minimale du chemin.

Si vous le faites de haut en bas, vous aurez besoin d'un espace O(n^2).N'oubliez pas que lorsque vous effectuez une mémorisation descendante, tous les résultats d'état doivent être stockés - il s'agit essentiellement d'une simple récursion avec mise en cache.

Cependant, lorsque vous procédez de manière ascendante, vous construisez la solution.Seuls les résultats d’état nécessaires pour passer à l’état suivant sont requis.Ainsi, dans le cas d'une somme de chemin minimale, seuls les états dans (i+1, j) sont nécessaires pour construire les états dans (i, j).Nous pouvons écarter le reste des États.

C'est pourquoi, lorsque vous procédez de bas en haut, vous pouvez réduire la complexité de l'espace à O(n).

Pour le problème de l'arbre, ce que vous avez décrit est l'approche descendante.Pour la solution que vous souhaitez, vous avez besoin d’une approche ascendante.

Approche descendante pour le problème de l'arbre

Ce que vous avez là-bas est une traversée de précommande.Cela peut être considéré comme la même chose que la DP descendante ou la mémorisation.Et comme nous l'avons vu dans l'exemple ci-dessus, pour utiliser le DP descendant, tous les résultats d'état doivent être stockés dans le cache.

Ici, les états qui vous intéressent sont les hauteurs des nœuds, donc la hauteur de chaque nœud doit être stockée, ce qui rend la complexité du stockage des états jusqu'à O(n).

Pensez donc à la façon dont le problème de l'arborescence serait implémenté de haut en bas - vous avez toutes les hauteurs dans un cache et vous l'appelez chaque fois que vous avez besoin d'accéder à la hauteur d'un nœud.

Ainsi, chaque fois que vous arrivez à un nœud, vous utilisez le cache pour obtenir les hauteurs, puis vous effectuez une arithmétique simple en temps constant pour obtenir le diamètre.Dans ce cas, cette arithmétique est height[n.left] + height[n.right].

De haut en bas est simplement une récursion avec mise en cache, donc pour la variante descendante, vous stockez uniquement les hauteurs pour obtenir une taille de cache de O(n).Le code est comme suit:

Map<TreeNode, Integer> dp = new HashMap<>();

public int diameterOfBinaryTree(TreeNode root) {
    if(root == null)
        return 0;
    else
        return Math.max(
            height(root.left, dp)+height(root.right, dp),
            Math.max( diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right) )
        );
}

private int height(TreeNode root, Map<TreeNode, Integer> dp) {
    if(dp.containsKey(root))
        return dp.get(root);

    if(root == null)
        return 0;
    else
        dp.put(root, 1 + Math.max(height(root.left, dp), height(root.right, dp)) );

    return dp.get(root);
}

Approche ascendante pour le problème des arbres

L'approche ascendante de tout problème d'arborescence utilise le parcours post-commande au lieu du parcours pré-commande.Nous construisons le parcours post-ordre pour calculer les états que nous voulons stocker dans le cache - dans ce cas, il s'agit de la hauteur.

Puisque nous calculons les enfants avant de calculer le nœud actuel, pour chaque nœud que nous visitons, nous disposons de la taille des enfants.Puisque les hauteurs des nœuds nous sont disponibles, pour un nœud donné, nous disposons également du diamètre passant par ce nœud pendant que nous traitons le nœud.

Donc, si nous voulons le diamètre maximum, nous devons simplement calculer le diamètre du nœud actuel, puis le comparer avec le diamètre maximum vu jusqu'à présent - nous faisons cela pour tous les nœuds.Tout cela se fait au sein d’un seul parcours post-ordre de l’arbre.

Le code est comme suit:

int maxDiameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    postorderHeight(root);
    return maxDiameter;
}

private int postorderHeight(TreeNode root) {
    if(root == null)
        return 0;
    int leftSubtreeHeight = postorderHeight(root.left);
    int rightSubtreeHeight = postorderHeight(root.right);
    
    maxDiameter = Math.max(maxDiameter, leftSubtreeHeight + rightSubtreeHeight);
    
    return 1 + Math.max(leftSubtreeHeight, rightSubtreeHeight);
}

Techniquement, la complexité spatiale est proportionnelle à la taille de la pile de récursion, mais la taille du cache est constante.

question 2

Demandez-vous si les états que vous devez stocker peuvent être réduits si vous procédez de bas en haut (post-commande).Si oui, faites-le - dans ce cas, oui, nous pouvons obtenir des hauteurs gratuitement si nous utilisons la commande postale.

Autres conseils

Je ne sais pas si cela aide, mais j'ai aussi beaucoup eu du mal avec les problèmes de DP sur les arbres, et ce qui m'a aidé a été de considérer d'abord des problèmes plus simples et de faire vraiment un tas d'exercices de ce type.Il est également très utile de les programmer (par exemple) en Python afin d'acquérir une expérience pratique.

Alors, peut-être est-il préférable de commencer par un problème d'arbre plus simple, comme la couverture de sommet (pondérée) ou l'ensemble indépendant (pondéré) ?

Dans ces deux cas (ils sont similaires, mais concentrons-nous sur la couverture du sommet), la solution entière d'un sous-arbre peut être résumé à la racine du sous-arbre avec deux nombres:la solution optimale si la racine du sous-arbre est dans la couverture du sommet et la solution optimale si la racine du sous-arbre est pas dedans le couvercle du sommet (mais couvert par le bas).

Le plan est donc de stocker, pour chaque nœud $u$, deux nombres, $u_{ ext{in}} = c_i$et $u_{ ext{in}} = c_o$, et à la fin, nous examinerons quelles sont les valeurs du nœud racine $r$, c'est à dire. $r_{ ext{in}}$ et $r_{ ext{out}}$.

L'algorithme

L'algorithme est alors assez simple.Pour le cas de base, en commençant par les feuilles, dans le nœud feuille $v$, vous stockez $v_{ ext{in}} = w(v)$ et $v_{ ext{out}} = 0$.De toute évidence, dans le sous-arbre avec un seul nœud, il n’y a pas d’arêtes à couvrir, c’est donc assez simple.

Ensuite, le reste de l'algorithme reçoit un nœud $v$ avec des enfants $u_1, \dots, u_d$, nous devons calculer deux cas.

  1. $v$ est dans la couverture du sommet :alors la solution optimale est $v_{ ext{in}} = w(v) + \sum_{u \in u_1 \dots u_d} \min(u_{ ext{in}}, u_{ ext{out}})$
  2. $v$ est pas dedans la couverture du sommet, donc tous les enfants doivent être, ainsi $v_{ ext{out}} = \sum_{u \in u_1 \dots u_d} u_{ ext{in}}$

Maintenant, la seule chose que nous devons faire est de renvoyer le résultat du nœud racine $r$, qui peut être soit dans ou pas dedans la couverture du sommet, donc on revient$$ \min( r_{ ext{in}}, r_{ ext{out}}) $$

En d'autres termes, nous avons découvert les informations dont nous avons besoin dans le "séparateur" d'un sous-arbre, et comment peut combiner les informations du sous-arbre avec le reste de l'arbre.

  1. Exercice:Résolvez la couverture de sommet pondérée et l’ensemble indépendant pondéré sur les arbres.
  2. Exercice 2 :Résolvez l’ensemble dominant pondéré, qui nécessite un état supplémentaire, à savoir dans l'ensemble dominant, pas dans le set dominant mais dominé, pas encore dominé (dominé d'en haut).
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top