【基础算法】(09)五大常用算法之五：分支限界法

2024-06-06 17:58
文章标签 算法 基础 五大 常用 之五 分支 09 限界

本文主要是介绍【基础算法】(09)五大常用算法之五：分支限界法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【基础算法】(09)五大常用算法之五：分支限界法

Auther: Thomas Shen
E-mail: Thomas.shen3904@qq.com
Date: 2017/10/27
All Copyrights reserved !

      • 基础算法09五大常用算法之五分支限界法
        • 简述
        • 算法原理
          • 1 分支限界法与回溯法
          • 2 分支限界法思想
          • 3 常见的两种分支限界法
        • 案例一单源最短路径问题
        • 案例二TSP问题中使用分支限界法
        • References

1. 简述：

本系列介绍了五大常用算法，其中本文是第五篇，介绍了 ‘分支限界法’ 的细节内容。

2. 算法原理：

分支限界法（branch and bound method）按广度优先策略搜索问题的解空间树，在搜索过程中，对待处理的节点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值（极大或极小）的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。分支限界法适合求解最优化问题。

2.1 分支限界法与回溯法：

  1. 求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

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

2.2 分支限界法思想：

分支限界法首先要确定一个合理的限界函数（bound funciton），并根据限界函数确定目标函数的界[down ,up]，按照广度优先策略搜索问题的解空间树，在分直结点上依次扩展该结点的孩子结点，分别估算孩子结点的目标函数可能值，如果某孩子结点的目标函数可能超出目标函数的界，则将其丢弃；否则将其加入待处理结点表（简称PT表），依次从表PT中选取使目标函数取得极值的结点成为当前扩展结点，重复上述过程，直到得到最优解。

2.3 常见的两种分支限界法：
  1. 队列式(FIFO)分支限界法
    按照队列先进先出（FIFO）原则选取下一个结点为扩展结点。
  2. 优先队列式分支限界法
    按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。
3. 案例一：单源最短路径问题

http://www.cnblogs.com/chinazhangjie/archive/2010/11/01/1866136.html

1. 问题描述：
在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。
这里写图片描述

下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。

这里写图片描述

找到一条路径：

这里写图片描述

目前的最短路径是8，一旦发现某个结点的下界不小于这个最短路进，则剪枝：

这里写图片描述

同一个结点选择最短的到达路径：

这里写图片描述
这里写图片描述

2. 剪枝策略:

在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。

在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。

3. 算法思想:

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

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

4. 实现:

/* 主题：单源最短路径问题
* 作者：chinazhangjie
* 邮箱：chinajiezhang@gmail.com
* 开发语言：C++
* 开发环境：Mircosoft Virsual Studio 2008
* 时间: 2010.11.01
*/#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;struct node_info
{
public:node_info (int i,int w) : index (i), weight (w) {}node_info () : index(0),weight(0) {}node_info (const node_info & ni) : index (ni.index), weight (ni.weight) {}friend bool operator < (const node_info& lth,const node_info& rth) {return lth.weight > rth.weight ; // 为了实现从小到大的顺序}public:int index; // 结点位置int weight; // 权值
};struct path_info 
{
public:path_info (): front_index(0), weight (numeric_limits<int>::max()) {}public:int front_index;int weight;
};// single source shortest paths
class ss_shortest_paths
{public:ss_shortest_paths (const vector<vector<int> >& g,int end_location) :no_edge (-1), end_node (end_location), node_count (g.size()) , graph (g) {}// 打印最短路径void print_spaths () const {cout << "min weight : " << shortest_path << endl;cout << "path: " ;copy (s_path_index.rbegin(),s_path_index.rend(),ostream_iterator<int> (cout, " "));cout << endl;}// 求最短路径void shortest_paths () {vector<path_info> path(node_count);priority_queue<node_info,vector<node_info> > min_heap;min_heap.push (node_info(0,0));    // 将起始结点入队while (true) {node_info top = min_heap.top ();    // 取出最大值min_heap.pop ();// 已到达目的结点if (top.index == end_node) {break ;}// 未到达则遍历for (int i = 0; i < node_count; ++ i) {// 顶点top.index和i间有边，且此路径长小于原先从原点到i的路径长 if (graph[top.index][i] != no_edge && (top.weight + graph[top.index][i]) < path[i].weight) {min_heap.push (node_info (i,top.weight + graph[top.index][i]));path[i].front_index = top.index;path[i].weight = top.weight + graph[top.index][i];}}if (min_heap.empty()) {break ;}}shortest_path = path[end_node].weight;int index = end_node;s_path_index.push_back(index) ;while (true) {index = path[index].front_index ;s_path_index.push_back(index);if (index == 0) {break;}}}private:vector<vector<int> >    graph ;            // 图的数组表示int                        node_count;        // 结点个数const int                no_edge;        // 无通路const int                end_node;        // 目的结点vector<int>                s_path_index;    // 最短路径int                        shortest_path;    // 最短路径
};int main()
{const int size = 11; vector<vector<int> > graph (size);for (int i = 0;i < size; ++ i) {graph[i].resize (size);}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][5] = 2;graph[1][4] = 7;graph[2][5] = 9;graph[2][6] = 2;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;ss_shortest_paths ssp (graph, 10);ssp.shortest_paths ();ssp.print_spaths ();return 0;
}

