www.久久久,精品久久久久一区,亚洲国产精品久久

動(dòng)態(tài)規(guī)劃過程是：每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以，這種多階段最優(yōu)化決策解決問題的過程就稱為動(dòng)態(tài)規(guī)劃。

動(dòng)態(tài)規(guī)劃實(shí)際上是一類題目的總稱，并不是指某個(gè)固定的算法。動(dòng)態(tài)規(guī)劃的意義就是通過采用遞推（或者分而治之）的策略，通過解決大問題的子問題從而解決整體的做法。動(dòng)態(tài)規(guī)劃的核心思想是巧妙的將問題拆分成多個(gè)子問題，通過計(jì)算子問題而得到整體問題的解。而子問題又可以拆分成更多的子問題，從而用類似遞推迭代的方法解決要求的問題。問題描述:

對(duì)于序列s和t,它們之間的距離定義為:對(duì)二者其一進(jìn)行幾次以下操作:1,刪除一個(gè)字符;2,插入一個(gè)字符;3,改變一個(gè)字符.每進(jìn)行一次操作,計(jì)數(shù)增加1.將s和t變?yōu)橄嗟刃蛄械淖钚∮?jì)數(shù)就是兩者的編輯距離(editdistance)或者叫相似度.請(qǐng)給出相應(yīng)算法及其實(shí)現(xiàn).

分析:

假設(shè)序列s和t的長(zhǎng)度分別為m和n,兩者的編輯距離表示為edit[m][n].則對(duì)序列進(jìn)行操作時(shí)存在以下幾種情況:

a,當(dāng)s和t的末尾字符相等時(shí),對(duì)末尾字符不需要進(jìn)行上述定義操作中(亦即"編輯")的任何一個(gè),也就是不需要增加計(jì)數(shù).則滿足條件:edit[m][n]=edit[m-1][n-1].

b,當(dāng)s和t的末尾字符不相等時(shí),則需要對(duì)兩者之一的末尾進(jìn)行編輯,相應(yīng)的計(jì)數(shù)會(huì)增加1.

b1,對(duì)s或t的末尾進(jìn)行修改,以使之與t或s相等,則此時(shí)edit[m][n]=edit[m-1][n-1]+1;

b2,刪除s末尾的元素,使s與t相等,則此時(shí)edit[m][n]=edit[m-1][n]+1;

b3,刪除t末尾的元素,使t與s相等,則此時(shí)edit[m][n]=edit[m][n-1]+1;

b4,在s的末尾添加t的尾元素,使s和t相等,則此時(shí)s的長(zhǎng)度變?yōu)閙+1,但是此時(shí)s和t的末尾元素已經(jīng)相等,只需要比較s的前m個(gè)元素與t的前n-1個(gè)元素,所以滿足edit[m][n]=edit[m][n-1]+1;

b5,在t的末尾添加s的尾元素,使t和s相等,此時(shí)的情況跟b4相同,滿足edit[m][n]=edit[m-1][n]+1;

c,比較特殊的情況是,當(dāng)s為空時(shí),edit[0][n]=n;而當(dāng)t為空時(shí),edit[m][0]=m;這個(gè)很好理解,例如對(duì)于序列""和"abc",則兩者的最少操作為3,即序列""進(jìn)行3次插入操作,或者序列"abc"進(jìn)行3次刪除操作.

所以,以上我們不難推出編輯距離的動(dòng)態(tài)規(guī)劃方程為:

Java動(dòng)態(tài)規(guī)劃之編輯距離問題示例代碼

所以, 字符串編輯距離的動(dòng)態(tài)規(guī)劃算法的遞歸實(shí)現(xiàn)可以用如下的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);

									    }

									  }

update:

同時(shí), 由編輯距離的動(dòng)態(tài)規(guī)劃方程我們可以看出, edit[m][n]可以由edit[m - 1][n - 1], edit[m - 1][n], edit[m][n - 1]得出, 而如果edit是一個(gè)二維數(shù)組的話, edit[m][n]可以由它的上, 左, 左上三個(gè)位置的元素通過條件判斷得出. 亦即我們可以通過遍歷二維數(shù)組, 然后通過回溯來計(jì)算當(dāng)前值.

例如對(duì)于字符串s = "sailn"和t = "failing", 對(duì)二維數(shù)組進(jìn)行初始化為:

m\n		f	a	i	l	i	n	g
	0	1	2	3	4	5	6	7
s	1	1
a	2
i	3
l	4
n	5

因?yàn)閟[0] = s, t[0] = f, 則s[0] != t[0], 則對(duì)應(yīng)于上述二維矩陣, edit[1][1] = min(edit[0][0], edit[0][1], edit[1][0]) + 1即edit[1][1] = min(0, 1, 1) + 1即edit[1][1] = 0 + 1 = 1.

m\n		f	a	i	l	i	n	g
	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
n	5

而對(duì)于s[1] = a, t[1] = a, s[1] = t[1], 則對(duì)應(yīng)于二維矩陣, edit[2][2] = edit[1][1], 所以edit[2][2] = 1. 所以按照這種規(guī)則, 將上述二維矩陣填滿則如下:

m\n		f	a	i	l	i	n	g
	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
n	5	5	4	3	2	2	2	3

所以, 兩者的編輯距離為edit[m][n] = edit[5][7] = 3.

所以, 按照上述思路即動(dòng)態(tài)規(guī)劃的回溯解法的java版本可以如下進(jìn)行:

									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], matrix[i][j - 1]), matrix[i - 1][j - 1]);

									          }

									        }

									      }

									    }

									    return matrix[a.length()][b.length()];

									  }