知识库

知识库资源

当前位置:首页>知识库
全部 14 商业 3

分支定界:怎样决定谁是“被淘汰者”?

时间:2021-04-24   访问量:1046

欢迎来到我的《算法通识课》

上一讲我们说到,动态规划的算法策略会面临维度爆炸的问题,可能性太多,动态规划就不好用了。那有什么算法策略能处理这个问题呢?

这就是我们这一讲要说的分支定界法。它能够“修剪”掉那些不会出现最优解的搜索空间,搜索空间减小了,搜索最优解也就快了。

那么,分支定界法是怎么决定哪部分需要修剪掉呢?我们这一讲就来回答这个问题。

1 组合优化:谁是最优的答案

分支定界法挺复杂的,我们从一个实际问题开始。

这些年,电动汽车越来越普及,为电动汽车服务的配套充电设施也在不断地完善。如果你是充电站布局的规划师,现在要建20个充电站,你会把充电站建在什么地方呢?

你可能会这么做:先调研一下,找出那些人口比较密集,而且地皮成本比较低的区域,作为备选地点;然后,把所有备选地点按照覆盖人口数量,从高到低排序,选最靠前的20个。

是不是挺有道理的?但这里有个问题,就是备选地点之间的距离。

有些备选地点之间的距离特别近。

假设每个充电站能覆盖的,都是一个半径为5公里的圆形区域。但如果两个备选地点挨得比较近,比如只有1公里,两个充电站覆盖的范围有重叠,那它们覆盖的人口数就大大减少了。

好,那我们做一些局部调整,避免充电站覆盖区域有重叠。这样总行了吧?还是不行,这个问题就更关键了。就是你没法说明这个部署方案,是最优的方案。

这类的问题,叫“组合优化”问题,在算法领域名气很大。

什么是“组合”呢?就是说你的每个决策都有几种可能性,比如某个地方“放”还是“不放”充电站,这就是两种可能性。当决策变量的个数多了,它们之间就产生了许多决策组合。这就是组合。

而“优化”呢,就是你要最大化或者最小化一个目标。

组合优化问题的特点是,找到一个可行的解不难,但找到最优解,特别难。因为所有可能的组合方案构成的搜索空间太大了,你一个一个地试,不知道要试到什么时候。

遇到这样的问题,我们该怎么考虑呢?

这就好像你的面前有一棵大树,大树有很多的分枝,每一个枝头上都结了一个苹果。你想找到所有苹果当中最大的一个。但一个一个摘下来比较,太慢了。

更好的方法是,把那些结出的苹果明显比较小的分枝都剪掉,而只留下少量的树枝,再把有限、少量的苹果进行比较。

采用这样的策略而设计出来的算法,就叫分支定界法。

2 分支定界:分支、定界、剪枝

要想把分支定界算法理解透,有三个关键词我们要理清楚。“分支”“定界”,还有一个包含在里面的隐藏关键词“剪枝”。我们分开来说。

先说说分支。

分支就是把问题解的不同可能性,分开去考虑。

比如你想研制一种超薄的显示器,实现这个目的的方案有多种,液晶技术、等离子技术,都可行。于是你让两个厂家分别进行探索,最后看谁更好,就用谁的,不用的那个就被淘汰了。这就是分支。

但你可能听了前面的课程,想起来我们前面还讲了一个,能把大问题拆解成小问题的“分治”策略。分支跟分治有什么区别呢?

我们还拿显示器来举例。

你想设计超薄显示器,于是让一个厂家去设计显示面板,一个去设计电源,一个去设计外观。最后三个厂家的结果拼在一起,成了最终的显示器设计。每家都贡献了价值。这叫分治。

用算法领域的话来说,分治需要对问题的“输入”进行分解,而分支需要对问题“解的搜索空间”进行分解。

回到我们充电站部署的问题。在这个问题里,怎么“分支”呢?

在所有北京市的充电站备选地点当中,你觉得,在北京火车站建充电站是个好选择,但又不是很肯定。于是分派了任务,让助手张三去探索所有在北京站建充电站的部署方案,而让李四去探索所有不在北京站建充电站的部署方案。

你看,你把所有部署方案组成的搜索空间,分成了相互不重叠的两部分,这个过程就是分支。

那光有分支就足够解决问题了吗?还不够。

分支的目的是淘汰一些解。要想淘汰,就得依赖“定界”和“剪枝”。举个例子。

比如说,你要找一个中学当中个子最高的学生。你大概率会从高中部里面去找,但万一初中部里有个小姚明呢?

所以问题的关键就在于,在不测身高的情况下,怎么判断初中部没有全校最高的学生呢?

