1.问题描述
上一次说了最小编辑距离，这次在这上面加一点料，a1、a2和a3每次操作的代价不同了，加入了每个操作的代价，这下问题变为，针对字符串a和字符串b定义三种操作，a1、a2、a3：
a1：修改a中一个字符，代价为A
a2：插入一个字符到a中，代价为B
a3：从a中删除一个字符，代价为C
经过这三种操作，将a变换成b，在给定a和b的情况下，求需要的最小代价
2.问题分析
该问题同样是一个动态规划求解问题，首先构建动态规划矩阵进行分析。假设a字符串“abcd”，b字符串“acde”，以a字符串为列，b字符串为行，构建动态规划矩阵如下所示。
| a | c | d | e | |
|---|---|---|---|---|
| a | ||||
| b | ||||
| c | ||||
| d |
现在的问题是要将列逐渐变成行，即将字符串a变成b，关键问题是填充上述矩阵元素值的方法。我们可以看到，矩阵的第一行，和第一列可以直接比较得出，即第一行字符“a”变成字符串b需要的操作，“a”变成第一列“a”，。两字符相等，不需要操作；“a”变成字符串“ab”需要再右侧基础上加一部插入操作，所以在矩阵[0,0]位置加上一部插入，变成矩阵[0,1]位置；依次类推，我们可以逐渐插入字符，从字符串“a”变成b，得到矩阵第一行的操作次数记录，这时记得插入操作的代价为B。同理，按列操作，可以得到a变换成字符“a”的操作次数，这里是删除操作，代价为C。如此得到矩阵第一行和第一列，如下所示。
| a | c | d | e | |
|---|---|---|---|---|
| a | 0 | B | 2B | 3B |
| b | C | |||
| c | 2C | |||
| d | 3C |
下面是计算的关键部分，就是如何计算矩阵中如下元素的值，可以看到，在矩阵中，从上方[i-1,j]到[i,j]为删除操作，代价为C，从左侧[i,j-1]到[i,j]为插入操作，代价为B，从左上方[i-1,j-1]到[i,j]是修改操作，如果此时a[i]!=b[j],执行修改，代价为A。
| a | c | d | e | |
|---|---|---|---|---|
| a | 0 | B | 2B | 3B |
| b | C | min(n1,n2,n3) | ||
| c | 2C | |||
| d | 3C | | |
从矩阵可以得出规律，每次需要操作时，都在$$[i-1,j-1]$$（i表示行，j表示列），$$[i-1,j]$$和$$[i,j-1]$$三个位置的基础上，计算当前元素[i,j]是否需要进行操作。根据[i-1,j],[i,j-1]和[i-1,j-1]三个位置的取值最小的值来判断进行的操作，加上操作的代价Cost，即为当前[i,j]的取值。最终结果取这三个值的最小值。可以得到动态规划方程：
int ncostA = 0, ncostB = nB, ncostC = nC;
if (a[i] != b[j])
{
ncostA = A;
}
[i,j] = min([i-1,j] + ncostC, [i,j-1] + ncostB, [i-1,j-1] + ncostA);
通过规划方程，对矩阵所有元素进行赋值，最终矩阵右下角次数值即为所求最少操作次数。为了编程方便，我们在构建矩阵时在原有字符串前加入一个标识位，假设A=1，B=2，C=3，得到如下矩阵。
| a | c | d | e | ||
|---|---|---|---|---|---|
| 0 | 2 | 4 | 6 | 8 | |
| a | 3 | 0 | 2 | 4 | 6 |
| b | 6 | 3 | 1 | 3 | 5 |
| c | 9 | 6 | 3 | 2 | 4 |
| d | 12 | 9 | 6 | 3 | 3 |
3代码
int min(int a, int b)
{
if (a < b)
{
return a;
}
else
{
return b;
}
}
int min(int a, int b, int c)
{
int ntemp1 = min(a, b);
int ntemp2 = min(b, c);
if (ntemp1 < ntemp2)
{
return ntemp1;
}
else
{
return ntemp2;
}
}
int minEditNumber(char *src, char * dst, int nA, int nB, int nC)
{
int nsrc = strlen(src);
int ndst = strlen(dst);
if (0 == nsrc)
{
return ndst;
}
else if (0 == ndst)
{
return nsrc;
}
int **pnmatrix = new int* [nsrc + 1];
for (int n = 0; n <= nsrc; n++)
{
pnmatrix[n] = new int[ndst + 1];
}
for (int i = 0; i <= nsrc; i++)
{
pnmatrix[i][0] = i*nC;
}
for (int j = 0; j <= ndst; j++)
{
pnmatrix[0][j] = j*nB;
}
for (int i = 1; i <= nsrc; i++)
{
for (int j = 1; j <= ndst; j++)
{
int ncost = 0;
if (src[i-1] != dst[j-1])
{
ncost = nA;
}
pnmatrix[i][j] = min(pnmatrix[i - 1][j - 1] + ncost, pnmatrix[i - 1][j] + nC, pnmatrix[i][j - 1] + nB);
}
}
//print matrix
for (int i = 0; i <= nsrc; i++)
{
for (int j = 0; j <= ndst; j++)
{
cout << pnmatrix[i][j] << " ";
}
cout << endl;
}
int nReturn = pnmatrix[nsrc][ndst];
for (int i = 0; i <= nsrc; i++)
{
delete[] pnmatrix[i];
pnmatrix[i] = NULL;
}
delete[] pnmatrix;
pnmatrix = NULL;
return nReturn;
}
int main()
{
char *p1 = "abcd";
char *p2 = "acde";
int nNo = minEditNumber(p1, p2，1，2，3);
}
原创文章，作者：admin，如若转载，请注明出处：https://www.isclab.org.cn/2015/11/09/%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92-%e6%9c%80%e5%b0%8f%e7%bc%96%e8%be%91%e4%bb%a3%e4%bb%b7/
