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

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

《《算法设计与分析》实验报告.docx》由会员分享，可在线阅读，更多相关《《算法设计与分析》实验报告.docx（20页珍藏版）》请在冰点文库上搜索。

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

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

学号：

姓名：

日期：

得分：

一、实验内容：

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）基本思想

回溯法求解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）。

三、源程序及注释：

1、蛮力法

intmin（inta[],intcolable[],intn,introw[]）

{

intj=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;

}

}

}

returnk;

}

intmain（）{

inti,j,s=0;

intn;

while（scanf（"%d",&n））{

intcolable[n];

colable[0]=0;

//对各列允许矩阵进行赋值

for（i=1;i

{

colable[i]=1;

}

introw[n];

for（i=0;i

{

row[i]=1;

}

inta[n][n];

for（i=0;i

{

for（j=0;j

{

if（i!

=j）

scanf（"%d",&a[i][j]）;

elsea[i][j]=inf;

}

}

i=0;

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（"%d\n",s）;

}

return0;

}

2、动态规划法

classTsp

{

private:

intcity_number;//城市个数

int**distance;//城市距离矩阵

int**process;//求最短路径的过程矩阵

public:

Tsp（intcity_number）;//构造函数

voidgetShoretstDistance（）;//动态规划法求最短路径

};

//构造函数

Tsp:

:

Tsp（intcity_num）

{

inti=0,j=0;

city_number=city_num;

//初始化城市距离矩阵

distance=newint*[city_number];

for（i=0;i

{

distance[i]=newint[city_number];

for（j=0;j

if（i==j）

distance[i][j]=0;

else

cin>>distance[i][j];

}

//生成过程矩阵

process=newint*[city_number];

for（i=0;i

{

process[i]=newint[1<<（city_number-1）];

}

}

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

voidTsp:

:

getShoretstDistance（）

{

inti,j,k;

//初始化第一列

for（i=0;i

{

process[i][0]=distance[i][0];

}

//初始化剩余列

for（j=1;j<（1<<（city_number-1））;j++）

{

for（i=0;i

{

process[i][j]=0x7ffff;//设0x7ffff为无穷大

//对于数字x，要看它的第i位是不是1，通过判断布尔表达式（（（x>>（i-1））&1）==1的真值来实现

if（（（j>>（i-1））&1）==1）

{

continue;

}

for（k=1;k

{

//不能达到k城市

if（（（j>>（k-1））&1）==0）

{

continue;

}

if（process[i][j]>distance[i][k]+process[k][j^（1<<（k-1））]）

{

process[i][j]=distance[i][k]+process[k][j^（1<<（k-1））];

}

}

}

}

cout<

}

//主函数

intmain（void）

{

intcity_number;

while（cin>>city_number）

{

Tsptsp（city_number）;//初始化城市代价矩阵

tsp.getShoretstDistance（）;//求出最短路径

}

return0;

}

3、回溯法

#defineMAX100

usingnamespacestd;

intn;//城市个数

inta[MAX][MAX];//城市间距离

intx[MAX];//记录路径

intbestx[MAX]={0};//记录最优路径

intbestp=63355;//最短路径长

intcp=0;//当前路径长

voidbackpack（intt）{

if（t>n）{

if（（a[x[n]][1]）&&（a[x[n]][1]+cp

bestp=a[x[n]][1]+cp;

for（inti=1;i<=n;i++）{

bestx[i]=x[i];

}

}

}else{

for（inti=t;i<=n;i++）{

/*约束为当前节点到下一节点的长度不为0,限界为走过的长度+当前要走的长度之和小于最优长度*/

if（（a[x[t-1]][x[i]]）&&（cp+a[x[t-1]][x[i]]

swap（x[t],x[i]）;

cp+=a[x[t-1]][x[t]];

backpack（t+1）;

cp-=a[x[t-1]][x[t]];

swap（x[t],x[i]）;

}

}

}

}

intmain（）{

cin>>n;//顶点数

for（inti=1;i<=n;i++）{

x[i]=i;

}

for（inti=1;i<=n;i++）{

for（intj=1;j<=n;j++）{

if（i==j）{

a[i][j]=0;

}else{

cin>>a[i][j];

}

}

}

backpack

（2）;

cout<

return0;

}

4、分支限界法

#defineINF0x3f3f3f3f

intn;

intmp[100][100];

voidin（）

{

scanf（"%d",&n）;

for（inti=1;i<=n;i++）

{

for（intj=1;j<=n;j++）

{

if（i==j）

{

mp[i][j]=INF;

continue;

}

scanf（"%d",&mp[i][j]）;

}

}

}

structnode

{

intvisp[22];//标记哪些点走了

intst;//起点

intst_p;//起点的邻接点

inted;//终点

inted_p;//终点的邻接点

intk;//走过的点数

intsumv;//经过路径的距离

intlb;//目标函数的值

booloperator<（constnode&p）const

{

returnlb>p.lb;

}

};

priority_queueq;

intlow,up;

intinq[22];

//确定上界

intdfs（intu,intk,intl）

{

if（k==n）returnl+mp[u][1];

intminlen=INF,p;

for（inti=1;i<=n;i++）

{

if（inq[i]==0&&minlen>mp[u][i]）/*取与所有点的连边中最小的边*/

{

minlen=mp[u][i];

p=i;

}

}

inq[p]=1;

returndfs（p,k+1,l+minlen）;

}

intget_lb（nodep）