测试数据（图）:
这里写图片描述

测试结果
min weight : 8
path: 0 2 6 9 10

4. 案例二：TSP问题中使用分支限界法

http://blog.csdn.net/lovesummerforever/article/details/18622127

TSP问题是指旅行家要旅行n个城市，要求各个城市经理且仅经理依次然后回到出发城市，并要求所走的路程最短。我们以下图的无限图为例，采用分支限界法解决这个问题。

这里写图片描述

该无向图对应的代价矩阵如下所示：
这里写图片描述

代价矩阵是1到1,1到2,1到3,1到4,1到5距离写在第一行，第二行为2到1,2到2,2到3,2到4，、、、依次

  1. 找到目标函数的界。上界为，采用贪心算法求得上界，从节点1开始到节点3—>5—>4—>2—>1,路径，即为图中红色圈的路径，其路径长度为C=1+2+3+7+3=16。
    下界为矩阵中每行中两个最小的相加，所有的行加起来的和的一半。( (3+1)+(3+6)+(1+2)+(3+4)+(2 +3) )/2=14
    所以求得界为[14,16]。

  2. 计算每个节点的限界值。
    计算目标函数（限界函数），lb分为三部分，第一部分是经过路径的长度相加的2倍，加上第二部分离着路径首尾节点最近的距离相加（不在已知路径上的），加上第三部分除了路径上节点，矩阵中两个最短的距离相加，最后这三部分和相加，得到的结果除以2便是每个节点的限界值。

  3. 画出PT图。如下所示。

这里写图片描述

根据上述所述得到最优解1–>3–>5–>4–>2–>1

