单源最短路径问题(分支限界法)

单元最短路径问题分支限界法【序】单元最短路径问题：分支限界法解析【引】在计算机科学中，图论问题一直是研究的热点之一。

而图的最短路径问题更是其中一个经典的困难问题。

在图中，单元最短路径问题就是要找到两个顶点之间的最短路径。

而在解决这个问题的过程中，我们可以借助分支限界法，来帮助我们找到最优的解。

本文将深度分析单元最短路径问题及分支限界法，以帮助读者全面理解并掌握这一问题解决方法。

【1】什么是单元最短路径问题？单元最短路径问题是图论中常见的一个问题，它要求在一个加权有向图或无向图中，找到两个给定顶点之间的最短路径。

该问题的解决方法包括了广度优先搜索、迪杰斯特拉算法等多种方法，其中分支限界法是一种常用的解决方法之一。

【2】分支限界法的基本思想分支限界法是一种通过搜索解空间来找到最优解的方法。

它通过将问题空间划分为一系列子问题，并不断搜索当前最优解的子空间，从而逐渐缩小问题空间，最终找到最优解。

【3】分支限界法在单元最短路径问题中的应用在解决单元最短路径问题时，分支限界法可以通过以下步骤来实施：1. 确定初始解和问题空间：选择一个顶点作为起始点，并设置一个初始解，例如将起始点的路径长度设置为0，其他顶点的路径长度设置为无穷大。

2. 扩展节点：从初始解开始，按照一定的扩展策略选择下一个节点进行扩展。

在单元最短路径问题中，我们可以选择将当前节点的邻接节点添加到解空间中。

3. 更新当前解：根据当前解空间中的节点，更新各节点的路径长度。

4. 剪枝：根据一定的条件，判断是否要剪去一些节点，从而缩小问题空间。

5. 重复上述步骤：不断迭代地重复上述步骤，直到找到最优解或者问题空间为空。

【4】为什么分支限界法适用于单元最短路径问题？分支限界法适用于单元最短路径问题的原因有以下几点：1. 分支限界法能够保证找到最优解。

通过不断地缩小问题空间，分支限界法能够找到最小的路径长度。

2. 分支限界法具有较高的搜索效率。

在每一步中，分支限界法都能够通过剪枝操作，排除一部分不可能达到最优解的节点，从而减少了搜索空间。

最短路径分支限界法最短路径问题是图论中的一个重要问题，涉及到在给定的图中找到两个顶点之间的最短路径。

在实际应用中，最短路径问题有着广泛的应用，比如导航系统中的路线规划、通信网络中的数据传输等。

为了解决最短路径问题，人们提出了许多算法，其中最短路径分支限界法是一种常用的方法之一。

最短路径分支限界法是一种穷举搜索算法，它通过不断地扩展当前路径，直到找到目标路径为止。

算法的核心思想是利用分支限界法来减少搜索空间，从而提高算法的效率。

具体而言，算法将搜索空间划分为若干个子空间，每次只对一个子空间进行搜索，从而避免了对整个搜索空间的穷举搜索，节省了时间和空间的开销。

最短路径分支限界法的基本步骤如下：1. 初始化：设置起始节点和目标节点，并初始化当前路径为空。

2. 扩展节点：从起始节点开始，按照某种策略选择一个节点进行扩展，将其加入当前路径。

3. 判断节点：判断当前路径是否到达目标节点，如果到达则得到一条候选路径，否则继续扩展。

4. 生成子节点：对当前节点生成所有可能的子节点，并计算子节点到起始节点的距离。

5. 选择子节点：从生成的子节点中选择一个作为下一个要扩展的节点，选择的策略可以根据具体情况进行调整。

6. 更新路径：将选中的子节点加入当前路径，并更新路径上的距离。

7. 剪枝操作：根据问题的特点，进行一定的剪枝操作，减少不必要的搜索。

