回溯法

應(yīng)用回溯法時，解空間往往以樹的結(jié)構(gòu)表示。回溯法以深度優(yōu)先的方式搜索解空間樹。如果回溯法在執(zhí)行過程中判斷解空間樹的某個節(jié)點不包含問題的解時，則跳過對以該節(jié)點為根的子樹的搜索，逐層向其祖先節(jié)點回溯；否則進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。
回溯法的搜索過程如下：從開始結(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結(jié)點就成為一個活結(jié)點，同時也成為當前的擴展結(jié)點。在當前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為一個新的活結(jié)點，并成為當前擴展結(jié)點。如果在當前的擴展結(jié)點處不能再向縱深方向移動，則當前擴展結(jié)點就成為死結(jié)點。

此時，應(yīng)往回移動（回溯）至最近的一個活結(jié)點處，并使這個活結(jié)點成為當前的擴展結(jié)點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點時為止。簡單來講回溯法的基本思想就是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。

編輯距離

兩個字符串之間，由一個轉(zhuǎn)成另一個所需的最少編輯操作次數(shù)，設(shè)A和B是兩個字符串，允許的字符操作包括：
(1)添加一個字符
(2)刪除一個字符
(3)修改一個字符
要用最少的字符操作將字符串A轉(zhuǎn)換為字符串B。
編輯距離d(A,B)的定義是把一個字符串A通過“插入、刪除和替換”這樣的編輯操作編程另外一個字符串操作變成另外一個字符串(B）所需要的最少編輯次數(shù)（代價或者費用最低)。從另外一個角度來看，可以將“字符串之間的編輯距離”視為“字符串之間的相似度”(和“最長公共子序列”問題有相同的視角)，也即“編輯距離”是將一個字符串轉(zhuǎn)換成另外一個字符串的代價(轉(zhuǎn)換的方法可能不唯一)，轉(zhuǎn)換的代價越高則說明兩個字符串的編輯距離越大，從而其相似度越低。
操作變成另外一個字符串(B)所需要的最少編輯次數(shù)(代價或者費用最低)。從另外一個角度來看，可以將“字符串之間的編輯距離”視為“字符串之間的相似度”(和“最長公共子序列”問題有相同的視角)，也即“編輯距離”是將一個字符串轉(zhuǎn)換成另外一個字符串的代價(轉(zhuǎn)換的方法可能不唯一)，轉(zhuǎn)換的代價越高則說明兩個字符串的編輯距離越大，從而其相似度越低.

可以判定，字符串 SNOWY 和 SUNNY 之間的編輯距離為 3。

解：
編輯距離問題的最優(yōu)子結(jié)構(gòu)性質(zhì)
編輯距離問題需要多個步驟處理。對字符串 A 做最少修改步驟變換到字符串 B，每個步驟都不是獨立的，受前面已經(jīng)確定的步驟和后面可選步驟的共同影響。設(shè)字符串 A 有 m 個字符，字符串 B 有 n 個字符。假定已經(jīng)得到將 A 的 1 ~ m 個字符轉(zhuǎn)換為 B 的 1 ~ n 個字符所需要的最優(yōu)解，即最少編輯次數(shù)；那么其子問題“將 A 的 1 ~ i 個字符轉(zhuǎn)換為 B 的 1 ~ j 個字符”也一定是最優(yōu)的，否則的話（反證法），存在一個子問題的最優(yōu)解，從而導致整個問題有一個更少的編輯次數(shù)，這和已知的最優(yōu)解矛盾。所以編輯距離存在最優(yōu)子結(jié)構(gòu)性質(zhì)。

建立狀態(tài)方程

代碼

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream>using namespace std;#define STR_LEN 100 #define TRUE 1 #define FALSE 0int FindTripleMin( int a, int b, int c ); int CalcEditDistance( char *StrA, char *StrB, int **d ); void PrintEditDistanceMatrix( int **d, int RowNum, int ColNum );char StrA[ STR_LEN ]; char StrB[ STR_LEN ]; int d[STR_LEN][STR_LEN]; int pp[STR_LEN][STR_LEN];int FindTripleMin( int a, int b, int c ) {int t = ( a < b ) ? a : b;return ( ( t < c ) ? t : c ); }// ( 1 ) A = fxpimu B = xwrs d( A, B ) = 5 // ( 2 ) A = abc B = cba d( A, B ) = 2 // ( 3 ) A = stot B = stop d( A, B ) = 1 // ( 4 ) A = cd B = abcb d( A, B ) = 3 int CalcEditDistance() {for( int i = 0; i <= strlen( StrA ); i++ )d[ i ][ 0 ] = i;for( int j = 0; j <= strlen( StrB ); j++ )d[ 0 ][ j ] = j;for( int i = 1; i <= strlen( StrA ); i++ ){for( int j = 1; j <= strlen( StrB ) ; j++){char x = StrA[i-1];char y = StrB[j-1];if(x == y){d[i][j] =d[i-1][j-1] + 0;}else{d[i][j] = FindTripleMin(d[i][j-1]+1 , d[i-1][j] + 1 , d[i-1][j-1] + 1);}}}return d[ strlen( StrA ) ][ strlen( StrB ) ]; }int FindBack(){int m = strlen( StrA );int n = strlen( StrB );while (n>=0 || m>=0){if (n && d[m][n-1]+1 == d[m][n]){//printf("%d " ,m);printf("\t插入 %c\n" , (StrB[n-1]));n -= 1;continue;}if (m && d[m-1][n]+1 == d[m][n]){//printf("%d " ,m);printf("\t刪除 %c\n" , (StrA[m-1]));m -= 1;continue;}if (d[m-1][n-1]+1 == d[m][n]){//printf("%d " ,m);printf("\t替換 %c --- %c\n" , StrA[m-1],StrB[n-1]);n -= 1;m -= 1;continue;}if (d[m-1][n-1] == d[m][n]){n -= 1;m -= 1;}}}void PrintEditDistanceMatrix(int RowNum, int ColNum ) {int i, j;printf( "\t編輯距離矩陣是 : \n" );for ( i = 0; i <= RowNum - 1; i++ ){printf( "\t" );for ( j = 0; j <= ColNum - 1; j++ )printf( "%d ", d[ i ][ j ] );printf( "\n" );}printf( "\n\n" ); }int main(void) {int i, m, n, dAB;system( "cls" );printf( "\n\n\t輸入字符串A : " );//cin >> StrA ;scanf( "%s", StrA );m = strlen( StrA );printf( "\n\t輸入字符串B: : " );getchar();//cin >> StrB ;scanf( "%s", StrB );n = strlen( StrB );dAB = CalcEditDistance();FindBack();cout << "\t編輯距離: " << dAB <<endl;PrintEditDistanceMatrix(( m + 1 ), ( n + 1 ) );for ( i = 0; i <= m; i++ )free( d[ i ] );free( d );return 0;}//

總結(jié)

以上是生活随笔為你收集整理的使用回溯法解决编辑距离问题(C语言)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。