El proceso de planificación dinámica es: cada decisión depende del estado actual y luego se transfiere el estado. Se genera una secuencia de decisión en un estado cambiante, por lo que este proceso de toma de decisiones de optimización de varias etapas se llama programación dinámica.
La programación dinámica es en realidad un término general para un tipo de tema, no un algoritmo fijo. El significado de la programación dinámica es resolver el enfoque general mediante la adopción de estrategias recursivas (o división y conquistar) y resolver los subproblemas de grandes problemas. La idea central de la programación dinámica es dividir ingeniosamente el problema en múltiples subproblemas y obtener la solución general al problema calculando los subproblemas. Los subproblemas se pueden dividir en más subproblemas, resolviendo así los problemas requeridos utilizando métodos similares a la iteración recursiva. Descripción de la pregunta:
Para las secuencias S y T, la distancia entre ellos se define como: realizar las siguientes operaciones varias veces en una de las dos: 1, eliminar un carácter; 2, inserte un carácter; 3, cambia un personaje. Cada vez que se realiza la operación, el recuento aumenta en 1. El recuento mínimo de convertir S y T en una secuencia igual es la distancia de edición (editDistance) o la similitud entre los dos. Dé el algoritmo correspondiente y su implementación.
analizar:
Suponga que las longitudes de las secuencias S y T son myn respectivamente, y la distancia de edición entre ellas se expresa como edit [m] [n]. Luego están las siguientes situaciones al operar la secuencia:
a. Cuando los caracteres finales de S y T son iguales, no se requiere ninguna de las operaciones de definición anteriores (es decir, "editar") para los caracteres finales, es decir, no se requiere un recuento. La condición está satisfecha: editar [m] [n] = editar [m-1] [n-1].
b. Cuando los caracteres finales de S y T no son iguales, el final de cualquiera de ellos debe editarse y el recuento correspondiente se incrementará en 1.
B1, modifique el final de S o T para que sea igual a t o s, luego edite [m] [n] = editar [m-1] [n-1] +1;
B2, elimine el elemento al final de S para hacer S y T igual, luego editar [m] [n] = editar [m-1] [n] +1;
B3, elimine el elemento al final de t para hacer que T y S iguales, luego editar [m] [n] = editar [m] [n-1] +1;
B4, agregue el elemento de cola de T al final de S para hacer que S y T igual, entonces la longitud de S se convierte en M+1, pero en este momento, los elementos finales de S y T ya son iguales. Solo necesita comparar los primeros elementos m de S con los primeros elementos N-1 de t, así que editar [m] [n] = editar [m] [n-1] +1;
B5, agregue el elemento de cola de S al final de T para hacer que T y S sean iguales. La situación en este momento es la misma que B4, satisface la edición [m] [n] = editar [m-1] [n] +1;
do. Un caso especial es que cuando S está vacío, edite [0] [n] = n; y cuando t esté vacío, edite [m] [0] = m; Esto es fácil de entender. Por ejemplo, para las secuencias "" y "ABC", la operación mínima de ambos es 3, es decir, la secuencia "" realiza 3 operaciones de inserción, o la secuencia "ABC" realiza 3 operaciones de eliminación.
Por lo tanto, no es difícil para nosotros deducir la ecuación de programación dinámica de la distancia de edición anterior:
Por lo tanto, la implementación recursiva del algoritmo de programación dinámica para la distancia de edición de cadenas se puede expresar en el siguiente código Java:
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, String 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); }}ACTUALIZAR:
Al mismo tiempo, desde la ecuación de programación dinámica de la distancia de edición, podemos ver que editar [m] [n] se puede derivar de editar [m - 1] [n - 1], editar [m - 1] [n], editar [m] [n - 1], y si la edición es una matriz bidimensional, editar [m] [n] se puede determinar por las condiciones por los elementos en sus elementos en sus elementos en su parte superior, izquierda y superior a la izquierda. Es decir, podemos atravesar la matriz bidimensional y luego calcular el valor actual a través del retroceso.
Por ejemplo, para las cadenas S = "Sailn" y T = "Failing", la matriz bidimensional se inicializa como:
| Minnesota | F | a | i | l | i | norte | gramo | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| s | 1 | 1 | ||||||
| a | 2 | |||||||
| i | 3 | |||||||
| l | 4 | |||||||
| norte | 5 |
Porque s [0] = s, t [0] = f, entonces s [0]! = T [0], luego corresponde a la matriz bidimensional anterior, editar [1] [1] = min (editar [0] [0], editar [0] [1], editar [1] [0] + 1 i.e. editar [1] [1] = min (0, 1, 1) + 1 i.e. editar [1] [1] [1].
| Minnesota | F | a | i | l | i | norte | gramo | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| s | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| a | 2 | 2 | 1 | |||||
| i | 3 | |||||||
| l | 4 | |||||||
| norte | 5 |
Para s [1] = a, t [1] = a, s [1] = t [1], corresponde a una matriz bidimensional, editar [2] [2] = editar [1] [1], entonces editar [2] [2] = 1. Según esta regla, llene la matriz bidimensional anterior de la siguiente manera:
| Minnesota | F | a | i | l | i | norte | gramo | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| s | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| a | 2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
| i | 3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
| l | 4 | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
| norte | 5 | 5 | 4 | 3 | 2 | 2 | 2 | 3 |
Por lo tanto, la distancia de edición entre los dos es editar [m] [n] = editar [5] [7] = 3.
Por lo tanto, de acuerdo con la idea anterior, la versión Java de la solución de retroceso de programación dinámica se puede realizar de la siguiente manera:
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) {matriz [i] [j] = j; } else if (j == 0) {matriz [i] [j] = i; } else {if (a.charat (i - 1) == b.charat (j - 1)) {matriz [i] [j] = matrix [i - 1] [j - 1]; } else {matriz [i] [j] = 1 + math.min (math.min (matriz [i - 1] [j], matriz [i] [j - 1]), matriz [i - 1]); }}} return matrix [a.length ()] [b.length ()]; }Resumir
Lo anterior es todo el contenido de este artículo sobre el código de muestra de problema de distancia de edición para la programación dinámica Java. Espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a otros temas relacionados en este sitio. Si hay alguna deficiencia, deje un mensaje para señalarlo.