8. 回溯操作：回溯到上一层节点，继续搜索其他子节点。

9. 终止条件：当搜索到达目标节点或者搜索空间为空时，算法终止。

最短路径分支限界法的关键在于选择合适的扩展策略和剪枝操作，以减少搜索空间。

常用的扩展策略包括贪心策略、A*算法等，而剪枝操作则可以根据具体问题的特点进行设计。

通过合理的策略选择和剪枝操作，最短路径分支限界法可以在较短的时间内找到最优解。

最短路径分支限界法虽然在解决最短路径问题中取得了一定的成果，但仍然存在一些局限性。

首先，算法的时间复杂度较高，特别是在处理大规模问题时，往往需要耗费大量的计算资源。

一、分支限界法：分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。

但在一般情况下，分支限界法与回溯法的求解目标不同。

回溯法的求解目标是找出T 中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。

回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。

分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。

为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

二、分支限界法的基本思想：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。

在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。

这个过程一直持续到找到所求的解或活结点表为空时为止。

三、选择下一扩展结点的不同方式：从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。

最常见的有以下两种方式：1、队列式(FIFO)分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。

分⽀限界法实验（单源最短路径）算法分析与设计实验报告第七次实验基本思想：附录：完整代码（分⽀限界法）Shorest_path.cpp//单源最短路径问题分⽀限界法求解#include#include#include#include"MinHeap2.h"using namespace std;templateclass Graph //定义图类{friend int main();public:void shortest_path(int); private:int n, //图的顶点数*prev; //前驱顶点数组Type **c, //图的邻接矩阵*dist; //最短距离数组};templateclass MinHeapNode //最⼩堆中的元素类型为MinHeapNode{friend Graph;public:operator int() const{return length;}private:int i; //顶点编号Type length; //当前路长};//单源最短路径问题的优先队列式分⽀限界法templatevoid Graph::shortest_path(int v){MinHeap> H(1000);//定义最⼩堆的容量为1000//定义源为初始扩展结点MinHeapNode E;//初始化源结点E.i=v;E.length=0;dist[v]=0;while(true)//搜索问题的解空间{for(int j=1;j<=n;j++)if((c[E.i][j]!=0)&&(E.length+c[E.i][j]{//顶点i到顶点j可达，且满⾜控制约束//顶点i和j之间有边，且此路径⼩于原先从源点i到j的路径长度dist[j]=E.length+c[E.i][j];//更新dist数组prev[j]=E.i;//加⼊活结点优先队列MinHeapNode N;N.i=j;N.length=dist[j];H.Insert(N);//插⼊到最⼩堆中}try{H.DeleteMin(E); // 取下⼀扩展结点}catch (int){break;}if(H.currentsize==0)//优先队列空{break;}}}int main(){int n=11;int prev[12]={0,0,0,0,0,0,0,0,0,0,0,0};//初始化前驱顶点数组intdist[12]={1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000};//初始化最短距离数组cout<<"单源图的邻接矩阵如下："<int **c=new int*[n+1];for(int i=1;i<=n;i++) //输⼊图的邻接矩阵{c[i]=new int[n+1];for(int j=1;j<=n;j++){cin>>c[i][j];}}int v=1; //源结点为1Graph G;G.n=n;G.c=c;G.dist=dist;G.prev=prev;clock_t start,end,over; //计算程序运⾏时间的算法start=clock();end=clock();over=end-start;start=clock();G.shortest_path(v);//调⽤图的最短路径查找算法//输出从源结点到⽬的结点的最短路径cout<<"从S到T的最短路长是："<for(int i=2;i<=n;i++)//输出每个结点的前驱结点{cout<<"prev("<}for(int i=2;i<=n;i++) //输出从源结点到其他结点的最短路径长度{cout<<"从1到"<}for(int i=1;i<=n;i++) //删除动态分配时的内存{delete[] c[i];}delete[] c;c=0;end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显⽰运⾏时间cout< system("pause");return 0;}MinHeap.h#includetemplateclass Graph;templateclass MinHeap //最⼩堆类{templatefriend class Graph;public:MinHeap(int maxheapsize=10); //构造函数，堆的⼤⼩是10~MinHeap(){delete[] heap;} //最⼩堆的析构函数int Size() const{return currentsize;} //Size()返回最⼩堆的个数T Max(){if(currentsize) return heap[1];} //第⼀个元素出堆MinHeap& Insert(const T& x); //最⼩堆的插⼊函数MinHeap& DeleteMin(T& x); //最⼩堆的删除函数void Initialize(T x[],int size,int ArraySize); //堆的初始化void Deactivate();void output(T a[],int n);private:int currentsize,maxsize;T *heap;};templatevoid MinHeap::output(T a[],int n) //输出函数，输出a[]数组的元素{for(int i=1;i<=n;i++)cout<cout<}templateMinHeap::MinHeap(int maxheapsize){maxsize=maxheapsize;heap=new T[maxsize+1]; //创建堆currentsize=0;}templateMinHeap& MinHeap::Insert(const T& x){if(currentsize==maxsize) //如果堆中的元素已经等于堆的最⼤⼤⼩return *this; //那么不能在加⼊元素进⼊堆中int i= ++currentsize;while(i!=1 && x{heap[i]=heap[i/2];i/=2;}heap[i]=x;return *this;}templateMinHeap& MinHeap::DeleteMin(T& x) //删除堆顶元素{if(currentsize==0){cout<<"Empty heap!"<return *this;}x=heap[1];T y=heap[currentsize--];int i=1,ci=2;while(ci<=currentsize){if(ciheap[ci+1])ci++;if(y<=heap[ci])break;heap[i]=heap[ci];i=ci;ci*=2;}heap[i]=y;return *this;}templatevoid MinHeap::Initialize(T x[],int size,int ArraySize) //堆的初始化{ delete[] heap;heap=x;currentsize=size;maxsize=ArraySize;for(int i=currentsize/2;i>=1;i--){T y=heap[i];int c=2*i;while(c<=currentsize){if(cheap[c+1])c++;if(y<=heap[c])break;heap[c/2]=heap[c];c*=2;}heap[c/2]=y;}}templatevoid MinHeap::Deactivate() {heap=0;}。

