实验二:动态规划算法的应用
——旅行商问题
一、问题描述:
某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。他要选定一
条从驻地出发,经过每个城市一遍,最后回到驻地的路线,使总的路程(或旅费)最小。
例如:给定 4 个城市{1,2,3,4}及其各城市之间的路程
请设计出一个动态规划算法,并用程序实现如下功能:
1.任给一个输入实例,能输出最短路程及其路线
2.能用图形演示旅行商的推销路线
二、算法思想:
在无向完全图中,对于任意两个顶点 vi 和 vj,我们可以在多项式时间内找到 vi 和 vj 这
两个顶点之间的所有路径,选择其中路程最短的一条,令 S[i,j]表示 vi 和 vj 这两个顶点之
间最短距离的那条路径。搜索路径 S[i,j],找到 vi 到达的在 S[i,j]上的第一个顶点,记该顶
点为 vk,将其记录在数组中 R[][],递归查找 vi 到 vk 和 vk 到 vj 的最短路径及其相应权值,
最后将数组 D[]中的顶点和权值之和打印出来即为所求,并用画图函数将行经过程画出。
三、具体实现:
1. int Exp(int k)//计算 2 的 k 次方:二进制数左移一位实现*2
{
k=1<<k;
return k;
}
该函数用以计算 2 的 k 次方(二进制数左移一位实现*2 计算)。设计思想:用一个二进
制数来表示顶点集,其各位数值表示的含义为:当该位为 i=1 时表示顶点 i+1 在集合 s 中,
否则若 i=0 顶点 i+1 不在集合 s 中。例如 k = 1 表示顶点 2 在集合 s 中。对给定 n 个顶点,共
需要用 n-1 位二进制位来记录它的全部顶点。
2. int Readfile()//读入测试文件
{
int space,i,j;
char s[10];
printf("请输入数据文件名:");
gets(s);
if(freopen(s,"r",stdin)==NULL)
评论2
最新资源