Java 동적 프로그래밍 편집 거리 문제 예제 코드

동적 계획 프로세스는 다음과 같습니다. 각 결정은 현재 상태에 따라 다릅니다. 그런 다음 상태가 양도됩니다. 의사 결정 순서는 변화하는 상태에서 생성 되므로이 다단계 최적화 의사 결정 프로세스를 동적 프로그래밍이라고합니다.

동적 프로그래밍은 실제로 고정 된 알고리즘이 아닌 주제 유형의 일반적인 용어입니다. 역동적 인 프로그래밍의 의미는 재귀 (또는 분열 및 정복) 전략을 채택하고 큰 문제의 하위 문제를 해결함으로써 전반적인 접근법을 해결하는 것입니다. 동적 프로그래밍의 핵심 아이디어는 문제를 여러 하위 문제로 영리하게 나누고 하위 문제를 계산하여 문제에 대한 전체 솔루션을 얻는 것입니다. 하위 프로젝트는 더 하위 문제로 나눌 수 있으므로 재귀 반복과 유사한 방법을 사용하여 필요한 문제를 해결할 수 있습니다. 질문 설명 :

시퀀스 S 및 T의 경우, 그들 사이의 거리는 다음과 같이 정의됩니다. 두 가지 중 하나에서 다음 작업을 여러 번 수행합니다. 1, 문자를 삭제하십시오. 2, 캐릭터를 삽입하십시오. 3, 캐릭터를 변경하십시오. 작업이 수행 될 때마다 수는 1만큼 증가합니다. S와 T의 최소 수는 동일한 순서로 회전합니다. 편집 거리 (EditDistance) 또는 둘 사이의 유사성입니다. 해당 알고리즘과 구현을 제공하십시오.

분석 :

시퀀스 S와 T의 길이가 각각 m과 n이며, 그들 사이의 편집 거리는 편집 [m] [n]로 표현된다고 가정한다. 그런 다음 시퀀스를 작동 할 때 다음과 같은 상황이 있습니다.

에이. s와 t의 끝 문자가 동일 할 때, 위의 정의 작업 (즉, "편집") 중 어느 누구도 끝 문자에 필요하지 않습니다. 즉, 카운트가 필요하지 않습니다. 조건이 충족됩니다 : 편집 [m] [n] = 편집 [m-1] [n-1].

비. s와 t의 끝 문자가 같지 않으면 그 중 하나의 끝을 편집해야하며 해당 카운트는 1만큼 증가합니다.

B1, s 또는 t의 끝을 t 또는 s와 동일하게하기 위해 s 또는 t의 끝을 수정 한 다음 [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, s 끝에서 t의 꼬리 요소를 추가하여 s와 t를 동일하게 한 다음 s의 길이는 m+1이되지만이 시점에서 s와 t의 끝 요소는 이미 동일합니다. s의 첫 번째 m 요소를 t의 첫 번째 n-1 요소와 비교하면 [m] [n] = 편집 [m] [n-1] +1;

b5, t 끝에서 s의 꼬리 요소를 추가하여 t와 s를 동일하게 만듭니다. 이 시점의 상황은 B4와 동일하며 [m] [n] = 편집 [m-1] [n] +1;

기음. 특별한 경우는 s가 비어있을 때 [0] [n] = n을 편집하는 것입니다. t가 비어있을 때 [m] [0] = m을 편집하십시오. 이해하기 쉽습니다. 예를 들어, 시퀀스 ""및 "ABC"의 경우, 두 가지 모두의 최소 작동은 3, 즉 시퀀스 "" "3 삽입 작업을 수행하거나"ABC "시퀀스를 수행합니다. 3 삭제 작업을 수행합니다.

따라서 위의 편집 거리의 동적 프로그래밍 방정식을 추론하는 것은 어렵지 않습니다.

따라서 문자열 편집 거리에 대한 동적 프로그래밍 알고리즘의 재귀 구현은 다음 Java 코드로 표현할 수 있습니다.

 public static int editdistance (문자열 a, 문자열 b) {if (a == null || b == null) {return -1; } return editDistance (a, a.length () -1, b, b.length () -1); } public static int editdistance (문자열 a, int m, 문자열 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, 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]에서 파생 될 수 있음을 알 수 있습니다. 편집이 2 차원 배열이면 [m] [n] [m] [n]가 왼쪽에있는 조건에 의해 결정될 수 있습니다. 즉, 2 차원 배열을 가로지고 역 추적을 통해 현재 값을 계산할 수 있습니다.

예를 들어, 문자열 s = "sailn"및 t = "실패"의 경우 2 차원 어레이는 다음과 같이 초기화됩니다.

s [0] = s, t [0] = f, 그런 다음 s [0]! = t [0]이기 때문에 위의 2 차원 매트릭스, 편집 [1] [1] = min (편집 [0] [0], 편집 [0] [1], 편집 [1] [0]) + 1 I.E. 편집 [1] [1] = min (0, 1, 1, 1, 1). 1 = 1.

s [1] = a, t [1] = a, s [1] = t [1]의 경우, 2 차원 행렬, 편집 [2] [2] = 편집 [1] [1]에 해당하므로 [2] [2] = 1을 편집하므로 다음과 같이 위의 2 차원 매트릭스를 채우십시오.

따라서 둘 사이의 편집 거리는 편집 [m] [n] = 편집 [5] [7] = 3입니다.

따라서 위의 아이디어에 따르면, 동적 프로그래밍의 역 추적 솔루션의 Java 버전은 다음과 같이 수행 될 수 있습니다.

 public static int editdistance (문자열 a, 문자열 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; } 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], matrix [i] [j -1]), 매트릭스 [i -1]); }}} return matrix [a.length ()] [b.length ()]; }

요약

위는 Java Dynamic Programming의 편집 거리 문제 샘플 코드에 대한이 기사의 전체 내용입니다. 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구는이 사이트의 다른 관련 주제를 계속 참조 할 수 있습니다. 단점이 있으면 메시지를 남겨 두십시오.