分支定界的基本思想：用来解决寻路问题（最短路径） 广度寻路算法 A星寻路算法
常用广度优先或者以最小耗费(最大效益)优先的方式搜索问题的解空间树
在分支定界算法思想中，每一个活节点（坐标点）只有一次机会成为扩展节点。
一旦成为扩展节点，就一次性产生其所有孩子节点。
在这些孩子节点中，导致不可行解或者非最优解的孩子节点被舍弃（剪枝），其余孩子节点被加入活节点表中（存放，记录，保存）
此后，从活节点表（ buff ）中取下一节点成为当前扩展节点。并重复上述节点扩展过程。
这个过程一直到找到需要的解（找到终点）或者活节点表（ buff 为空：每一个点都找过了，都不是终点）为空。
分支定界法常用的两个数据结构：
1
.
队列式分支定界法
按照队列原则选取下一个节点为扩展节点（（爬虫）广度优先）
2
.
优先队列式分支定界法
按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点（A星寻路）
有向图
引入权重的概念：每条边都是有权重的，用
紫色
表示
可以用邻接表，矩阵法存储图
有一个图结构
求 s 到 t 的最佳(短)路径
广度方式求单源最短路径问题
和寻路算法解决的是同样的问题：最佳路径，但是代码不大一样，中间遇到的问题也有一定的区别
s ~ s：0
s ~ t：max
s ~ s[0，0] s ~ a[0，1] s ~ b[0，2]
寻路过程中的每一层每一个点的路径都需要求出来，直到最后一层，中间没有用的不保留，最终得到一条最佳路径
利用有向网图结构，怎么解空间？怎么剪枝？怎么一步步存储中间的过程？
路径长度一致如何解决
遍历同一层有先后顺序，先遍历 a， b，还是 c，不能同时遍历，最先遍历的最先出来，其他的就被剪枝，如果要保留路径长度一致的，就需要附加其他步骤
用矩阵法描述图结构
#include <iostream>
#include <vector>
#include <limits>//numeric_limits
#include <queue>
using namespace std;
//节点类
class Node {
public://属性 一般应该是 private 或者 protected
int index; //序号 顶点中的值
int weight; //权重
public://功能
//构造函数
Node(int index = 0, int weight = 0) :index(index), weight(weight) {}
//拷贝构造 通过一个对象创建另一个对象
Node(const Node& object) :index(object.index), weight(object.weight) {}
//重载小于运算符 为了比较 剪枝
friend bool operator<(const Node& one, const Node& two) {
return (one.weight > two.weight);//找最短路径-> 最小权值
}
};
//路径类 节点类是边 路径类其实是很多节点(边)相加
class Path {
public://属性 一般应该是 private 或者 protected
int index; //序号
int weight; //权重
public://功能 c++标准整型最大值 给s~t的最大值赋值 权重是最大值-> 表示开始的时候什么都没有
Path() :index(0), weight(numeric_limits<int>::max()) {}
};
//求最短路径
class shortTestPath {
public://属性
vector<vector<int>> graph; //图结构 二维数组描述整条路径
int nodeCount; //节点数
const int edge; //入口-> 不连通的标记
const int end; //出口
vector<int> pathIndex; //存储最短路径的容器
int shortPath; //最短路径的值 3 + 2 + 1 + 2 == 8
public://功能
//构造函数
shortTestPath(const vector<vector<int>>& object, int end) :edge(-1), end(end),
nodeCount(object.size()), graph(object) {}//传入二维数组给graph赋值 传入终点 起点从-1开始 传入的节点数size
//打印路径
void printPath() {
cout << "最短路径值:" << shortPath << endl;
cout << "路径:";
//反向打印-> 用现成的迭代器做打印
copy(pathIndex.rbegin(), pathIndex.rend(),//需要提供一个间隔的符号-> 用空格隔开
ostream_iterator<int>(cout, " ")); //vector只能加在后面push_back-> 用反向迭代器
cout << endl;
}
void getShortTestPath() {
vector<Path> myPath(nodeCount);//初始化路径容器大小
priority_queue<Node, vector<Node>> minHeap;//准备一个优先队列（小顶堆）
minHeap.push(Node(0, 0));//入口入堆
while (1) {
Node top = minHeap.top();//获取堆顶
minHeap.pop(); //出堆
//判断是不是等于终点 如果是终点结束循环-> 寻路结束
if (top.index == end) break;
//没有结束-> 剪枝过程 只保留需要的部分-> 访问的节点和另一个节点是连通的时候 并且路径小于其他路
for (int i = 0; i < nodeCount; i++) {//nodeCount为节点的数量 从第一个到最后一个相加
if (graph[top.index][i] != edge &&//不等于不连通状态->连通的状态
//原来的权值+将要去的地方的权值<原来的路径
top.weight + graph[top.index][i] < myPath[i].weight) {
//构建一个新的节点入堆保留 当前权值比原来权值短-> 把新的权值放到堆中
minHeap.push(Node(i, top.weight + graph[top.index][i]));
//改变原来路径的序号-> 已经走到新的位置
myPath[i].index = top.index;
//更新权值 加上最新顶点的权值
myPath[i].weight = top.weight + graph[top.index][i];
}
}
//最终堆空了,还没找到终点-> 需要结束
if (minHeap.empty()) break;
}//end of while (1)
//求最短路径的值
shortPath = myPath[end].weight;
//求路径-> 从终点开始一路往前打印
int index = end;
//尾插法把所有序号都丢进去
pathIndex.push_back(index);
while (1) {
index = myPath[index].index;//一步步往前打印
pathIndex.push_back(index);
if (0 == index) break;//如果等于第一个就结束
}
}
};
int main() {
//准备图结构
const int size = 11;//顶点个数用于准备图结构-> vector一个个push过于麻烦
vector<vector<int>> graph(size);//二维数组初始化
for (int i = 0; i < size; i++) {
graph[i].resize(size);//重置大小 开空间
}
//赋值 二维数组的每一个位置初始化为-1-> 表示不连通的状态
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
graph[i][j] = -1;
}
}
//按照图的数据一个个赋值
graph[0][1] = 2;
graph[0][2] = 3;
graph[0][3] = 4;
graph[1][2] = 3;
graph[1][4] = 7;
graph[1][5] = 2;
graph[2][6] = 2;
graph[2][5] = 9;
graph[3][6] = 2;
graph[4][7] = 3;
graph[4][8] = 3;
graph[5][6] = 1;
graph[5][8] = 3;
graph[6][9] = 1;
graph[6][8] = 5;
graph[7][10] = 3;
graph[8][10] = 2;
graph[9][8] = 2;
graph[9][10] = 2;
//创建shortTestPath对象 终点是10
shortTestPath sPath(graph, 10);
sPath.getShortTestPath();//求出最短路径
sPath.printPath();//打印
while (1);
return 0;
}
/*输出*/
最短路径值:8
路径:0 2 6 9 10