《算法设计与分析》实验报告 下载本文

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

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

学 号: 日 期:

一、实验内容:

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