//分支限界法  
#include<iostream>  
#include<algorithm>  
#include<cstdio>  
#include<queue>  
#define INF 100000  
using namespace std;  
/*  n*n的一个矩阵  */  
int n;  
int mp[22][22];//最少3个点，最多15个点  
/*输入距离矩阵*/  
void in()  
{  scanf("%d",&n);  for(int i=1; i<=n; i++)  {  for(int j=1; j<=n; j++)  {  if(i==j)  {  mp[i][j]=INF;  continue;  }  scanf("%d",&mp[i][j]);  }  }  
}  
struct node  
{  int visp[22];//标记哪些点走了  int st;//起点  int st_p;//起点的邻接点  int ed;//终点  int ed_p;//终点的邻接点  int k;//走过的点数  int sumv;//经过路径的距离  int lb;//目标函数的值  bool operator <(const node &p )const  {  return lb>p.lb;  }  
};  
priority_queue<node> q;  
int low,up;  
int inq[22];  
//确定上界  
int dfs(int u,int k,int l)  
{  if(k==n) return l+mp[u][1];  int minlen=INF , p;  for(int i=1; i<=n; i++)  {  if(inq[i]==0&&minlen>mp[u][i])/*取与所有点的连边中最小的边*/  {  minlen=mp[u][i];  p=i;  }  }  inq[p]=1;  return dfs(p,k+1,l+minlen);  
}  
int get_lb(node p)  
{  int ret=p.sumv*2;//路径上的点的距离  int min1=INF,min2=INF;//起点和终点连出来的边  for(int i=1; i<=n; i++)  {  if(p.visp[i]==0&&min1>mp[i][p.st])  {  min1=mp[i][p.st];  }  }  ret+=min1;  for(int i=1; i<=n; i++)  {  if(p.visp[i]==0&&min2>mp[p.ed][i])  {  min2=mp[p.ed][i];  }  }  ret+=min2;  for(int i=1; i<=n; i++)  {  if(p.visp[i]==0)  {  min1=min2=INF;  for(int j=1; j<=n; j++)  {  if(min1>mp[i][j])  min1=mp[i][j];  }  for(int j=1; j<=n; j++)  {  if(min2>mp[j][i])  min2=mp[j][i];  }  ret+=min1+min2;  }  }  return ret%2==0?(ret/2):(ret/2+1);  
}  
void get_up()  
{  inq[1]=1;  up=dfs(1,1,0);  
}  
void get_low()  
{  low=0;  for(int i=1; i<=n; i++)  {  /*通过排序求两个最小值*/  int min1=INF,min2=INF;  int tmpA[22];  for(int j=1; j<=n; j++)  {  tmpA[j]=mp[i][j];  }  sort(tmpA+1,tmpA+1+n);//对临时的数组进行排序  low+=tmpA[1];  }  
}  
int solve()  
{  /*贪心法确定上界*/  get_up();  /*取每行最小的边之和作为下界*/  get_low();  /*设置初始点,默认从1开始 */  node star;  star.st=1;  star.ed=1;  star.k=1;  for(int i=1; i<=n; i++) star.visp[i]=0;  star.visp[1]=1;  star.sumv=0;  star.lb=low;  /*ret为问题的解*/  int ret=INF;  q.push(star);  while(!q.empty())  {  node tmp=q.top();  q.pop();  if(tmp.k==n-1)  {  /*找最后一个没有走的点*/  int p;  for(int i=1; i<=n; i++)  {  if(tmp.visp[i]==0)  {  p=i;  break;  }  }  int ans=tmp.sumv+mp[p][tmp.st]+mp[tmp.ed][p];  node judge = q.top();  /*如果当前的路径和比所有的目标函数值都小则跳出*/  if(ans <= judge.lb)  {  ret=min(ans,ret);  break;  }  /*否则继续求其他可能的路径和，并更新上界*/  else  {  up = min(up,ans);  ret=min(ret,ans);  continue;  }  }  /*当前点可以向下扩展的点入优先级队列*/  node next;  for(int i=1; i<=n; i++)  {  if(tmp.visp[i]==0)  {  next.st=tmp.st;  /*更新路径和*/  next.sumv=tmp.sumv+mp[tmp.ed][i];  /*更新最后一个点*/  next.ed=i;  /*更新顶点数*/  next.k=tmp.k+1;  /*更新经过的顶点*/  for(int j=1; j<=n; j++) next.visp[j]=tmp.visp[j];  next.visp[i]=1;  /*求目标函数*/  next.lb=get_lb(next);  /*如果大于上界就不加入队列*/  if(next.lb>up) continue;  q.push(next);  }  }  }  return ret;  
}  
int main()  
{  in();  printf("%d\n",solve());  return 0;  
}
References. ：
  • [ 1 ]. Coursera | Java程序设计 | PKU
  • [ 2 ]. http://www.cnblogs.com/chinazhangjie/archive/2010/11/01/
    1866136.html
  • [ 3 ]. http://blog.csdn.net/lovesummerforever/article/details/18622127
  • [ 4 ]. http://blog.csdn.net/yake827/article/details/52119469

这篇关于【基础算法】(09)五大常用算法之五：分支限界法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1036828。

相关文章

HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
JS常用组件收集

JS常用组件收集

收集了一些平时遇到的前端比较优秀的组件，方便以后开发的时候查找！！！ 函数工具： Lodash 页面固定： stickUp、jQuery.Pin 轮播： unslider、swiper 开关: switch 复选框： icheck 气泡： grumble 隐藏元素： Headroom
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
常用的jdk下载地址

常用的jdk下载地址

jdk下载地址 安装方式可以看之前的博客： mac安装jdk oracle 版本：https://www.oracle.com/java/technologies/downloads/ Eclipse Temurin版本：https://adoptium.net/zh-CN/temurin/releases/ 阿里版本： github：https://github.com/
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2