假设初中部刚刚进行了春游。春游的地方有个山洞,山洞高1.8米。所有初中生都进了山洞,既没有弯腰的,也没有磕到头的。

这就是说,初中部学生的身高没有超过一米八的。这个“1.8米”就是初中部这个分支的一个上界。这个过程就叫“定界”。如果高中部里已经有一个一米八以上的学生了,那我们就可以放心地淘汰整个初中部。这个过程叫“剪枝”。

我们用算法领域的说法,再概括一下。

“定界”就是估计某个子搜索空间中最优解的上界的过程。“剪枝”是当某个子搜索空间能获得的目标上界,比不上某个已知的可行方案,就直接把这个子空间淘汰的过程。

把它们合在一起,就是分支定界法。还是用充电站的例子,我们把整个过程说一下。

首先,我们要找到一个可行解,当作临时的最优解,并且计算一下它对应的目标值。

比如说,我们最开始说的方案,就是在覆盖人口最多的前20个备选地点建充电站,就是一个可行解。我们可以把它当作临时最优解,算算它能覆盖的人口是多少,比如说,覆盖了200万人。

然后,我们把整个搜索空间,根据某个变量进行分支操作。比如我们把所有的方案,分成了两部分,一部分都在北京站建充电站,一部分都不在北京站建充电站。

这时,我们就可以进行定界分析了。我们可能会发现,不在北京站建充电站的那些方案,能覆盖的人口上界是190万。比刚刚的临时最优解200万少,那这部分的方案就可以全都淘汰掉。

于是,我们只计算包括北京站的方案就可以了。我们继续对这些方案进行分支操作,让它分支成更多新的子搜索空间,重复进行定界分析。

如果在继续分支的过程里,你发现有一个方案,能覆盖300万人,超过了原来的临时最优解200万。那就可以把这个方案,替换掉原来的,成为新的临时最优解。

最后,当所有的子空间,要么被剪枝,要么小到可以直接评估之后,这时的临时最优解就不再是“临时”的了,而变成了整个问题的最优解。到此为止,问题解决完毕。

3 如何让分支定界法更高效

听起来分支定界算法很有效吧。其实和其他算法一样,它也有它的有效条件。效果好不好,主要取决于我们能多有效地进行剪枝。

你看,如果我们只进行分支,不进行剪枝,那就和把整个搜索空间全部算一遍没有区别,计算的效率没有提高。这也就是为什么,为了让分支定界法高效运行,算法工程师探索了各种各样的方法,目的就是多多地进行剪枝。

不过,有的时候,就算我们有好的分支定界策略,解决组合优化问题还是要花很长时间。这个时候,怎么办?

算法工程师的策略叫,“提前停止”,特别有用。

什么叫提前停止呢?就是在没找到问题最优解的时候,提前停止对最优解的搜索。

回到充电站部署的问题。如果我们已经有一个不错的临时最优解,假设它预期覆盖的人口是990多万。而定界分析告诉我们最优解的上界是1000万。也就是说,我们的临时最优解,离真正的最优解的距离不到1%。

这时候,我们还要去追求最后那1%吗?很可能不需要。

在实际问题中,参数的测量或者估计往往没有那么准确。即使找到最优解,应用到实际中,可能也有偏差。这样的话,我们完全可以提前停止算法运行。虽然舍弃了所谓的最优解,但却大大地节省了算法运行的时间。

 划重点

1 组合优化是一类特别难解决的问题,它的搜索空间大,我们很难确定谁是最优解。
2 分支定界法是把分支、定界、剪枝三个过程结合在一起,减小搜索空间,保证找到组合优化问题最优解的算法策略。 3 要让分支定界法高效,从根本上是要进行有效的剪枝。为了进一步提升分支定界法的效率,我们可以使用提前停止的策略。

最后,给你留一道思考题。你有没有这样的经历:在进行某些决策的时候发现有好多个选择,你估计了每个选择能带来好处的上界,然后确定了哪些能直接淘汰而不再考虑?欢迎留言,分享你的故事给我。

我们刚刚提到了一种放弃最优解的思想,其实有一种很重要的算法策略,背后的思想就是它,这就是启发式算法策略。我们下一讲详细来说。


上一篇:动态规划:怎样从小问题出发,逐级解决大问题?

下一篇:启发式:放弃最优解之后,怎么办?

发表评论:

评论记录:

未查询到任何数据!
点击这里给我发消息

在线咨询

咨询专员 点击这里给我发消息

点击这里给我发消息 售后服务专员

在线咨询

免费通话

24小时免费咨询

请输入您的联系电话,座机请加区号

免费通话

微信扫一扫

微信联系
返回顶部