xxxxx实验报告
课程名称： _算法设计与分析 项目名称：_分支限界法实现_
姓名：_xxxxx专业：xxxxxxx班级：__xxxxxxx_学号：__xxxxxxxxxxxxxxxxx__同组成员____无_______
实验报告成绩（百分制）__________ 实验指导教师签字：__________
第二篇：分枝限界法_实验报告
一、课题名称
用分枝限界法求解单源最短路径问题
二、课题内容和要求
设计要求：学习算法设计中分枝限界法的思想，设计算法解决数据结构中求解单源最短路径问题，编程实现：
（1）给出指定源点的单源最短路径；
（2）说明算法的时间复杂度。
三、需求分析
1.实现极小堆的创建，用来存储活结点表。
2.实现循环队列的创建、初始化、入队、出队等操作。
3.实现分支限界法来实现求解单元最短路径的算法。
4.实现最短路径的正确输出。
四、概要设计
建立工程MinPath.dsw,加入源文件main.cpp，头文件CirQueue.h,init.h，Minpath.h和output.h. CirQueue.h中实现极小堆的创建，循环队列的创建、初始化、入队、出队等操作，Minpath.h中实现分支限界法来实现求解单元最短路径的算法。output.h中实现最短路径的正确输出。如下图所示：
实验用例如下，通过邻接矩阵的方式写在init.h中：
五、详细设计
main函数：
#include<iostream.h>
#include"init.h"
#include"CirQueue.h"
#include"MinPath.h"
#include"output.h"
void main()
{
int k;
int q;
cout<<"------------欢迎使用本系统---------------"<<endl;
cout<<"------------请选择单元路径的起点：---------------"<<endl;
cout<<"------------提示：输入"<<1<<"到"<<n-1<<"之间的整数---------------"<<endl;
cin>>k;
cout<<"------------请选择单元路径的终点：---------------"<<endl;
cin>>q;
while(k<1||k>11)
{
cout<<"------------提示：输入"<<1<<"到"<<n-1<<"之间的数，请重新输入---------------"<<endl;
cin>>k;
}
MinPath(k);
output(k,q);
}
init.h
const int size = 200;
const int inf = 1000; //两点距离上界置为1000
const int n = 12; //图顶点个数加1
int prev[n]; //图的前驱顶点
int dist[] = {0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf}; //最短距离数组
int c[n][n] = {{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,2,3,4,inf,inf,inf,inf,inf,inf,inf},
{0,inf,0,3,inf,7,2,inf,inf,inf,inf,inf},
{0,inf,inf,0,inf,inf,9,2,inf,inf,inf,inf},
{0,inf,inf,inf,0,inf,inf,2,inf,inf,inf,inf},
{0,inf,inf,inf,inf,0,inf,inf,3,3,inf,inf},
{0,inf,inf,inf,inf,inf,0,1,inf,3,inf,inf},
{0,inf,inf,inf,inf,inf,inf,0,inf,5,1,inf},
{0,inf,inf,inf,inf,inf,inf,inf,0,inf,inf,3},
{0,inf,inf,inf,inf,inf,inf,inf,inf,0,inf,2},
{0,inf,inf,inf,inf,inf,inf,inf,inf,2,inf,2},
{0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0},}; //图的邻接矩阵
CirQueue.h
class MinHeapNode//创建极小堆用来存储活结点表
{
public :
int i; //顶点编号
int length; //当前路长
};
class CirQueue//循环队列
{
private:
int front,rear;//头指针和尾指针
MinHeapNode data[size];
public:
CirQueue()//初始化建空队列
{
front = rear = 0;
}
void queryIn(MinHeapNode e)//元素入队操作
{
if((rear +1)%size != front)//队列未满
{
rear = (rear+1)%size; //插入新的队尾元素
data[rear] = e; //在队尾插入元素
}
}
void queryOut()//元素出队操作
{
if(rear != front)
{
front = (front+1)%size; //删除队头元素
}
}
MinHeapNode getQuery()//读取队头元素，但不出队
{
if(rear != front)
{
return data[(front+1)%size];
}
return data[1];
}
bool empty()//判断队列是否为空
{
return front == rear;
}
bool full()//判断队列是否为满
{
return (rear +1)%size == front;
}
};//CirQueue结束
MainPath.h
void MinPath(int v)
{
CirQueue s;//定义源为初始扩展结点
MinHeapNode e;
e.i = v;
e.length = 0;
dist[v] = 0;
s.queryIn(e); //将源节点加入队列
while(true){
for(int j = 1;j<n;j++){
if(j>=n)
{
break;
}
MinHeapNode m = s.getQuery();
if((c[m.i][j]<inf)&&(m.length + c[m.i][j] < dist[j]))//顶点i到顶点j可达，且从源出发途经i到j的路径长度小于当前最优路径长度
{
dist[j] = m.length + c[m.i][j];
prev[j] = m.i;
MinHeapNode mi;//加入活结点优先队列
mi.i = j;
mi.length = dist[j];
if(s.full())
{
break;
}
s.queryIn(mi); //元素入队
}
}//for循环结束
if(s.empty())
{
break;
}
s.queryOut(); //当该结点的孩子结点全部入队后，删除该结点
}//while循环结束
}//方法结束
output.h
void output(int k,int q)
{
int q1=q;
if(dist[q1]==1000){
cout<<"------------找不到此路径---------------"<<endl;
return;
}
cout<<"最短路径长为: "<<dist[q1]<<endl;
cout<<"单源最短路径为: ";
int a[12]={0};
int t =q1;
int s=0;
for(int i=0;t!=k;i++)
{
a[i] = prev[t];
t = prev[t];
s=s+1;
}
for(i=s-1;i>-1;i--) {
cout<<a[i]<<" ";
}
cout<<q1;
cout<<endl<<"------------欢迎使用本系统---------------"<<endl;
}
六、测试数据及其结果分析
1.选择起点：1，终点：11
1到11最短路径长为8，为1->3->7->10->11所获得。
2.选择起点：2，终点：9
2到9最短路径长为5，为2->6->9所获得。
3.选择起点8，终点2
8到2没有路径，输出“找不到此路径”。
4.选择起点11，终点1
11到1没有路径，输出“找不到此路径”。
七、调试过程中的问题
1.CirQueue.h中，函数getQuery()中在调试过程中出现warnig: 'CirQueue::getQuery' : not all control paths return a value.
解决方案：在if语句下面加上return data[1];使当rear = front时函数也返回一个值。
2.当两结点间没有路径时，程序执行时出现错误。
解决方案：在输出函数output中加入下面代码
if(dist[q1]==1000){
cout<<"------------找不到此路径---------------"<<endl;
return;
}
即当两结点无路径时，输出提示“找不到此路径”，程序执行时不会崩溃。
3.输出过程中，如何使结点按顺序输出？
定义一个数组a[],应用递归对存储前驱结点的数组prev[]从后往前求解，将得到的值赋给数组a[],最后逆向输出对应的数组a[],即得到正确的路径顺序。如下：
for(int i=0;t!=k;i++)
{
a[i] = prev[t];
t = prev[t];
s=s+1;
}
for(i=s-1;i>-1;i--) {
cout<<a[i]<<" ";
}
八、程序设计总结
本次实验回顾了用分枝限界法求解单源最短路径问题的思想，运用了优先权队列和堆的一些知识，对以前学过的东西有了进一步的认识，也认识到以前学习上的疏漏和不足，算法的时间复杂度是O(n^2)。本来设计中没有考虑终点可变的情形，后来通过对output.h中输出函数的修改，加入一个变量k,对函数进行相应的修改不断地调试，最终得到正确的结果，本次实验对编程能力尤其是调试和改进程序的能力有了较大的提高。