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/

动态规划——最小编辑代价

1.问题描述

2.问题分析

3代码

相关推荐