一道难题：如何用分支限界法求解单源最短路径单源最短路径问题是图论中的经典问题之一，不仅在实际生活中有广泛应用，而且对于算法设计和分析也有重要价值。

分支限界法是一种解决最短路径问题的强有力工具。

在这篇文章中，我们将详细介绍如何用分支限界法求解单源最短路径问题。

首先，我们需要了解单源最短路径问题的定义。

给定一个有向图和一个起点s，对于图中的每一个顶点v，找到从s到v的最短路径。

这里的最短路径是指从s到v经过的边权之和最小的路径。

接下来，我们可以按照以下步骤实现用分支限界法求解单源最短路径问题：1. 初始化距离数组dist[]，将s到其他所有点的距离设置为无穷大，将s到自己的距离设置为0。

2. 将起点s加入优先队列，队列中的元素按照距离dist[]从小到大排序。

3. 从优先队列中取出距离最小的顶点u，并遍历u的邻居节点v。

如果从s到v的距离可以通过从s到u再到v的路径更优，则更新dist[]数组和优先队列中的元素。

4. 重复步骤3，直到队列为空或者找到终点。

如果找到终点，则最优解就是dist[]数组中终点的值。

上述步骤中，第3步的优化是通过分支限界法实现的。

我们利用了贪心策略，并将目标函数设为从s到u的最短路径距离加上从u到v 的边权。

对于每一个节点u，我们只扩展目标函数值最小的那条边。

这样可以大幅度减少搜索空间，提高算法效率。

