J'ai du mal à comprendre le processus de réflexion nécessaire pour trouver des récurrences pour les problèmes de programmation dynamique

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

Question

Je faisais quelques problèmes de programmation dynamique et j'ai du mal à comprendre le processus de réflexion nécessaire pour trouver des récurrences.

Le premier problème que j'ai résolu était sous-chaîne palindromique la plus longue et j'ai réussi à le résoudre avec succès en utilisant la logique suivante :J'ai une fonction f(i,j) qui renvoie la sous-chaîne palindromique la plus longue entre les caractères aux positions i,j dans la chaîne.J'ai trouvé la récurrence suivante :

f(i,j) = true // if(s[i] = s[j])
f(i,j) = true // if(i>j) 
f(i,j) = true // if(s[i] = s[j] and f(i+1, j-1) == true)
f(i,j) = false // otherwise

Grâce à cette récurrence, j'ai réussi à résoudre le problème avec succès.

Le deuxième problème que je voulais résoudre était Parenthèses valides les plus longues (ce que je veux faire en utilisant DP et non des piles).La question est:Étant donné une chaîne contenant uniquement les caractères '(' et ')', recherchez la longueur de la sous-chaîne de parenthèses valides la plus longue.

Mon processus de réflexion initial était que cela était similaire au problème de sous-chaîne palindromique le plus long que j'ai déjà résolu.J'ai donc défini f(i,j) comme une fonction qui renvoie la parenthèse valide la plus longue entre les éléments i,j.La récurrence que j'ai trouvée est la suivante - j'utilise ici -1 pour indiquer que f(i,j) ne forme pas de parenthèse valide :

f(i,j) = -1 // if i == j
f(i,j) = -1 // if j=i+1 and ! (s[i] = '(' and s[j] = ')')
f(i,j) = 2 // if j = i+1 and s[i] = '(' and s[j] = ')'
f(i,j) = 2 + f(i+1, j-1) if s[i] = '(' and s[j] = ')' and f(i+1, j-1) > 0;
f(i,j) = -1 // otherwise

Mon code (écrit en Java) pour la version descendante de ce qui précède est (remarque :dp[][] a été initialisé à -2 indiquant que l'état i,j n'est pas encore traité) :

private int topDown(String s, int i, int j, int[][] dp) {
    if(dp[i][j] != -2)
        return dp[i][j];

    if(i == j)
        dp[i][j] = -1;
    else if(j == i+1 && (s.charAt(i) != '(' || s.charAt(j) != ')' ) )
        dp[i][j] = -1;
    else if(j == i+1 && (s.charAt(i) == '(' && s.charAt(j) == ')' ) )
        dp[i][j] = 2;
    else if(s.charAt(i) == '(' && s.charAt(j) == ')' && topDown(s, i+1, j-1, dp) > -1)
        dp[i][j] = 2 + topDown(s, i+1, j-1, dp);
    else
        dp[i][j] = -1;

    return dp[i][j];
}

Cela ne fonctionne pas pour les entrées comme ()() car il renverra 2 au lieu de 4.

Je n'ai pas réussi à trouver une solution moi-même, alors j'ai cherché en ligne.j'ai trouvé une solution ici.

Dans ce cas, l'auteur définit f(i) comme la longueur de la plus longue sous-chaîne de parenthèses équilibrées valides qui commence à l'index i.Il décrit ensuite la récidive comme suit :

f(i) = 2 + f(i+2)   // if s[i] = "(" and s[i+1] = ")"
f(i) = f(i+1) + f(i + f(i+1) + 2)   // s[i]="(" AND s[i+1]="(" AND s[i+f(i+1)+1]=")"
f(i) = 0    // otherwise

Je n'ai pas écrit/testé le code pour la récurrence mais je suppose qu'il est correct.

