贪新算法和分支限界法解单源最短路径

一、 问题描述与分析

1. 分支限界法解单源最短路径：

分支限界法类似于回溯法，是在问题的解空间树上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

常见的两种分支限界法： 1) 队列式(FIFO)分支限界法

按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 2) 优先队列式分支限界法

按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 单源最短路径问题适合于用分支限界法求解。

解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。 2. 贪新算法解单源最短路径：

Dijkstra算法是解单源最短路径问题的贪心算法。其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

二、 算法设计 1. 分支限界法：

Public class BBShortest {

Static class HeapNode implements Comparable {

Int I;

Float length;

HeapNode(int ii, float ll) { I=ii;

Length=ll; }

Public int comparator(Object x) {

Float xl=((HeapNode)x).length; If(lengthReturn 1; } }

Static float[][]a;

Public static void shortest(int v,float []dist,int []p) {

Int n=p.length-1;

MinHeap heap=new MinHeap(); //定义源为初始扩展节点

HeapNode enode=new HeapNode(v,0); for(int j=1;j<=n;j++)

dist[j]=Float.MAX_VALUE; dist[v]=0;

while (true) { // 搜索问题的解空间 for (int j=1;j<=n;j++)

if(a[enode.i][j] < Float.MAX_VALUE && enode.length+a[enode.i][j] < dist[j])

{// 顶点i到顶点j可达，且满足控制约束 dist[j]=enode.length+a[enode.i][j]; p[j]=enode.i;

HeapNode node = new HeapNode(j,dist[j]); heap.put(node); // 加入活结点优先队列 }

if (heap.isEmpty()) break;

else enode = (HeapNode) heap.removeMin(); } } }

2. 贪新算法：

public static void dijkstra(int v){ int n=dist.length-1; if(v<1||v>n) return;

boolean[]s=new boolean[n+1]; for(int i=1;i<=n;i++) {

dist[i]=a[v][i]; s[i]=false;

if(dist[i]<0) prev[i]=0;

else prev[i]=v;

}

dist[v]=0; s[v]=true;

for(int i=1;iint temp=Integer.MAX_VALUE; int u=v;

for(int j=1;j<=n;j++)

if((!s[j])&&(dist[j]0)) {

u=j;

temp=dist[j]; }

s[u]=true;

for(int j=1;j<=n;j++) {

if((!s[j])&&(a[u][j]>0)) {

int newdist=dist[u]+a[u][j];

if(newdistdist[j]=newdist; prev[j]=u; } } } } }

三、 算法实现

1. 分支限界法解单源最短路径：

#include using namespace std; #define MAX 1000 class Graph {

public:

void ShorestPaths(int); void ShowDist(); Graph(); private:

int n; int *prev; int **c;

int *dist; };

class MinHeapNode {

friend Graph; public:

int getI() {return i;} void setI(int ii) {

i = ii; }

int getLength(){return length;} void setLength(int len) {

length = len; } private:

int i; int length; };

class MinHeap {

friend Graph; public:

MinHeap(); MinHeap(int);

void DeleteMin(MinHeapNode &); void Insert(MinHeapNode); bool OutOfBounds(); private:

int length;

MinHeapNode *node; };

Graph::Graph() {

int wi = 0; int yi = 0;

cout<<\"请输入图的节点个数：\"; cin>>n;

cout<<\"请输入图的邻接矩阵:\" << endl;

c = new int*[n+1]; dist = new int[n+1]; prev = new int[n+1]; for (wi = 0; wi <= n; wi++) {

c[wi] = new int[n+1]; if (wi == 0) {

for (yi = 0; yi <= n; yi++) {

c[wi][yi] = 0; } } else {

for (yi = 0; yi <= n; yi++) {

if (yi == 0) {

c[wi][yi] = 0; } else {

cin >> c[wi][yi]; } } } }

for (wi = 0; wi <= n; wi++) {

dist[wi] = MAX; prev[wi] = 0; } }

void Graph::ShowDist() {

cout << \"从源点到该节点的最短路径:\" << endl; int i = 0; int temp = 0;

for (i = 1; i <= n; i++) {

cout << \"dist[\" << i << \"] = \" << dist[i] << endl;

}

cout << \"从源点到终点的最短路径长度为:\" << dist[n] << endl; cout << \"其路径为：\"; temp = n;

while(temp != 0) {

if (prev[temp] == 0) {

cout << (temp); } else {

cout << (temp) << \" <- \"; }

temp = prev[temp]; }

cout << endl; }

void Graph::ShorestPaths(int v) {

MinHeap H(n); MinHeapNode E; E.i = v;

E.length = 0; dist[v] = 0; while (true) {

int j = 0;

for (j = 1; j <= n; j++) {

if ((c[E.i][j] != MAX) && (c[E.i][j] != 0)) {

if (E.length + c[E.i][j] < dist[j]) {

dist[j] = E.length + c[E.i][j]; prev[j] = E.i; if (j != n) {

MinHeapNode N; N.i = j;

N.length = dist[j];

H.Insert(N); } } else {

H.DeleteMin(E); } } }

if (H.OutOfBounds()) {

break; } } }

MinHeap::MinHeap() {

length = 10;

node = new MinHeapNode[length+1]; for (int i = 0; i <= length; i++) {

node[i].setI(0);

node[i].setLength(0); } }

MinHeap::MinHeap(int n) {

length = n;

node = new MinHeapNode[length+1]; for (int i = 0; i <= length; i++) {

node[i].setI(0);

node[i].setLength(0); } }

void MinHeap::DeleteMin(MinHeapNode &E) {

int i = 0; int j = 0;

j = E.getI(); node[j].setI(0);

node[j].setLength(0); int temp = MAX;

for (i = 1; i <= length; i++) {

if ((node[i].getLength() < temp) && (node[i].getLength() != 0)) {

E.setI(i);

E.setLength(node[i].getLength()); temp = node[i].getLength(); } } }

void MinHeap::Insert(MinHeapNode N) {

node[N.getI()].setI(N.getI());

node[N.getI()].setLength(N.getLength()); }

bool MinHeap::OutOfBounds() {

int i = 0;

bool flag = true;

for (i = 1; i <= length; i++) {

if (node[i].getI() != 0) {

flag = false; } }

return flag; }

int main() {

Graph graph;

graph.ShorestPaths(1); graph.ShowDist(); return 0; }

2. 贪新算法解单源最短路径：

#include #include using namespace std;

#define MAX 999

void getdata(int **c,int n) {

int i,j;

int begin,end,weight; for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if(i==j) c[i][j]=0; else c[i][j]=MAX; } }

for(i=1;i<=n;i++) { cout<<\"请输入起点-终点-权值：\"; cin>>begin; cin>>end>>weight; c[begin][end]=weight; } }

void Dijkstra(int n,int v ,int *dist,int *prev,int **c) {

bool s[MAX]; int i,j;

for (i=1;i<=n;i++) { dist[i]=c[v][i]; s[i]=false; if(dist[i]==MAX) prev[i]=0; else prev[i]=v; }

dist[v]=0;s[v]=true; for (i=1;i<=n;i++) { int temp=MAX; int u=v; for(j=1;j<=n;j++)

if((!s[j])&&(dist[j]void PrintPath(int *prev,int n,int begin,int end) {

int *path=new int [n+1]; int i,m=n; bool k=true; path[end]=end; for(i=end-1;i>1;i--) { path[i]=prev[path[i+1]]; m--; }

for (i=m;i<=end;i++) { cout<\"; }

cout<<\"\\b\\b\"<<\" \"<void main() {

int n,i; int v=1;

cout<<\"请输入顶点个数：\"; cin>>n;

int *dist=new int [n+1]; int *prev=new int [n+1]; int **c;

}

c=new int *[n+1]; for (i=0;i<=n;i++) { c[i]=new int [n+1]; }

getdata(c,n); int begin=1,end;

cout<<\"请输入所求单源路径的起点-终点：\"; cin>>begin>>end; v=begin;

Dijkstra(n,v,dist,prev,c); PrintPath(prev,n,begin,end);

四、 算法分析与改进

分支限界法解单源最短路径运行结果：

贪新算法解单源最短路径运行结果：

对当前优先搜索方向的判断标准为,有可能的最优解

而最优解可以用一个评估函数来做,即已经有的耗散度加上以后有可能的耗度 分支限界法算法就是把两个耗散度加在一起,作为当前状态的搜索搜索方向;

但是对以后的耗散度的评估是麻烦的, dijakstra算法就是把当前有的路的最短的作为,以后耗散度的评估.

分支限界算法就是只以以前的耗散度为评估函数