在实际应用中，分支限界法不仅可以求解单源最短路径问题，还可以应用于其他的组合优化问题中。

希望读者能够在掌握了基本理论和算法之后，加深对于分支限界法的理解，从而更好地解决实际问题。

算法分析与设计实验报告第七次实验姓名学号班级时间12.26上午地点工训楼309实验名称分支限界法实验(单源最短路径)实验目的1.掌握并运用分支限界法的基本思想2.运用分支限界法实现单源最短路径问题实验原理问题描述：在下图所给的有向图G中，每一边都有一个非负边权。

要求图G的从源顶点s 到目标顶点t之间的最短路径。

基本思想：下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。

其中，每一个结点旁边的数字表示该结点所对应的当前路长。

为了加速搜索的进程，应采用有效地方式选择活结点进行扩展。

按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。

catch (int){break;}if(H.currentsize==0) //优先队列空{break;}}}上述有向图的结果：测试结果附录：完整代码（分支限界法）Shorest_path.cpp//单源最短路径问题分支限界法求解#include<iostream>#include<time.h>#include<iomanip>#include"MinHeap2.h"using namespace std;template<class Type>class Graph //定义图类{friend int main();public:void shortest_path(int); private:int n, //图的顶点数*prev; //前驱顶点数组Type **c, //图的邻接矩阵*dist; //最短距离数组};template<class Type>class MinHeapNode //最小堆中的元素类型为MinHeapNode{friend Graph<Type>;public:operator int() const{return length;}private:int i; //顶点编号Type length; //当前路长};//单源最短路径问题的优先队列式分支限界法template<class Type>void Graph<Type>::shortest_path(int v){MinHeap<MinHeapNode<Type>> H(1000);//定义最小堆的容量为1000//定义源为初始扩展结点MinHeapNode<Type> E;//初始化源结点E.i=v;E.length=0;dist[v]=0;while(true)//搜索问题的解空间{for(int j=1;j<=n;j++)if((c[E.i][j]!=0)&&(E.length+c[E.i][j]<dist[j])){//顶点i到顶点j可达，且满足控制约束//顶点i和j之间有边，且此路径小于原先从源点i到j的路径长度dist[j]=E.length+c[E.i][j];//更新dist数组prev[j]=E.i;//加入活结点优先队列MinHeapNode<Type> N;N.i=j;N.length=dist[j];H.Insert(N);//插入到最小堆中}try{H.DeleteMin(E); // 取下一扩展结点}catch (int){break;}if(H.currentsize==0)//优先队列空{break;}}}int main(){int n=11;int prev[12]={0,0,0,0,0,0,0,0,0,0,0,0};//初始化前驱顶点数组intdist[12]={1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000 };//初始化最短距离数组cout<<"单源图的邻接矩阵如下："<<endl;int **c=new int*[n+1];for(int i=1;i<=n;i++) //输入图的邻接矩阵{c[i]=new int[n+1];for(int j=1;j<=n;j++){cin>>c[i][j];}}int v=1; //源结点为1Graph<int> G;G.n=n;G.c=c;G.dist=dist;G.prev=prev;clock_t start,end,over; //计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();G.shortest_path(v);//调用图的最短路径查找算法//输出从源结点到目的结点的最短路径cout<<"从S到T的最短路长是："<<dist[11]<<endl;for(int i=2;i<=n;i++)//输出每个结点的前驱结点{cout<<"prev("<<i<<")="<<prev[i]<<" "<<endl;}for(int i=2;i<=n;i++) //输出从源结点到其他结点的最短路径长度{cout<<"从1到"<<i<<"的最短路长是："<<dist[i]<<endl;}for(int i=1;i<=n;i++) //删除动态分配时的内存{delete[] c[i];}delete[] c;c=0;end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显示运行时间cout<<endl;system("pause");return 0;}MinHeap.h#include<iostream>template<class Type>class Graph;template<class T>class MinHeap //最小堆类{template<class Type>friend class Graph;public:MinHeap(int maxheapsize=10); //构造函数，堆的大小是10~MinHeap(){delete[] heap;} //最小堆的析构函数int Size() const{return currentsize;} //Size()返回最小堆的个数T Max(){if(currentsize) return heap[1];} //第一个元素出堆MinHeap<T>& Insert(const T& x); //最小堆的插入函数MinHeap<T>& DeleteMin(T& x); //最小堆的删除函数void Initialize(T x[],int size,int ArraySize); //堆的初始化void Deactivate();void output(T a[],int n);private:int currentsize,maxsize;T *heap;};template<class T>void MinHeap<T>::output(T a[],int n) //输出函数，输出a[]数组的元素{for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;}template<class T>MinHeap<T>::MinHeap(int maxheapsize){maxsize=maxheapsize;heap=new T[maxsize+1]; //创建堆currentsize=0;}template<class T>MinHeap<T>& MinHeap<T>::Insert(const T& x){if(currentsize==maxsize) //如果堆中的元素已经等于堆的最大大小return *this; //那么不能在加入元素进入堆中int i= ++currentsize;while(i!=1 && x<heap[i/2]){heap[i]=heap[i/2];i/=2;}heap[i]=x;return *this;}template<class T>MinHeap<T>& MinHeap<T>::DeleteMin(T& x) //删除堆顶元素{if(currentsize==0){cout<<"Empty heap!"<<endl;return *this;}x=heap[1];T y=heap[currentsize--];int i=1,ci=2;while(ci<=currentsize){if(ci<currentsize && heap[ci]>heap[ci+1])ci++;if(y<=heap[ci])break;heap[i]=heap[ci];i=ci;ci*=2;}heap[i]=y;return *this;}template<class T>void MinHeap<T>::Initialize(T x[],int size,int ArraySize) //堆的初始化{delete[] heap;heap=x;currentsize=size;maxsize=ArraySize;for(int i=currentsize/2;i>=1;i--){T y=heap[i];int c=2*i;while(c<=currentsize){if(c<currentsize && heap[c]>heap[c+1])c++;if(y<=heap[c])break;heap[c/2]=heap[c];c*=2;}heap[c/2]=y;}}template<class T>void MinHeap<T>::Deactivate(){heap=0; }。

