Le processus de planification dynamique est: chaque décision dépend de l'état actuel, puis l'état est transféré. Une séquence de décision est générée dans un état changeant, donc ce processus de prise de décision d'optimisation en plusieurs étapes est appelé programmation dynamique.
La programmation dynamique est en fait un terme général pour un type de sujet, pas un algorithme fixe. La signification de la programmation dynamique est de résoudre l'approche globale en adoptant des stratégies récursives (ou division et conquérir) et en résolvant les sous-problèmes de gros problèmes. L'idée principale de la programmation dynamique est de diviser intelligemment le problème en plusieurs sous-problèmes et d'obtenir la solution globale au problème en calculant les sous-problèmes. Les sous-problèmes peuvent être divisés en plus de sous-problèmes, résolvant ainsi les problèmes requis en utilisant des méthodes similaires à l'itération récursive. Description de la question:
Pour les séquences S et T, la distance entre eux est définie comme: effectuant les opérations suivantes plusieurs fois sur l'un des deux: 1, supprimez un caractère; 2, insérer un caractère; 3, changez un caractère. Chaque fois que l'opération est effectuée, le nombre est augmenté de 1. Le nombre minimum de virage S et T en séquence égale est la distance d'édition (édition) ou la similitude entre les deux. Veuillez donner l'algorithme correspondant et son implémentation.
analyser:
Supposons que les longueurs des séquences S et T sont respectivement M et N, et la distance d'édition entre eux est exprimée en édition [M] [n]. Ensuite, il y a les situations suivantes lors de l'exploitation de la séquence:
un. Lorsque les caractères finaux de S et T sont égaux, aucune des opérations de définition ci-dessus (c'est-à-dire "modifier") n'est requise pour les caractères finaux, c'est-à-dire qu'aucun décompte n'est requis. La condition est satisfaite: modifier [m] [n] = modifier [m-1] [n-1].
né Lorsque les caractères finaux de S et T ne sont pas égaux, la fin de l'un ou l'autre doit être modifiée et le nombre correspondant sera augmenté de 1.
B1, modifiez la fin de S ou T pour le rendre égal à T ou S, puis modifiez [M] [n] = modifier [M-1] [N-1] +1;
B2, supprimez l'élément à la fin de S pour rendre s et t égal, puis modifier [m] [n] = modifier [M-1] [n] +1;
B3, supprimez l'élément à la fin de T pour rendre T et S égal, puis modifiez [M] [n] = modifier [M] [N-1] +1;
B4, ajoutez l'élément de queue de t à la fin de S pour rendre S et T égal, alors la longueur de S devient m + 1, mais à ce moment, les éléments finaux de S et T sont déjà égaux. Il vous suffit de comparer les premiers éléments M de S avec les premiers éléments N-1 de T, donc modifier [m] [n] = modifier [m] [n-1] +1;
B5, ajoutez l'élément de queue de S à la fin de T pour rendre t et s égal. La situation à l'heure actuelle est la même que B4, satisfaisant l'édition [m] [n] = édition [m-1] [n] +1;
c. Un cas particulier est que lorsque S est vide, modifiez [0] [n] = n; et lorsque t est vide, modifiez [m] [0] = m; C'est facile à comprendre. Par exemple, pour les séquences "" et "ABC", le fonctionnement minimum des deux est 3, c'est-à-dire que la séquence "" effectue 3 opérations d'insertion, ou séquence "ABC" effectue 3 opérations de suppression.
Par conséquent, il n'est pas difficile pour nous de déduire l'équation de programmation dynamique de la distance d'édition ci-dessus:
Par conséquent, l'implémentation récursive de l'algorithme de programmation dynamique pour la distance d'édition de chaîne peut être exprimée dans le code Java suivant:
public static int editDistance (String A, String b) {if (a == null || b == null) {return -1; } return editDistance (a, a.length () - 1, b, b.length () - 1); } public static int editDistance (String A, int m, chaîne b, int n) {if (m <0 || n <0) {return 1; } else if (a.charat (m) == b.charat (n)) {return editDistance (a, m - 1, b, n - 1); } else {return math.min (math.min (editDistance (a, m - 1, b, n) + 1, editDistance (a, m, b, n - 1) + 1), editDistance (a, m - 1, b, n - 1) + 1); }}MISE À JOUR:
En même temps, à partir de l'équation de programmation dynamique de la distance d'édition, nous pouvons voir que l'édition [m] [n] peut être dérivée de l'édition [m - 1] [n - 1], éditer [m - 1] [n], modifier [m] [n - 1],, et si le montage est un tableau à deux dimensions, le montage de la main, la gauche et la gauche. Autrement dit, nous pouvons traverser le tableau bidimensionnel, puis calculer la valeur de courant par retournement de retour en arrière.
Par exemple, pour les chaînes S = "Sailn" et T = "FAILLING", le tableau bidimensionnel est initialisé comme:
| m / n | f | un | je | l | je | n | g | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| s | 1 | 1 | ||||||
| un | 2 | |||||||
| je | 3 | |||||||
| l | 4 | |||||||
| n | 5 |
Parce que s [0] = S, t [0] = f, alors s [0]! = T [0], alors correspond à la matrice à deux dimensions ci-dessus, modifier [1] [1] = min (modifier [0] [0], modifier [0] [1], modifier [1] [0]) + 1. 1 = 1.
| m / n | f | un | je | l | je | n | g | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| s | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| un | 2 | 2 | 1 | |||||
| je | 3 | |||||||
| l | 4 | |||||||
| n | 5 |
Pour S [1] = a, t [1] = a, s [1] = t [1], il correspond à une matrice bidimensionnelle, modifier [2] [2] = modifier [1] [1], donc modifier [2] [2] = 1. Selon cette règle, remplissez la matière matricielle à deux dimensions ci-dessus comme suit:
| m / n | f | un | je | l | je | n | g | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| s | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| un | 2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
| je | 3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
| l | 4 | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
| n | 5 | 5 | 4 | 3 | 2 | 2 | 2 | 3 |
Par conséquent, la distance d'édition entre les deux est édition [m] [n] = édition [5] [7] = 3.
Par conséquent, selon l'idée ci-dessus, la version Java de la solution de retour en arrière de la programmation dynamique peut être effectuée comme suit:
public static int editDistance (String A, String b) {if (a == null || b == null) {return -1; } int [] [] matrix = new int [a.length () + 1] [b.length () + 1]; for (int i = 0; i <a.length () + 1; i ++) {for (int j = 0; j <b.length () + 1; j ++) {if (i == 0) {matrix [i] [j] = j; } else if (j == 0) {matrix [i] [j] = i; } else {if (a.charat (i - 1) == b.charat (j - 1)) {matrix [i] [j] = matrice [i - 1] [j - 1]; } else {matrix [i] [j] = 1 + math.min (math.min (matrix [i - 1] [j], matrice [i] [j - 1]), matrice [i - 1]); }}} return Matrix [a.Length ()] [B.Length ()]; }Résumer
Ce qui précède est l'intégralité du contenu de cet article sur l'exemple d'échantillon de problème de distance d'édition pour la programmation dynamique Java. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler.