《算法设计与分析》实验报告Word下载.docx
《《算法设计与分析》实验报告Word下载.docx》由会员分享，可在线阅读，更多相关《《算法设计与分析》实验报告Word下载.docx（20页珍藏版）》请在冰点文库上搜索。
由于限界函数的不同，下界为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<
n;
j++）
if（colable[j]==1&
&
row[j]==1）//节点没有被访问
if（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<
i++）
{
colable[i]=1;
}
introw[n];
for（i=0;
row[i]=1;
inta[n][n];
for（j=0;
if（i!
=j）
scanf（"
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;
city_number;
distance[i]=newint[city_number];
if（i==j）
distance[i][j]=0;
else
cin>
>
distance[i][j];
//生成过程矩阵
process=newint*[city_number];
process[i]=newint[1<
<
（city_number-1）];
//动态规划法求最短路径
voidTsp:
getShoretstDistance（）
inti,j,k;
//初始化第一列
process[i][0]=distance[i][0];
//初始化剩余列
for（j=1;
（1<
（city_number-1））;
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++）
//不能达到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<
process[0][（1<
（city_number-1））-1]<
endl;
//主函数
intmain（void）
intcity_number;
while（cin>
city_number）
Tsptsp（city_number）;
//初始化城市代价矩阵
tsp.getShoretstDistance（）;
//求出最短路径
#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））{
bestp=a[x[n]][1]+cp;
for（inti=1;
=n;
i++）{
bestx[i]=x[i];
}else{
for（inti=t;
/*约束为当前节点到下一节点的长度不为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]];
cin>
//顶点数
x[i]=i;
for（intj=1;
j++）{
if（i==j）{
a[i][j]=0;
}else{
a[i][j];
backpack
（2）;
bestp<
#defineINF0x3f3f3f3f
intmp[100][100];
voidin（）
scanf（"
n）;
for（inti=1;
i<
i++）
for（intj=1;
j<
j++）
if（i==j）
mp[i][j]=INF;
continue;
mp[i][j]）;
structnode
intvisp[22];
//标记哪些点走了
intst;
//起点
intst_p;
//起点的邻接点
inted;
//终点
inted_p;
//终点的邻接点
intk;
//走过的点数
intsumv;
//经过路径的距离
intlb;
//目标函数的值
booloperator<
（constnode&
p）const
returnlb>
p.lb;
priority_queue<
node>
q;
intlow,up;
intinq[22];
//确定上界
intdfs（intu,intk,intl）
if（k==n）returnl+mp[u][1];
intminlen=INF,p;
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;
//起点和终点连出来的边
if（p.visp[i]==0&
min1>
mp[i][p.st]）
min1=mp[i][p.st];
ret+=min1;
min2>
mp[p.ed][i]）
min2=mp[p.ed][i];
ret+=min2;
if（p.visp[i]==0）
min1=min2=INF;
if（min1>
mp[i][j]）
min1=mp[i][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;
/*通过排序求两个最小值*/
inttmpA[22];
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;
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;
if（tmp.visp[i]==0）
break;
intans=tmp.sumv+mp[p][tmp.st]+mp[tmp.ed][p];
nodejudge=q.top（）;
/*如果当前的路径和比所有的目标函数值都小则跳出*/
if（ans<
=judge.lb）
ret=min（ans,ret）;
/*否则继续求其他可能的路径和，并更新上界*/
else
up=min（up,ans）;
ret=min（ret,ans）;
/*当前点可以向下扩展的点入优先级队列*/
nodenext;
next.st=tmp.st;
/*更新路径和*/
next.sumv=tmp.sumv+mp[tmp.ed][i];
/*更新最后一个点*/
next.ed=i;
/*更新顶点数*/
next.k=tmp.k+1;
/*更新经过的顶点*/
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;
in（）;
solve（）;
四、运行输出结果：
（1）蛮力法：
（2）动态规划法：
（3）回溯法：
（4）分支限界法：
五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：
1、首先是部分函数以及头文件的使用，在编写程序过程中经常会遇到需要使用自带或额外编写函数，经常需要查询相关资料。
2、代码运行时需要对oj上题目所要求的输入输出进行对应修改，否则会得到wronganswer。
3、由于算法的不同需要使用不同的数据结构进行存储，在数据结构的切换时会出现各种各样的问题，查询资料并逐步调试可以解决。
六、算法与代码的对应与解释（抽讲）
借助矩阵把问题转换为矩阵中点的求解。
首先构造距离矩阵，任意节点到自身节点的距离为无穷大。
在第一行找到最小项a[1][j]，从而跳转到第j行，再找到最小值a[j][k]，再到第k行进行查找……然后构造各行允许数组row[n]={1,1…1}，各列允许数组colable[n]={0,1,1….1}，其中1表示允许访问，即该节点未被访问；
0表示不允许访问，即该节点已经被访问。
如果改行或该列不允许访问，跳过该点访问下一节点。
程序再发问最后一个节点前，所访问的行中至少有1个允许访问的节点，依次访问这些节点找到最小的即可；
在访问最后一个节点后，再次访问，会返回k=0，即实现访问源节点，得出一条简单回路。
假设从顶点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}）是一个子问题。
确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先方式搜索整个解空间。
这个开始结点成为活结点，同时也成为当前的扩展结点处，搜索向纵深方向移至一个新结点。
这个新结点即成为新的活结点，并为当前扩展结点。
如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。
此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。
回溯法以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。
算法开始时创建一个最小堆，用于表示活结点优先队列。
堆中每个结点的子树费用的下界lcost值是优先队列的优先级。
接着算法计算出图中每个顶点的最小费用出边并用minout记录。
如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。
如果每个顶点都有出边，则根据计算出的minout作算法初始化。
升级会员 