Mes questions sont les suivantes :

  1. Lorsque je résolvais le problème au départ, je n'avais pas pensé à l'écrire en fonction de f(i).Je n'y pensais qu'en fonction de f(i,j) et cela s'est avéré faux.Existe-t-il donc un moyen simple de savoir simplement en examinant un problème quels états doivent être calculés ?Par exemple, pourquoi ne puis-je pas résoudre le problème de sous-chaîne palindromique la plus longue en fonction de f(i) ?de même, pourquoi ne puis-je pas résoudre le problème de la parenthèse la plus longue en fonction de f(i,j) ?

  2. Existe-t-il un moyen de résoudre le problème de la parenthèse valide la plus longue en fonction de f(i,j) où f(i,j) représente la longueur de la parenthèse valide la plus longue entre i et j ?Ce n'est pas grave si la complexité d'exécution est plus élevée, je suis juste curieux à ce sujet.

Merci.

Était-ce utile?

La solution

Voici une façon de résoudre le problème des parenthèses valides les plus longues par programmation dynamique comme vous l'aviez espéré.Ou presque.

Par souci de simplicité, une chaîne est dite valide si elle est constituée de parenthèses ouvrantes et fermantes bien formées.

L'observation critique est qu'une chaîne est valide s'il s'agit d'une chaîne vide, d'une concaténation de deux chaînes valides ou de "(" suivi d'une chaîne valide suivie de ")".En fait, cette observation est la définition récursive habituelle des parenthèses ouvrantes et fermantes bien formées !Cette observation indique qu’un ensemble approprié de sous-problèmes est s[i...j].

Laisser s être la chaîne de longueur donnée L.

  • Laisser dp haricot L par L+1 tableau de booléens.
    dp[i][j] deviendra vrai si la sous-chaîne s[i,j] est valable.Ici s[i,j] signifie la sous-chaîne avec les indices de i inclusif à j exclusif, 0 <=i <= j < L.En particulier, s[i,i] signifie la chaîne vide.

  • Au départ, tout dp[i][j] sont faux.

  • Le cas de base est la chaîne vide, dp[i][i] = true pour tous i.

  • La relation de récurrence est, d'après l'observation ci-dessus, dp[i][j] = true pour i < j si s[i] == '(' et dp[i+1][j-1] == true et s[j-1] == ')' ou il y a un index k, de telle sorte que les deux dp[i][k] == true et dp[k][j] == true.On peut stipuler que i < k < j.

Voici la version descendante de l’approche ci-dessus, suivant le style de la question.

private static boolean topDown(String s, int i, int j, Boolean[][] dp) {
    if (i > j) return false;
    if (dp[i][j] != null) return dp[i][j];

    if (i == j) {
        dp[i][i] = true;
    } else {
        if (s.charAt(i) == '(' && s.charAt(j - 1) == ')' && topDown(s, i + 1, j - 1, dp)) {
            dp[i][j] = true;
        } else {
            for (int k = i + 1; k < j; k++) {
                if (topDown(s, i, k, dp) && topDown(s, k, j, dp)) {
                    dp[i][j] = true;
                }
            }
        }

    }

    if (dp[i][j] != null) {
        return true;
    } else {
        dp[i][j] = false;
        return false;
    }
}

Voici la version ascendante.Le code est un peu accéléré par l'observation qu'une chaîne ne peut être valide que lorsque sa longueur est paire. 

private static int longestValidSubstring(String s) {
    final int L = s.length();

    // isValid[i][j] is true iff s.substring(i,j) is valid.
    boolean[][] isValid = new boolean[L][L + 1];

    // empty string is valid.
    for (int i = 0; i < L; i++) {
        isValid[i][i] = true;
    }
    for (int l = 2; l <= L; l += 2) {  // l is the length
        for (int i = 0; i <= L - l; i++) {
            // determine isValid[i][i+l]
            if (s.charAt(i) == '(' && s.charAt(i + l - 1) == ')' && isValid[i + 1][i + l - 1]) {
                isValid[i][i + l] = true;
            } else {
                for (int j = 2; j < l; j += 2) {
                    if (isValid[i][i + j] && isValid[i + j][i + l]) {
                        isValid[i][i + l] = true;
                        break;
                    }
                }
            }
        }
    }

    for (int l = L & 0xfffffffe; l >= 2; l -= 2) {
        for (int i = 0; i <= L - l; i++) {
            if (isValid[i][i + l]) {
                return l;
            }
        }
    }
    return 0;
}

