基于分⽀限界法的旅⾏商问题（TSP）⼀
旅⾏推销员问题（英语：Travelling salesman problem, TSP）是这样⼀个问题：给定⼀系列城市和每对城市之间的距离，求解访问每⼀座
城市⼀次并回到起始城市的最短回路。它是组合优化中的⼀个NP困难问题，在运筹学和理论计算机科学中⾮常重要。
分⽀限界法在上⼀篇Blog中我有简单说明，并给出了 ，这篇⽂章⾥介绍⼀下基于分⽀限界法的TSP算法。
对于TSP，我们需要利⽤上界和下界来对BFS进⾏剪枝，通过不断更新上界和下界，尽可能的排除不符合需求的child，以实现剪枝。最终，
当上限和下限等同时，我们可以获得最优的BFS解，以解决TSP问题。
在第⼀篇中，我们⽤dfs获取上界，⽤每⾏矩阵最⼩值来获取下界。
代码如下，下⾯代码中，我采⽤贪⼼法（使⽤DFS暴⼒搜索到⼀个结果）来获取最初的上界，通过累加每⾏旅⾏商矩阵中的最⼩值来获取⼀
个下界。
//分⽀限界法
#include
#include
#include
#include
const int INF = 100000;
const int MAX_N = 22;
using namespace std;
//n*n的⼀个矩阵
int n;
int cost[MAX_N][MAX_N];//最少3个点，最多MAX_N个点
struct Node
{
bool visited[MAX_N];//标记哪些点⾛了
int s;//第⼀个点
int s_p;//第⼀个点的邻接点
int e;//最后⼀个点
int e_p;//最后⼀个点的邻接点
int k;//⾛过的点数
int sumv;//经过路径的距离
int lb;//⽬标函数的值（⽬标结果）
bool operator <(const Node &p)const
{
return p.lb < lb;//⽬标函数值⼩的先出队列
}
};
priority_queue pq;//创建⼀个优先队列
算法分析与设计实验报告
分支限界法实现单源最短路径
班级： 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的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。
一道难题：如何用分支限界法求解单源最短路径
单源最短路径问题是图论中的经典问题之一，不仅在实际生活中有广泛应用，而且对于算法设计和分析也有重要价值。分支限界法是一种解决最短路径问题的强有力工具。在这篇文章中，我们将详细介绍如何用分支限界法求解单源最短路径问题。
首先，我们需要了解单源最短路径问题的定义。给定一个有向图和一个起点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，我们只扩展目标函数值最小的那条边。这样可以大幅度减少搜索空间，提高算法效率。
在实际应用中，分支限界法不仅可以求解单源最短路径问题，还可以应用于其他的组合优化问题中。希望读者能够在掌握了基本理论和算法之后，加深对于分支限界法的理解，从而更好地解决实际问题。
1、分支限界法
(1)描述：采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。
所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。
所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率。
(2)原理：按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。然后，从活结点表中取出一个结点作为当前扩展结点。重复上述结点扩展过程，直至找到问题的解或判定无解为止。
(3)分支限界法与回溯法
1)求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
2)搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
(4)常见的分支限界法 1)FIFO分支限界法(队列式分支限界法)
基本思想：按照队列先进先出(FIFO)原则选取下一个活结点为扩展结点。
搜索策略：一开始，根结点是唯一的活结点，根结点入队。从活结点队中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。
2)LC(least cost)分支限界法(优先队列式分支限界法)
基本思想：为了加速搜索的进程，应采用有效地方式选择活结点进行扩展。按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。
