Chinaunix首页 | 论坛 | 博客
  • 博客访问: 163977
  • 博文数量: 118
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 12
  • 用 户 组: 普通用户
  • 注册时间: 2013-06-21 16:38
文章分类

全部博文(118)

文章存档

2013年(118)

我的朋友

分类: C/C++

2013-09-04 17:12:00

    最近在网上偶然看到了一个关于最重要算法的调查(),这些算法中有些熟悉,有些连听过都没听过。自己感觉对算法还是比较感兴趣,于是想抽些时间简单的实现下。这样既可以对已经知道的东西进行下巩固,又可以学习些新的东西,而且过两天也该开学了,到时候写代码的机会可能就少了,顺便练练手 下面进入正文。

我们知道动态规划是求解全局最优解的有效方法,一般来说能用动态规划算法求解的问题具有以下
个显著特称:
        1)具有最优子结构,也就是说可以递归的定义最优解。
        2)这些最优子结构存在很多的重叠,就像递归的求解斐波那契数列一样,会导致很多子问题求解不止一次,这将导致算法复杂度急剧增加。
   
下面结合具体例子进行说明:
       此处选择的问题是编辑距离的求法,所谓的编辑距离,是如下定义的:
       存在两个字符串A和B,对A进行四中操作:copy、delete、insert和replace,将A转换为B,在此过程中所进行的操作代价最小的过程就是编辑距离了。例如字符串algorithm可以经过上面
       所说四中操作转换为altruistic。在进行求解的工程中,我们要对上述四种操作的代价进行定义,要注意的是copy和replace的代价要小于delete和insert,否则的话copy和replace操作都不
       会使用。
   
   下面利用动态规划算法进行求解:
    首先,要找出最优子结构,假设原字符串为x[1,...,i],目标字符串为y[1,...,j],编辑距离定义为c[i,j],于是我们可以得到如下的公式:
                c[i,j] = min{c[i-1,j]+cost(delete),c[i,j-1]+cost(insert),c[i-1,j-1]+cost(x[i]==y[j]?copy:replace)}
    其中cost代表代价。这就是这个问题的最优子结构啦,之所以分成以上几种情况是因为,最优解 c[i,j]的上一步有四种可能,也就是上面所说的四种操作啦。我们可以明显的看到,如果要是
  递归的求解上述问题会出现很多重叠子问题,例如,在递归求解c[i,j]时,我们就得求解四次 c[i-1,j-1]子问题。这也就是动态规划问题的第二个特征啦。
    接下来,通过编程实现。
    我们知道,从另一个方面看,动态规划问题就是一种自底而上填表的过程(dynamic programming中的programming就是用表格求解的意思)。接下来还是以上面的将algorithm转换
  为altruistic
为例进行说明。我们以横轴表示altruistic,以纵轴表示algorithm,所填的表格如下:
  

 此处只是为了方便没有自己去画,而是通过程序进行打印而已。此处定义copy代价为1,delete的代价为2,所以第一列 和第一行会是那样。
 下面给出主要的代码:

点击(此处)折叠或打开

  1. static const int COPY_COST      = 1;
  2. static const int REPLACE_COST   = 1;
  3. static const int DELETE_COST    = 2;
  4. static const int INSERT_COST    = 2;

  5. enum status{DELETE,INSERT,COPY,REPLACE};

  6. void edit_distance(const std::string src,const std::string des){
  7.     size_t row = src.size();
  8.     size_t col = des.size();
  9.     std::vector<std::vector<size_t> >table(row,std::vector<size_t>(col));
  10.     std::vector<std::vector<status> >condition(row,std::vector<status>(col));
  11.     size_t i=0;
  12.     while(i<row){
  13.         table[i][0] = i*COPY_COST;
  14.         condition[i][0] = COPY;
  15.         ++i;
  16.     }
  17.     size_t j = 1;
  18.     while(j<col){
  19.         table[0][j] = j*DELETE_COST;
  20.         condition[0][j] = DELETE;
  21.         ++j;
  22.     }
  23.     for(i=1;i<row;++i){
  24.         for(j=1;j<col;++j){
  25.             size_t x = table[i][j-1]+INSERT_COST;
  26.             size_t y = table[i-1][j]+DELETE_COST;
  27.             size_t z = table[i-1][j-1] + (src[i]==des[j] ? (COPY_COST) : (REPLACE_COST));
  28.             if(x<y){
  29.                 if(x<z){
  30.                     table[i][j]=x;
  31.                     condition[i][j] = INSERT;
  32.                 }
  33.                 else{
  34.                     table[i][j]=z;
  35.                     condition[i][j] = src[i]==des[j]?COPY:REPLACE;
  36.                 }
  37.             }
  38.             else{
  39.                 if(y<z){
  40.                     table[i][j]=y;
  41.                     condition[i][j] = DELETE;
  42.                 }
  43.                 else{
  44.                     table[i][j]=z;
  45.                     condition[i][j] = src[i]==des[j]?COPY:REPLACE;
  46.                 }
  47.             }
  48.         }
  49.     }
  50. }
此处列去了如何得到结果的一些列操作,那个是保存在condition中的,只需递归的输出下就可以了 。

参考文献:
 算法导论:192~221
  此文出处:http://blog.chinaunix.net/uid-28311809-id-3874518.html
阅读(836) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~