La version itérative devrait être plus rapide que la version descendante.Cependant, même la version itérative n’est pas assez rapide lorsque L est grand puisqu'il calcule L * L entrées, ce qui est assez grand une fois L est supérieur à 10 000.De plus, le tableau bidimensionnel isValid utilise également beaucoup de mémoire.

Ici et ici sont deux autres solutions optimisées.Je n'en discuterai pas, car ils sortent du cadre de cette réponse.

Existe-t-il un moyen de résoudre le problème des parenthèses valides les plus longues en fonction de f(i,j) où f(i,j) représente la longueur des parenthèses valides les plus longues entre i et j ?Ce n'est pas grave si la complexité d'exécution est plus élevée, je suis juste curieux à ce sujet.

La qualité fondamentale des sous-problèmes dans la programmation dynamique est que vous pouvez résoudre plus facilement un sous-problème plus important une fois que vous avez la solution au sous-problème plus petit.Vous pouvez également étendre ou combiner les solutions aux sous-problèmes plus petits pour créer une solution au problème plus vaste.

Dans ce problème particulier, si nous savons si toutes les sous-chaînes plus courtes sont valides ou non, alors il est facile de savoir qu'une sous-chaîne plus longue, légèrement plus longue, est valide ou non.D'un autre côté, si nous connaissons tous les f(i,j), qui représentent la longueur de la sous-chaîne valide la plus longue entre i et j, l'absence d'emplacement spécifique de ces sous-chaînes valides les plus longues ne nous aide pas à déterminer si une sous-chaîne d'une chaîne plus longue est valide. la sous-chaîne est valide ou non.La différence est cruciale, même si elle peut être subtile pour des yeux non avertis.Vous apprendrez à apprécier la différence.

Lorsque je résolvais le problème au départ, je n'avais pas pensé à l'écrire en fonction de f(i).Je n'y pensais qu'en fonction de f(i,j) et cela s'est avéré faux.Existe-t-il donc un moyen simple de savoir simplement en examinant un problème quels états doivent être calculés ?Par exemple, pourquoi ne puis-je pas résoudre le problème de sous-chaîne palindromique la plus longue en fonction de f(i) ?de même, pourquoi ne puis-je pas résoudre le problème de la parenthèse la plus longue en fonction de f(i,j) ?

Comme je l’ai montré ci-dessus, il n’est pas nécessairement faux d’utiliser f(i,j) même si nous devrions donner à f(i,j) une signification légèrement différente.Résoudre efficacement un problème n’est peut-être pas facile, même si l’on sait qu’il peut être résolu par programmation dynamique.Pas mal de problèmes me laissent longtemps perplexe même si je me considère expérimenté.Cela nécessite une certaine intelligence et expérience pour identifier ou formuler l’ensemble approprié de sous-problèmes (qui ne correspondent pas nécessairement à la forme exacte du problème d’origine).

Pour étendre une sous-chaîne palindromique à une sous-chaîne palindromique plus longue, vous devez l'étendre des deux côtés.Cela indique qu'il n'est peut-être pas facile de résoudre le problème de sous-chaîne palindromique la plus longue en fonction d'une seule variable qui représente l'une des extrémités de la chaîne palindromique d'une manière simple et efficace.Cependant, si l’on analyse la structure fine des palindromes, on pourrait arriver à la L'algorithme de Manacher, qui utilise essentiellement une carte à partir d'une seule variable qui représente le point central des sous-chaînes palindromiques.

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top