文件名称:3-17
- 所属分类：
- 人工智能/神经网络/遗传算法
- 资源属性：
- 上传时间：
- 2017-12-20
- 文件大小：
- 267kb
- 下载次数：
- 0次
- 提 供 者：
- ma***
- 相关连接：
- 无
- 下载说明：
- 别用迅雷下载，失败请重下，重下不扣分！
介绍说明－－下载内容均来自于网络，请自行研究使用
字符串比较问题
问题分析：解答此题需要一个较为巧妙的解题思路。解决此题可以借用“最长公共子串”问题的解题思路。采用自底向上的动态规划思想。假设对于给定的字符串A，B长度分别为m,n，A[1..m],B[1..n],这里可以使用变量val[m][n]表示A,B的扩展距离。
对于字符串A[1..m],B[1..n],有以下两种情况：
1.A[m]和B[n]处在扩展字符串的同一个位置，那么val[m][n]=val[m-1][n-1]+abs(A[m]-B[n])。
2.A[m]和B[n]不在扩展字符串的同一个位置，则val[m][n]=min{val[m-1][n]+k,val[m][n-1]+k}。
综上，val[m][n]=min{val[m-1][n]+k，val[m][n-1]+k，val[m-1][n-1]+abs(A[m]-B[n])}
由上述递推式，采用自底向上的方法在多项式时间内即可求出val[m][n](String comparison problem)
问题分析：解答此题需要一个较为巧妙的解题思路。解决此题可以借用“最长公共子串”问题的解题思路。采用自底向上的动态规划思想。假设对于给定的字符串A，B长度分别为m,n，A[1..m],B[1..n],这里可以使用变量val[m][n]表示A,B的扩展距离。
对于字符串A[1..m],B[1..n],有以下两种情况：
1.A[m]和B[n]处在扩展字符串的同一个位置，那么val[m][n]=val[m-1][n-1]+abs(A[m]-B[n])。
2.A[m]和B[n]不在扩展字符串的同一个位置，则val[m][n]=min{val[m-1][n]+k,val[m][n-1]+k}。
综上，val[m][n]=min{val[m-1][n]+k，val[m][n-1]+k，val[m-1][n-1]+abs(A[m]-B[n])}
由上述递推式，采用自底向上的方法在多项式时间内即可求出val[m][n](String comparison problem)
相关搜索： 算法
(系统自动生成,下载前可以参看下载内容)
下载文件列表
| 文件名 | 大小 | 更新时间 |
|---|---|---|
| 3-17 | ||
| 3-17\3-17.cbp | 1097 | 2017-11-29 |
| 3-17\3-17.depend | 114 | 2017-11-29 |
| 3-17\3-17.layout | 322 | 2017-11-30 |
| 3-17\bin | ||
| 3-17\bin\Debug | ||
| 3-17\bin\Debug\3-17.exe | 982092 | 2017-11-29 |
| 3-17\main.cpp | 1012 | 2017-11-29 |
| 3-17\obj | ||
| 3-17\obj\Debug | ||
| 3-17\obj\Debug\main.o | 29677 | 2017-11-29 |
| 3-17\字符串比较.txt | 12 | 2017-11-29 |