分支限界法实现单源最短路径.doc

______________________________________________________________________________________________________________

算法分析与设计实验报告
分支限界法实现单源最短路径

班级： 11计算机1
学号： 110104200109
姓名： 金李扬
日期： 5.22

1.问题描述

以分支限界法实现单源最短路径
1.以分支限界实现优先队列
2.再以分支限界法的优先队列实现单元最短路径

以该图为算法测试数据，获得链接矩阵如下：
以-1代表无法到达的点
-1 2 3 4 -1 -1 -1 -1 -1 -1 -1
-1 -1 3 -1 7 2 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 9 2 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 3 3 -1 -1
-1 -1 -1 -1 -1 -1 1 -1 3 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 5 1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

2.算法思想

分支限界法基本思想：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

算法步骤
1.用一极小堆来存储活结点表，其优先级是结点所对应的当前路长。
2.算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。

剪枝函数
1.在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。
2.在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。

3.算法设计
1.定义HEAPNODE结构体：
typedef struct HeapNode {
int left, right;
int weight;
bool friend operator < (const HeapNode &a, const HeapNode &b) {
return a.weight > b.weight;
}
int i,length;
HeapNode() { }
HeapNode(int ii,int l)
{
i=ii;
length=l;
}
};
2.以堆实现优先队列类：
#define MAXN 25500
class priority_queue {
private :
HeapNode r[MAXN];
int length;

void heap_adjust(int s, int m) {
HeapNode rc = r[s];
for (int j = s << 1; j <= m; j <<= 1) {
if (j < m && r[j] < r[j+1]) j++;
if (!(rc < r[j])) break;
r[s] = r[j]; s = j;
}
r[s] = rc;
}

public :
priority_queue() {
length = 0;
}
/*===========下面是堆操作部分，建堆，堆排等=============*/

void creat_heap() {
for (int i = length >> 1; i > 0; i--) {
heap_adjust(i, length);
}
}

void set_size(int length) {
this->length = length;
}

void set_value(int id, HeapNode value) {
r[id] = value;
}

void heap_sort() {
for (int i = length; i > 1; i--) {
HeapNode tmp = r[1];
r[1] = r[i];
r[i] = tmp;
heap_adjust(1, i - 1);
}
}

bool is_heap() {
int len = length >> 1 - 1, j;
if (len < 1) {
if (length == 1 || (!(r[1] < r[length])
&& !(r[1] < r[length - 1])))
return true;
return false;
}
for (int i = 1; i <= len; i++) {
j = i << 1;
if (r[j] < r[j + 1]) j++;
if (r[i] < r[j]) return false;
}
return true;
}

/* 用堆实现的priority_queue */
void push(HeapNode rc) {
++length;
r[length] = rc;
int s = length >> 1;
for (int j = length; j > 1; j >>= 1) {
if (!(r[s] < r[j])) break;
HeapNode tmp = r[s];
r[s] = r[j];
r[j] = tmp;
s >>= 1;
}
}

void pop() {
HeapNode tmp = r[1];
r[1] = r[length];
r[length] = tmp;
heap_adjust(1, --length);
}

HeapNode top() {
return r[1];
}

int size() {
return length;
}

bool empty() {
if (length <= 0)
return true;
return false;
}
};

3.分支限界法实现单源最短路径
void shorest(int v)
{
priority_queue heap;
HeapNode enode(v,0);
for(int i=1; i<=n; i++) dist[i]=MAX;
dist[v]=0;
while(1)
{
for(int j=1; j<=n; j++)
if(a[enode.i][j]<MAX && enode.length+a[enode.i][j]<dist[j])
{
dist[j]=enode.length+a[enode.i][j];
HeapNode node(j,dist[j]);
heap.push(node);
}
if(heap.empty()) break;
else
{
enode=heap.top();
heap.pop();
}
}
}

4.主函数
int main ()
{
cout<<"请输入节点个数:";
cin>>n;
cout<<"请输入n*n的链接矩阵:"<<endl;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
cin>>a[i][j];
if(a[i][j]==-1) a[i][j]=MAX;
}
shorest(1);
cout<<"从起始节点S到终点T最短路径为:"<<dist[n]<<endl;
return 0;
}

4.复杂度分析
1.分支限界法实现单源最短路径：n*n
2.优先队列：n*logn
n*n+n*logn=n*n;

5.结论

以分支限界法实现的单源最短路径复杂度比dijakstra算法高

Welcome To
Download !!!

欢迎您的下载，资料仅供参考！

精品资料