Java Dynamic Programming Editar Distância Problema Exemplo Código

O processo de planejamento dinâmico é: cada decisão depende do estado atual e, em seguida, o estado é transferido. Uma sequência de decisão é gerada em um estado de mudança; portanto, esse processo de tomada de decisão de otimização de vários estágios é chamado de programação dinâmica.

A programação dinâmica é na verdade um termo geral para um tipo de tópico, não um algoritmo fixo. O significado da programação dinâmica é resolver a abordagem geral adotando estratégias recursivas (ou divisórias e conquistadas) e resolvendo os subproblemas de grandes problemas. A idéia central da programação dinâmica é dividir inteligentemente o problema em vários subproblemas e obter a solução geral para o problema calculando os subproblemas. Os subproblemas podem ser divididos em mais problemas, resolvendo assim os problemas necessários usando métodos semelhantes à iteração recursiva. Descrição da pergunta:

Para as sequências S e T, a distância entre elas é definida como: executando as seguintes operações várias vezes em um dos dois: 1, exclua um caractere; 2, insira um personagem; 3, mude um personagem. Cada vez que a operação é realizada, a contagem é aumentada em 1. A contagem mínima de transformar S e T em uma sequência igual é a distância de edição (editdistância) ou a semelhança entre os dois. Dê o algoritmo correspondente e sua implementação.

analisar:

Suponha que os comprimentos das sequências S e T sejam M e N, respectivamente, e a distância de edição entre elas é expressa como edição [m] [n]. Depois, há as seguintes situações ao operar a sequência:

um. Quando os caracteres finais de S e T são iguais, nenhuma das operações de definição acima (ou seja, "editar") é necessária para os caracteres finais, ou seja, nenhuma contagem é necessária. A condição é satisfeita: editar [m] [n] = editar [m-1] [n-1].

b. Quando os caracteres finais de S e T não são iguais, o final de qualquer um deles precisa ser editado e a contagem correspondente será aumentada em 1.

B1, modifique o final de s ou t para torná-lo igual a t ou s e editar [m] [n] = editar [m-1] [n-1] +1;

B2, exclua o elemento no final de S para tornar s e t igual e edite [m] [n] = editar [m-1] [n] +1;

B3, exclua o elemento no final de t para tornar T e S iguais e edite [m] [n] = editar [m] [n-1] +1;

B4, adicione o elemento da cauda de T no final de S para tornar S e T iguais, então o comprimento de S se torna M+1, mas, neste momento, os elementos finais de S e T já são iguais. Você só precisa comparar os primeiros M Elementos de S com os primeiros elementos N-1 de t, então edite [m] [n] = editar [m] [n-1] +1;

B5, adicione o elemento da cauda de S no final de T para tornar T e S iguais. A situação neste momento é a mesma que B4, satisfazendo a edição [m] [n] = editar [m-1] [n] +1;

c. Um caso especial é que, quando S está vazio, edite [0] [n] = n; e quando t está vazio, edite [m] [0] = m; Isso é fácil de entender. Por exemplo, para sequências "" e "ABC", a operação mínima de ambos IS 3, ou seja, sequência "" executa 3 operações de inserção ou sequência "ABC" executa 3 operações de exclusão.

Portanto, não é difícil para nós deduzir a equação de programação dinâmica da distância de edição acima:

Portanto, a implementação recursiva do algoritmo de programação dinâmica para a distância de edição de string pode ser expressa no seguinte código Java:

 public static int editDistance (string a, string b) {if (a == null || b == null) {return -1; } retornar 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); }}

ATUALIZAR:

Ao mesmo tempo, a partir da equação dinâmica de programação da distância de edição, podemos ver que editar [m] [n] pode ser derivado de editar [m - 1] [n - 1], editar [m - 1] [n], editar [m] [n], e se o que é um editor de uma vez por dia, e editar [n] [n], e se o que é o que é o que é o que é um editor, e o que é o mesmo que o eDIT, e o que é o que é o que é o que é o que é um dos dois dias, e o impotim, e o que é um dos nutrientes. Isto é, podemos atravessar a matriz bidimensional e calcular o valor atual através do backtracking.

Por exemplo, para as cordas s = "sailn" e t = "falhando", a matriz bidimensional é inicializada como:

Porque s [0] = s, t [0] = f, então s [0]! = T [0], então corresponde à matriz bidimensional acima, editar [1] [1] = min (editar [0] [0], editar [0] [1], editar [1] [0] + 1 1 isto é [1] [1] [1] [1], editar [1] [0] + 1 1 isto é [1] [1] [1] [1], (1], (1] [0] 1 1 isto é [1] [1] [1] [1], Edit [1] [0] + 1 1 isto é [1] [1] [1] [1], (1], (1] [0] 1 1 isto é [1]. 1 = 1.

Para s [1] = a, t [1] = a, s [1] = t [1], corresponde a uma matriz bidimensional, editar [2] [2] = editar [1] [1], então edite [2] [2] = 1. De acordo com esta regra, preencha a matriz bidimensional acima como segue:

Portanto, a distância de edição entre os dois é editar [m] [n] = editar [5] [7] = 3.

Portanto, de acordo com a idéia acima, a versão Java da solução de backtracking de programação dinâmica pode ser realizada da seguinte maneira:

 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] = matriz [i - 1] [j - 1]; } else {matrix [i] [j] = 1 + math.min (math.min (matriz [i - 1] [j], matriz [i] [j - 1]), matriz [i - 1]); }}} retornar matrix [A.Length ()] [b.Length ()]; }

Resumir

O exposto acima é o conteúdo inteiro deste artigo sobre o código de amostra do problema da distância de edição para programação dinâmica de Java. Espero que seja útil para todos. Amigos interessados ​​podem continuar se referindo a outros tópicos relacionados neste site. Se houver alguma falha, deixe uma mensagem para apontá -la.