分支限界法求单源最短路径分支限界法是一种求解最优化问题的算法，在图论中，可以用来求解单源最短路径。

本文将介绍分支限界法的基本原理和步骤，并通过一个具体的示例来说明其应用。

一、分支限界法简介分支限界法是一种穷举搜索算法，通过不断地将问题空间划分成更小的子问题，以寻找最优解。

它与传统的深度优先搜索算法相似，但在搜索过程中，通过引入上界（界限）来限制搜索范围，从而有效地剪枝和加速搜索过程。

分支限界法求解单源最短路径问题的基本思想是，首先将源点标记为已访问，然后以源点为根节点构建一棵搜索树，树中的每个节点表示当前访问的顶点，并记录到达该顶点的路径和权值。

通过遍历搜索树，逐步更新最短路径以及当前最优权值，从而找到最短路径。

二、分支限界法的步骤1. 创建搜索树：- 将源点标记为已访问，并将其作为根节点。

- 根据源点与其他顶点之间的边权值构建搜索树的第一层。

- 初始化当前最优路径和权值。

2. 遍历搜索树：- 从当前层中选择一个未访问的顶点作为扩展节点。

- 计算到达该扩展节点的路径和权值，并更新当前最优路径和权值。

- 根据已有的路径和权值，计算该扩展节点的上界，并与当前最优权值进行比较。

若上界小于当前最优权值，则进行剪枝操作，否则继续搜索。

- 将该扩展节点的子节点添加到搜索树中。

3. 更新最短路径：- 当搜索树的所有叶子节点都已遍历时，找到最短路径以及相应的权值。

