内容发布更新时间 : 2024/11/9 9:41:26星期一 下面是文章的全部内容请认真阅读。

《算法设计与分析》实验报告

学 号： 日 期：

一、实验内容：

TSP问题。

二、所用算法的基本思想及复杂度分析：

1、 蛮力法

1） 基本思想

找出所有可能的旅行路线，即以次考虑图中所有顶点的全排列，从中选取路径长度最短的哈密顿回路（也称为简单回路）。

2） 复杂度分析

蛮力法求解TSP问题必须依次考察顶点集合的所有全排列，从中找出路径长度最短的简单回路，因此，其时间下界是Ω(n!)。 2、 动态规划法

1） 基本思想

TSP问题满足最优性原理。对于图G=(V,E)，假设从顶点i出发，令V’=V-I，则d(i,V’)表示从顶点i出发经过V’中各个顶点一次且仅一次，最后回到出发点i的最短路径长度。显然初始子问题为d(k,{ })，即从顶点i出发只经过顶点k回到顶点i。现在考虑原问题的一部分，d(k,V’-{k})表示从顶点k出发经过V’-{k}中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，则：

d(k,{ })=Cki

d(i,V’)=min{Cik+d(k,V’-{k})}(k∈V’) 2） 复杂度分析

算法需要对顶点集合{1,2，…，n-1}的每一个子集进行操作，因此，时间复杂性为Ω(2n)。 3、 回溯法

1

姓 名： 得 分：

1） 基本思想

回溯法求解TSP问题，首先把所有的顶点的访问标志初始化为0，然后在解空间树中从根节点出发开始搜索，如果从根节点到当前结点对应一个部分解，即满足上述约束条件，则在当前结点处选择第一棵子树继续搜索，否则，对当前子树的兄弟结点进行搜索，如果当前结点的所有子树都已尝试过并且发生冲突，则回溯到当前结点的父节点。采用邻接矩阵mp[n][n]存储顶点之间边的情况，为避免在函数间传递参数，将数组mp设置为全局变量，设数组x[n]表示哈密顿回路经过的顶点。

2） 复杂度分析

在哈密顿回路的可能解中，考虑到约束条件xi!=xj(1<=I,j<=n,i!=j),则可能解应该是（1,2,…,n）的一个排列，对应的解空间树种至少有n!个叶子结点，每个叶子结点代表一种可能解。当找到可行的最优解时，算法停止。根据递归条件不同时间复杂度也会不同，这里为O（n！）。 4、 分支限界法

1） 基本思想

首先确定目标函数的界[down,up]，可以用贪心法求得TSP问题的一个上界。对于无向图的代价矩阵，把矩阵中的每一行最小的元素相加，可以得到一个简单的下界。但还有一个信息量更大的下界：考虑一个TSP问题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个城市，另一条是离开这个城市的，那么，如果把矩阵中每一行最小的两个元素相加再除以2，假设图中的所有代价都是整数，在对这个结果向上取整，就得到了一个合理的下界。强调的是，这个解可能不是一个可行解（可能没有构成哈密顿回路），但给出了一个参考下界。

2） 复杂度分析

目标函数（限界函数），lb分为三部分，第一部分是经过路径的长度相加的2倍，加上第二部分离着路径首尾节点最近的距离相加（不在已知路径上的），加上第三部分除了路径上节点，矩阵中两个最短的距离相加，最后这三部分和相加，得到的结果除以2便是每个节点的限界值。由于限界函数的不同，下界为O（n），上界为O（2^n）。

2

三、源程序及注释：

1、蛮力法

int min(int a[],int colable[],int n,int row[]) {

int j=0,m=a[0],k=0;

while(colable[j]==0||row[j]==0) { j++; m=a[j]; }//求最短距离 for(;j

if(colable[j]==1&&row[j]==1)//节点没有被访问 {

if(m>=a[j]) {

m=a[j];//m始终保持最短距离 k=j; } } } return k; }

int main(){

int i,j,s=0;

int n;

while(scanf(\

int colable[n]; colable[0]=0;

3

//对各列允许矩阵进行赋值 for(i=1;i

colable[i]=1;

}

int row[n]; for(i=0;i

row[i]=1;

}

int a[n][n]; for(i=0;i

for(j=0;j

if(i!=j)

scanf(\

} i=0;

}

else a[i][j]=inf;

while(row[i]==1) {

j=min(a[i],colable,n,row); row[i]=0; colable[j]=0; s=s+a[i][j]; i=j;

}

printf(\

4

}

} return 0;

2、动态规划法

class Tsp { };

//构造函数

Tsp::Tsp(int city_num) {

private:

int city_number; int **distance; int **process;

//城市个数 //城市距离矩阵 //求最短路径的过程矩阵

public:

Tsp(int city_number);

//构造函数

//动态规划法求最短路径

void getShoretstDistance();

int i=0,j=0;

city_number=city_num;

//初始化城市距离矩阵

distance=new int*[city_number]; for(i=0;i

distance[i]=new int[city_number]; for(j=0;j

if(i==j)

distance[i][j]=0;

else

5