{

intret=p.sumv*2;//路径上的点的距离

intmin1=INF,min2=INF;//起点和终点连出来的边

for（inti=1;i<=n;i++）

{

if（p.visp[i]==0&&min1>mp[i][p.st]）

{

min1=mp[i][p.st];

}

}

ret+=min1;

for（inti=1;i<=n;i++）

{

if（p.visp[i]==0&&min2>mp[p.ed][i]）

{

min2=mp[p.ed][i];

}

}

ret+=min2;

for（inti=1;i<=n;i++）

{

if（p.visp[i]==0）

{

min1=min2=INF;

for（intj=1;j<=n;j++）

{

if（min1>mp[i][j]）

min1=mp[i][j];

}

for（intj=1;j<=n;j++）

{

if（min2>mp[j][i]）

min2=mp[j][i];

}

ret+=min1+min2;

}

}

returnret%2==0?

（ret/2）:

（ret/2+1）;

}

voidget_up（）

{

inq[1]=1;

up=dfs（1,1,0）;

}

voidget_low（）

{

low=0;

for（inti=1;i<=n;i++）

{

/*通过排序求两个最小值*/

intmin1=INF,min2=INF;

inttmpA[22];

for（intj=1;j<=n;j++）

{

tmpA[j]=mp[i][j];

}

sort（tmpA+1,tmpA+1+n）;//对临时的数组进行排序

low+=tmpA[1];

}

}

intsolve（）

{

/*贪心法确定上界*/

get_up（）;

/*取每行最小的边之和作为下界*/

get_low（）;

/*设置初始点,默认从1开始*/

nodestar;

star.st=1;

star.ed=1;

star.k=1;

for（inti=1;i<=n;i++）star.visp[i]=0;

star.visp[1]=1;

star.sumv=0;

star.lb=low;

/*ret为问题的解*/

intret=INF;

q.push（star）;

while（!

q.empty（））

{

nodetmp=q.top（）;

q.pop（）;

if（tmp.k==n-1）

{

/*找最后一个没有走的点*/

intp;

for（inti=1;i<=n;i++）

{

if（tmp.visp[i]==0）

{

p=i;

break;

}

}

intans=tmp.sumv+mp[p][tmp.st]+mp[tmp.ed][p];

nodejudge=q.top（）;

/*如果当前的路径和比所有的目标函数值都小则跳出*/

if（ans<=judge.lb）

{

ret=min（ans,ret）;

break;

}

/*否则继续求其他可能的路径和，并更新上界*/

else

{

up=min（up,ans）;

ret=min（ret,ans）;

continue;

}

}

/*当前点可以向下扩展的点入优先级队列*/

nodenext;

for（inti=1;i<=n;i++）

{

if（tmp.visp[i]==0）

{

next.st=tmp.st;

/*更新路径和*/

next.sumv=tmp.sumv+mp[tmp.ed][i];

/*更新最后一个点*/

next.ed=i;

/*更新顶点数*/

next.k=tmp.k+1;

/*更新经过的顶点*/

for（intj=1;j<=n;j++）next.visp[j]=tmp.visp[j];

next.visp[i]=1;

/*求目标函数*/

next.lb=get_lb（next）;

/*如果大于上界就不加入队列*/

if（next.lb>up）continue;

q.push（next）;

}

}

}

returnret;

}

intmain（）{

in（）;

cout<

return0;

}

四、运行输出结果：

（1）蛮力法：

（2）动态规划法：

（3）回溯法：

（4）分支限界法：

五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：

1、首先是部分函数以及头文件的使用，在编写程序过程中经常会遇到需要使用自带或额外编写函数，经常需要查询相关资料。

2、代码运行时需要对oj上题目所要求的输入输出进行对应修改，否则会得到wronganswer。

3、由于算法的不同需要使用不同的数据结构进行存储，在数据结构的切换时会出现各种各样的问题，查询资料并逐步调试可以解决。

六、算法与代码的对应与解释（抽讲）

（1）蛮力法：

借助矩阵把问题转换为矩阵中点的求解。

首先构造距离矩阵，任意节点到自身节点的距离为无穷大。

在第一行找到最小项a[1][j]，从而跳转到第j行，再找到最小值a[j][k]，再到第k行进行查找……然后构造各行允许数组row[n]={1,1…1}，各列允许数组colable[n]={0,1,1….1}，其中1表示允许访问，即该节点未被访问；0表示不允许访问，即该节点已经被访问。

如果改行或该列不允许访问，跳过该点访问下一节点。

程序再发问最后一个节点前，所访问的行中至少有1个允许访问的节点，依次访问这些节点找到最小的即可；在访问最后一个节点后，再次访问，会返回k=0，即实现访问源节点，得出一条简单回路。

（2）动态规划法：

假设从顶点s出发，令d（i,V’）表示从顶点i出发经过V’（是一个点的集合）中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。

推导：

（分情况来讨论）

①当V’为空集，那么d（i,V’），表示从i不经过任何点就回到s了，如上图的城市3->城市0（0为起点城市）。

此时d（i,V’）=Cis（就是城市i到城市s的距离）、

②如果V’不为空，那么就是对子问题的最优求解。

你必须在V’这个城市集合中，尝试每一个，并求出最优解。

d（i,V’）=min{Cik+d（k,V’-{k}）}

注：

Cik表示你选择的城市和城市i的距离，d（k,V’-{k}）是一个子问题。

（3）回溯法：

确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先方式搜索整个解空间。

这个开始结点成为活结点，同时也成为当前的扩展结点处，搜索向纵深方向移至一个新结点。

这个新结点即成为新的活结点，并为当前扩展结点。

如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。

此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。

回溯法以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。

（4）分支限界法：

算法开始时创建一个最小堆，用于表示活结点优先队列。

堆中每个结点的子树费用的下界lcost值是优先队列的优先级。

接着算法计算出图中每个顶点的最小费用出边并用minout记录。

如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。

如果每个顶点都有出边，则根据计算出的minout作算法初始化。