三、示例分析为了更好地理解分支限界法的运行过程，我们将通过一个具体的示例来进行分析。

假设有一个有向带权图，其中包含5个顶点和6条边。

首先，我们需要构建初始搜索树，将源点A作为根节点。

根据源点与其他顶点之间的边权值，我们可以得到搜索树的第一层B(2)、C(3)、D(4)、E(5)。

接下来，我们从第一层选择一个未访问的顶点作为扩展节点。

假设选择节点B进行扩展。

此时，我们计算到达节点B的路径和权值，并更新当前最优路径和权值。

对于节点B，到达它的路径为AB，权值为2。

贪⼼算法和分⽀限界法解决单源最短路径单源最短路径计科1班朱润华 2012040732⽅法1：贪⼼算法⼀、贪⼼算法解决单源最短路径问题描述：单源最短路径描述：给定带权有向图G=(V,E),其中每条边的权是⾮负实数。

另外，还给定V中的⼀个顶点，称之为源(origin)。

现在要计算从源到其他各顶点的最短路径的长度。

这⾥的路径长度指的是到达路径各边权值之和。

Dijkstra算法是解决单源最短路径问题的贪⼼算法。

Dijkstra算法的基本思想是：设置顶点集合S并不断地做贪⼼选择来扩充集合。

⼀个顶点属于集合S当且仅当从源点到该顶点的最短路径长度已知。

贪⼼扩充就是不断在集合S中添加新的元素（顶点）。

初始时，集合S中仅含有源(origin)⼀个元素。

设curr是G的某个顶点，把从源到curr 且中间只经过集合S中顶点的路称之为从源到顶点curr的特殊路径，并且使⽤数组distance记录当前每个顶点所对应的最短路径的长度。

Dijkstra算法每次从图G中的(V-S)的集合中选取具有最短路径的顶点curr，并将curr加⼊到集合S中，同时对数组distance 进⾏必要的修改。

⼀旦S包含了所有的V中元素，distance数组就记录了从源(origin)到其他顶点的最短路径长度。

⼆、贪⼼算法思想步骤：Dijkstra算法可描述如下，其中输⼊带权有向图是G=(V,E)，V={1,2,…，n}，顶点v 是源。

c是⼀个⼆维数组，c[i][j]表⽰边(i,j)的权。

当(i,j)不属于E时，c[i][j]是⼀个⼤数。

dist[i]表⽰当前从源到顶点i的最短特殊路径长度。

在Dijkstra算法中做贪⼼选择时，实际上是考虑当S添加u之后，可能出现⼀条到顶点的新的特殊路，如果这条新特殊路是先经过⽼的S到达顶点u,然后从u经过⼀条边直接到达顶点i，则这种路的最短长度是dist[u]+c[u][i]。

如果dist[u]+c[u][i]1、⽤带权的邻接矩阵c来表⽰带权有向图, c[i][j]表⽰弧上的权值。

实验报告13课程数据结构与算法实验名称分支限界法第页班级11计本学号105032011130 姓名风律澈实验日期：2013年6月3日报告退发(订正、重做)一、实验目的掌握分支限界法的原理和应用。

二、实验环境1、微型计算机一台2、WINDOWS操作系统，Java SDK，Eclipse开发环境三、实验内容必做题：1、编写程序，采用分支限界法求解单元最短路径问题。

2、编写程序，采用分支限界发法实现0-1背包问题。

