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;}

动态规划法总结到此结束啦!

本文标签: 动态规划法解决的问题