admin 管理员组文章数量: 894198
动态规划法解决的问题
近似串匹配问题
代码如下:
int min(int a,int b,int c){int t;if(a>b){t=a;a=b;b=t;}if(a>c){t=a;a=c;c=t;} return a;
}
int D[6][7]={0,1,2,3,4,5,6,1,0,1,2,3,4,5,2,1,1,2,3,3,4,3,2,2,1,2,3,4,4,3,3,2,1,2,3,5,4,4,3,2,2,2
};int ASM(char P[], char T[], int m, int n, int K){int i,j; for (j=1; j<=n; j++) //初始化第0行D[0][j]=0;for (i=0; i<=m; i++) //初始化第0列D[i][0]=i;for (j=1; j<=n; j++) //根据递推式依次计算每一列{for (i=1; i<=m; i++){if (P[i-1]==T[j-1]) D[i][j]=min(D[i-1][j-1], D[i-1][j]+1, D[i][j-1]+1);elseD[i][j]=min(D[i-1][j-1]+1, D[i-1][j]+1, D[i][j-1]+1);}if (D[m][j]<=K) return j;}}
多段图的最短路径问题
代码如下:
int arc[50][50];
const int MAX=1000;
int CreatGraph(){int i,j,k;int weight;int vnum,archum;//顶点个数和边的个数cin>>vnum>>archum;for(i=0;i<vnum;i++){for(j=0;j<vnum;j++)arc[i][j]=MAX; } for(k=0;k<archum;k++)//代价矩阵 {cin>>i>>j>>weight;arc[i][j]=weight;}return vnum;
}
int backPath(int n)
{int i,j,temp;int cost[50],path[50];for(i=1;i<n;i++){cost[i]=MAX;path[i]=-1;}cost[0]=0;path[0]=-1;for(j=0;j<n;j++){for(i=j-1;i>=0;i--){if(arc[i][j]+cost[i]<cost[j]){cost[j]=arc[i][j]+cost[i];path[j]=i;}}}cout<<n-1;i=n-1;while(path[i]>=0){cout<<"-"<<path[i];i=path[i];}return cost[n-1];
}
多源点的最短路径
代码如下;
void Floyd(int r[n][n],int dist[n][n])
{int i,j,k;for(i=0;i<n;i++)for(j=0;j<n;j++){dist[i][j]=arc1[i][j];} for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)if(dist[i][k]+dist[k][j]<dist[i][j])dist[i][j]=dist[i][k]+dist[k][j];
}
主函数测试示例如下:
int s;char P[]="happy";char T[]="hsppay";s=ASM(P, T, 5, 6, 2);cout<<s;
CreatGraph();cout<<"min="<<backPath(5);
int d[n][n];Floyd(arc1,d);
for(int i=0;i<n;i++){for(int j=0;j<n;j++)cout<<d[i][j]<<" ";cout<<endl;}
动态规划法总结到此结束啦!
本文标签: 动态规划法解决的问题
版权声明:本文标题:动态规划法解决的问题 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/jishu/1687604940h120222.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论