四、实验步骤和结果(附上代码和程序运行结果截图)1,单源最短路径import java.util.PriorityQueue;public class BBShortest {/*** @param args*/static class HeapNode implements Comparable{int i;//顶点编号int length;HeapNode(int ii,int ll){//构造函数，类种类i=ii;length=ll;}@Overridepublic int compareTo(Object o) {//为优先队列设置优先级判定方法// TODO Auto-generated method stubint x=((HeapNode)o).length;if(length<x) return -1;if(length==x) return 0;return 1;}}static int [][]a;//图的邻接矩阵public static void shortest(int v,int []dist,int []p){int n=p.length-1;PriorityQueue<HeapNode> heap=new PriorityQueue<HeapNode>();//生成一个优先队列存放活节点HeapNode enode=new HeapNode(v,0);for(int j=1;j<=n;j++)dist[j]=Integer.MAX_VALUE;//默认每个顶点初始都是最长距离dist[v]=0;while(true){for(int j=1;j<=n;j++)if(a[enode.i][j]<Integer.MAX_VALUE&&enode.length+a[enode.i][j]<dist[ j]){//约束条件，有连通&&可能存在更有解dist[j]=enode.length+a[enode.i][j];//更改点j的最优路径p[j]=enode.i;//把这个成为解的编号写入存放结果的数组p中HeapNode node=new HeapNode(j,dist[j]);heap.add(node);//加入活结点优先队列}if(heap.isEmpty())break;elseenode=heap.poll();}}public static void main(String[] args) {// TODO Auto-generated method stubint M=Integer.MAX_VALUE;a=new int[][]{{M,M,M,M,M,M},{M,0,10,M,30,100},{M,M,0,50,M,M},{M,M,M,0,M,10},{M,M,M,20,0,60},{M,M,M,M,M,0}};int v = 1;int dist[]=new int[a.length];int p[]=new int[a.length];shortest(v,dist,p);for(int i=1;i<dist.length;i++){System.out.print(dist[i]+" ");}}}--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 2，0-1背包问题package bag01b;import java.util.ArrayList;public class bag01do {/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stubArrayList<object> objects=new ArrayList<>();objects.add(new object(3,9));objects.add(new object(5,10));objects.add(new object(2,7));objects.add(new object(1,4));bag b=new bag(7,objects);b.findmaxvalue();b.show();}}----------------------------------------------------------------------- package bag01b;import java.util.ArrayList;import java.util.Collections;import java.util.PriorityQueue;public class bag {private int bagv;private ArrayList<object> objects;private int maxvalue;private ArrayList<object> result_objects;public bag(int v,ArrayList<object> o){super();this.bagv=v;this.objects=o;this.maxvalue=0;this.result_objects=null;Collections.sort(objects);}public void show(){System.out.println("maxvalue :"+ this.maxvalue);System.out.println("the object when maxvalue:"+this.result_objects);}public void findmaxvalue(){PriorityQueue<Node> enode=new PriorityQueue<>();Node node=new Node(0,null,bagv,this.objects);enode.offer(node);while(true){if(enode.isEmpty())break;node=enode.poll();if(node.isend()){this.maxvalue=node.get_bag_value();this.result_objects=newArrayList<>(node.get_in_bag_object());return;}int i=node.get_node_in();object iobject=this.objects.get(i);if(node.get_bag_weight()+iobject.getweight()<=this.bagv){ ArrayList<object> newnodeinbag=newArrayList<object>(node.get_in_bag_object());newnodeinbag.add(iobject);int newnodebagv=node.get_bag_leftv()-iobject.getweight();Node newnode=new Node(i+1,newnodeinbag,newnodebagv,this.objects);enode.add(newnode);if(newnode.get_bag_value()>this.maxvalue){this.maxvalue=newnode.get_bag_value();this.result_objects=newArrayList<>(newnode.get_in_bag_object());}}Node newnode=new Node(i+1,node.get_in_bag_object(),node.get_bag_leftv(),this.objects);if(newnode.get_bag_prio()>this.maxvalue)enode.add(newnode);}}}----------------------------------------------------------------------- package bag01b;import java.util.ArrayList;public class Node implements Comparable<Node>{private int node_in;private ArrayList<object> inbag_object;private ArrayList<object> outbag_object;private int leftv;private int prio;public Node(int i,ArrayList<object> in,int l,ArrayList<object> out){ super();this.node_in=i;if(in==null)in=new ArrayList<>();this.inbag_object=in;this.leftv=l;this.outbag_object=out;this.prio=this.find_prio();}private int find_prio() {// TODO Auto-generated method stubint bag_left=this.leftv;int p=this.get_bag_value();int i=this.node_in;object iobject=null;while(true){if(i>=this.inbag_object.size())break;iobject=this.inbag_object.get(i);if(iobject.getweight()>bag_left)break;bag_left-=iobject.getweight();p+=iobject.getvalue();i++;}if(i<=this.inbag_object.size()-1)p+=iobject.getvw()*bag_left;return p;}public int get_bag_weight(){int w=0;for(object o:this.inbag_object){w+=o.getweight();}return w;}public int get_bag_value(){int w=0;for(object o:this.inbag_object){w+=o.getvalue();}return w;}@Overridepublic int compareTo(Node o) {// TODO Auto-generated method stubif(this.prio>o.prio) return -1;if(this.prio<o.prio) return 1;return 0;}public boolean isend(){if(this.node_in==this.outbag_object.size()) return true;elsereturn false;}public ArrayList<object> get_in_bag_object(){return this.inbag_object;}public int get_node_in(){return this.node_in;}public int get_bag_leftv(){return this.leftv;}public int get_bag_prio(){return this.prio;}public String toString(){return"node in"+this.node_in+"node prio"+this.prio;}}----------------------------------------------------------------------- package bag01b;public class object implements Comparable<object>{private static int ids=1;private int id;private int weihgt;private int value;public object(int w,int v){super();this.weihgt=w;this.value=v;this.id=ids++;}public int getid(){return this.id;}public int getweight(){return this.weihgt;}public int getvalue(){return this.value;}public float getvw(){return (float)this.value/this.weihgt;}@Overridepublic int compareTo(object o) {// TODO Auto-generated method stubif(this.getvw()>o.getvw()) return -1;if(this.getvw()<o.getvw()) return 1;return 0;}public String toString(){return"object "+this.id+" ";}}-----------------------------------------------------------------------五、实验总结(本次实验完成的情况，心得体会)。

0033算法笔记分支限界法分支限界法与单源最短路径问题 0033算法笔记-分支限界法分支限界法与单源最短路径问题1、分支限界法(1)叙述：使用广度优先产生状态空间一棵的结点，并采用剪枝函数的方法称作分枝限界法。

所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即为：儿子结点）。

所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减去搜寻一棵的某些分支，从而提升搜寻效率。

(2)原理：按照广度优先的原则，一个活结点一旦成为扩展结点（e-结点）r后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。

然后，从活结点表中取出一个结点作为当前扩展结点。

重复上述结点扩展过程，直至找到问题的解或判定无解为止。

(3)分支限界法与回溯法1)解目标：追溯法的解目标就是找到求解空间树中满足用户约束条件的所有求解，而分支限界法的解目标则就是找到满足用户约束条件的一个求解，或是在八十足约束条件的解中找出在某种意义下的最优解。

2)搜寻方式的相同：追溯法以深度优先的方式搜寻求解空间一棵，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

(4)常见的分支限界法1)fifo分支限界法(队列式分支限界法)基本思想：按照队列先进先出(fifo)原则选取下一个活结点为扩展结点。

搜寻策略：一已经开始，根结点就是唯一的活结点，根结点入队。

从活结点队中抽出根结点后，做为当前拓展结点。

对当前拓展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足用户约束函数的儿子重新加入活结点队列中。

再从活结点表抽出队首结点（队中最先进去的结点）为当前拓展结点，……，直至找出一个求解或活结点队列入空年才。

2)lc(leastcost)分支限界法(优先队列式分支限界法)基本思想：为了加速搜索的进程，应采用有效地方式选择活结点进行扩展。

按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。