Java Dynamic Programming Редактирование

Процесс динамического планирования: каждое решение зависит от текущего состояния, а затем государство передается. Последовательность принятия решений генерируется в изменяющемся состоянии, поэтому этот многоэтапный процесс принятия решений оптимизацией называется динамическим программированием.

Динамическое программирование на самом деле является общим термином для типа темы, а не фиксированного алгоритма. Значение динамического программирования состоит в том, чтобы решить общий подход, приняв рекурсивные (или разделение и завоевание) стратегии и решение подпрограмм больших проблем. Основная идея динамического программирования состоит в том, чтобы умело разбить проблему на несколько подпрограмм и получить общее решение проблемы путем расчета подпрограмм. Подпроблемы могут быть разделены на более подпрограмм, тем самым решая необходимые проблемы с использованием методов, аналогичных рекурсивной итерации. Описание вопроса:

Для последовательностей S и T расстояние между ними определяется как: выполнение следующих операций несколько раз на одном из двух: 1, удалите символ; 2, вставьте персонажа; 3, изменить персонажа. Каждый раз, когда выполняется операция, количество увеличивается на 1. Минимальный счет поворота S и T в равную последовательность - это расстояние редактирования (редактирование) или сходство между ними. Пожалуйста, дайте соответствующий алгоритм и его реализацию.

проанализировать:

Предположим, что длина последовательностей S и T составляет M и N соответственно, а расстояние редактирования между ними выражается как редактирование [M] [n]. Тогда есть следующие ситуации при эксплуатации последовательности:

а Когда конечные символы S и T будут равны, ни одна из вышеуказанных операций определения (то есть «редактирование») не требуется для конечных символов, то есть не требуется подсчет. Условие удовлетворено: редактировать [m] [n] = редактировать [M-1] [n-1].

беременный Когда конечные символы S и T не равны, конец любого из них необходимо отредактировать, и соответствующий счет будет увеличен на 1.

B1, измените конец S или T, чтобы сделать его равным T или S, затем редактировать [M] [n] = редактировать [M-1] [n-1] +1;

B2, удалите элемент в конце S, чтобы сделать S и t равным, затем редактировать [m] [n] = редактировать [m-1] [n] +1;

b3, удалите элемент в конце t, чтобы сделать t и s равным, затем редактировать [m] [n] = редактировать [m] [n-1] +1;

B4, добавьте хвостовой элемент T в конце S, чтобы сделать S и T равным, тогда длина S становится M+1, но в это время конечные элементы S и T уже равны. Вам нужно только сравнить первые M-элементы S с первыми элементами N-1 T, поэтому редактируйте [m] [n] = редактировать [M] [n-1] +1;

B5, добавьте хвостовой элемент S в конце T, чтобы сделать t и s равным. Ситуация в это время такая же, как B4, удовлетворяющая редактирование [m] [n] = edit [m-1] [n] +1;

в Особый случай заключается в том, что когда S пуст, редактировать [0] [n] = n; и когда t пуст, отредактируйте [m] [0] = m; Это легко понять. Например, для последовательностей «» и «ABC» минимальная работа обоих IS 3, то есть последовательность «выполняет 3 операции вставки, или последовательность« ABC »выполняет 3 операции удаления.

Следовательно, нам не сложно вывести динамическое уравнение программирования расстояния редактирования выше:

Следовательно, рекурсивная реализация алгоритма динамического программирования для расстояния редактирования строк может быть выражена в следующем коде 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); }}

ОБНОВЛЯТЬ:

В то же время, из уравнения динамического программирования расстояния редактирования, мы видим, что редактирование [M] [n] может быть получено из редактирования [M - 1] [N - 1], редактирования [M - 1] [n], редактирования [M] [N - 1], и если редактирование является двухмерной массивом, редактирование [M] [n] может определяться по условиям на элементах с элементом ELIP, и его. То есть мы можем пересечь двумерный массив, а затем вычислить текущее значение с помощью возврата.

Например, для строк s = "sailn" и t = "сбой", двумерный массив инициализируется как:

Потому что s [0] = s, t [0] = f, затем s [0]! = T [0], затем соответствует вышеуказанной двумерной матрице, редактирование [1] [1] = min (редактирование [0] [0], редактирование [0] [1], редактирование [1] [0]) + 1, т.е. edit [1] = min (1) + 1) + 1). 1 = 1.

Для s [1] = a, t [1] = a, s [1] = t [1], он соответствует двумерной матрице, редактируйте [2] [2] = редактировать [1] [1], поэтому редактируйте [2] [2] = 1. Поэтому в соответствии с этим правилом заполните вышеуказанную двухмерную матрицу следующим образом:

Следовательно, расстояние редактирования между ними является редактирование [m] [n] = редактировать [5] [7] = 3.

Следовательно, согласно вышеуказанной идее, Java -версия решения динамического программирования может быть выполнена следующим образом:

 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] = matrix [i - 1] [j - 1]; } else {matrix [i] [j] = 1 + math.min (math.min (matrix [i - 1] [j], матрица [i] [j - 1]), матрица [i - 1]); }}} return matrix [a.length ()] [b.length ()]; }

Суммировать

Выше приведено все содержимое этой статьи о примере кода от редактирования расстояния для динамического программирования Java. Я надеюсь, что это будет полезно для всех. Заинтересованные друзья могут продолжать ссылаться на другие связанные темы на этом сайте. Если есть какие -либо недостатки, пожалуйста, оставьте сообщение, чтобы указать это.