趣话最大割问题:花果山之群猴博弈

Jack小新
2024-08-29 11:38:59
本帖最后由 Jack小新 于 2024-8-29 11:54 编辑

 

趋利避害,是所有生物遵循的自然法则,人类也不例外。

 

举个例子,假如你是某生鲜平台的配送员,载着满满一电瓶车货物,要将其配送至片区内多个住户。

 

在多劳多得的规则下,要想多赚点配送费,你就不得不合理规划配送路径,尽量少走回头路,以最快速度完成配送,最终返回站点。

 

如果是你,会怎样规划路线?

 

都说世界是数学的,生活中诸如此类的困扰,都可以归为一类,叫做组合优化问题:在有限个可能解的集合中,找出最优解。

 

如何顺应人类趋利避害的天性,做出利益最大化的抉择?还得是魔法打败魔法。

 

现在可以请出今天的主角最大割问题 (Max-Cut Problem):一种能够帮我们合理规划复杂组合关系的数学问题。

 

何为最大割问题?

 

对绝大多数不熟悉数学或编程的读者来说,一看「最大割」这仨字,必然断定它是个既枯燥又难懂的学术名词。

 

事实上,它蛮有趣、也并不难懂。在解释概念之前,各位不妨先听个故事,名字叫做《该死,美猴王那纷纷扰扰的花果山》。

 

话说,花果山上有只石猴,獐鹿为友,猕猿为亲,携众猴入驻花果山后,被拥立为美猴王。

 

可美猴王也有烦恼:正所谓猴性顽劣,目之所及,众猴抢盆夺碗,占灶争床,眼瞅花果山恐再无宁时,真真是头疼。

 

于是,美猴王体内趋利避害的远古基因开始觉醒:怎样才能让花果山最大程度地保持和平

 

不如取消原有大杂居,试试分区管理?可碍于辖区内面积有限,只有两座山头可分,又该怎么分呢?

 

美猴王开始了一场思想实验。

 

情况 1:假设有 2 只见面就掐架的猴,外加两座猴山;

 

这种情况下,总共有 4 种分区方案。

 

 

那么,在这 4 种方案中,哪种最能维持整体和平呢?

 

我们将这 2 只猴看作一组关系,通过辅助线实线代表小猴之间见面就掐的矛盾来观察。

 

 

可以看到,切割这组猴的关系线时,图 1 和 2 没有线被切断,图 3 和 4 切断线的数量为 1。

 

这意味着,此种情况下,切断 1 条关系线的方案,可以维持花果山和平。

 

情况 2:假设有 4 只彼此都不服的猴,外加两座猴山;

 

这种情况下,总共有 16 种分区方案。(出于篇幅考虑,下面仅展示 4 种。)

 

 

在这些方案中,哪种最能维持花果山和平呢?我们依然将 4 只猴看作一组关系,通过辅助线来观察。

 

 

可以看到,在切割这组包含 4 只猴的关系线时,图 3 被切断的线最多,数量为 4。

 

也就是说,在此种情况下,切断 4 条关系线的方案,最能维持花果山和平。

 

情况 3:假设有 5 只猴 (有些猴之间有矛盾,有些猴之间没有,仍用连线表示),外加两座猴山;

 

 

这种情况下,怎样将这 5 只猴合理分开呢?

 

感兴趣的读者可以找张纸画一画。根据前两种假设我们可知,最能维持花果山和平的方案,被切断的关系线数量一定最多。

 

放在此种假设中,最优方案切断的数量线为 5 条 (尽管右侧山上其中两只猴也有矛盾,但这种分割法已经是最优解了)。

 

换成平面切割视图,则是这样:

 

 

OK,故事听到这里,恭喜,你已经会求解最大割问题了。

 

所谓最大割 Max-Cut 问题,就是求一种分割方法:给定一张无向图,将所有顶点分割成两群,使得同时被切断的边数量最大。

 

故事中,猴子对应图中的顶点,俩猴之间的矛盾则对应边。

 

但你有没有留意到,在前面的假设中,我们默认猴子间的矛盾值都相同,倘若不同呢?比如猴甲与猴乙之间有杀父之仇夺妻之恨,见面肯定以死相拼;但猴甲和猴丁只是因为昨天分桃时猴丁插了个队,见面顶多会呸一声。

 

实际生活中,在矛盾值有高有低的情况下,我们还需要优先把一言不合便要掐个你死我活的隔开。

 

当每条边都有一个权重系数时,分割目标函数的思路就会发生变化,从使被切断的边数量最大,变为使切割边的总权重之和最大。这种情况较刚才的假设更为复杂,我们称其为加权最大割问题。

 

到此,最大割问题的描述就讲完了,这种轻松涨知识的感觉是不是还不赖?诶等等,各位先别急着开香槟。

 

这个世界,远比想象中复杂。

 

最大割问题为何难解?

 

刚才是谁按下了各位开香槟的手?哦对,是我,但我是有原因的。

 

不知各位读者有没有留意到,刚才发生在美猴王故事中的几种假设,我们都能靠手工画图完成。

 

从专业角度来说,我们用的是穷举法。  

 

穷举法,是指根据题目给定的约束条件,从可能的集合中一一列举出问题答案,再依次判定:令命题成立者,即为解。
一言以蔽之:大力出奇迹。
 

倘若不是 2、4、5 只猴子,而是 10、50、100、甚至直接捅穿猴子窝成千上万只猴子,我们还能用穷举法计算出结果吗?

 

不能。这里存在一个被称为计算复杂度的巨大挑战。

 

在计算机科学中,一个问题的计算复杂度,就是看运行这个算法所需要的资源量,特别是时间 (CPU 占用时间) 和空间 (内存占用时间)。如果问题的计算复杂度比较高,当问题的变量数增大时,需要筛选的备选答案数量(我们称之为“解空间”)就可能以极快的速度增加

 

当需要筛选的可能答案数量过于巨大时,哪怕派出当今运行速度最快的计算机也极难完成,因为计算机需要太多时间来验证所有方案的可能性。

 

这时,局面就会开始失控。比如旅行商问题:3 句话就能描述清楚,但很小的变量数就能形成一个极其庞大的解空间,从而使得用计算机去穷举的“蛮力解法”耗时变得极长。 

 

旅行商问题:一个商品推销员要遍访多个城市,期间所有城市不能重复经过,最后回到出发城市。
他该如何规划最短路径?
 

 

旅行商问题的描述看上去很简单吧?直觉上是不是很好求解?

 

但是!从数学角度来看,它的挑战在于,随着城市数的增加,求解的计算量会呈“阶乘级”上升。

 

 

大家能一眼就念出 15 个城市可能存在的路径组合数量吗?

 

数学上,我们用一个非常形象的词来描述这种现象,叫做组合爆炸:变量 (城市数) 只是增加了一点点,解空间的可能性就快速增长成一个极其庞大的规模。

 

回到花果山的故事中,当猴子数量、矛盾关系数量持续增加时,美猴王所要考虑的分割方案的数量同样会呈阶乘级增长,再也没法用简单的“画图穷举”的方法去求解了。

 

至此,我们可以对最大割问题做个简单总结:

 

1)  作为组合优化问题的一种,随着问题规模的增加,可能的解决方案数量会呈阶乘级增长;(采用穷举法,几乎不可能在可接受的时间内找到全局最优解。)

 

2) 当解决方案数量呈阶乘级增长时,求解组合优化问题的难度,将大大超出经典计算机的能力范围。

 

最大割问题有何现实意义?
 

你或许会想,尽管明白了什么是最大割问题,但它有什么用呢?现实生活中哪儿有那么多调皮的小猴需要我去调度?

 

诶,千万别小瞧了它。

 

德国当代著名作家丹尼尔·凯曼说过:数学并不会使人脱离现实世界,恰恰相反,数学牵引着现实,让人更加接近现实,让现实更加清晰。

 

最大割问题,就是这句话的优雅诠释。

 

远的不提,咱就拿自动驾驶来说,汽车要想安全地自行驾驶,必须得能感知周围环境,除了要能“认清”车辆行人的行动轨迹,还得能分清路面移动的物体是野猫还是塑料袋,从而精准避障。

 

但汽车的“眼睛”是摄像头和雷达,这些感官设备带给它的只是一堆一堆的 01 数据,还需要它的大脑去“识别”这些数据所代表的“具体含义”。

 

以摄像头为例,它所获取的是一帧帧平面二维图片,图片则由一个个不同色值的像素点构成。至于哪些像素点应该被归纳为物体 A,哪些像素点应该被归纳为物体 B,就需要自动驾驶的“大脑”去计算和识别。

 

要实现这一点,离不开图像分割技术,也就是通过将图像划分成互不相交的区域,实现物体分离,再一一将这些物体识别成不同的对象,进而去判断这些对象会不会动、会怎么动,与汽车自身的运动会不会产生碰撞等,这才能让汽车“看清楚路”。

 

 

最大割问题可以帮助完成图像分割

 

汽车周身摄像头拍摄到的画面,可以将其映射为带权无向图,像素视为图中节点。这样一来,图像分割问题就转化成了图的顶点划分问题,利用最小剪切准则,得到图像的最佳分割,汽车就能“看见”路况,进而科学决策,做到安全驾驶。

 

这只是最大割问题应用的冰山一角,事实上,它的应用或变体遍布整个商业领域,是构成我们数字社会非常重要的算法基础

 

1、金融:动态投资组合优化、欺诈检测、信用评估、客户划分;
2、通信:MIMO 波束选择及资源分配;
3、设计:电路板优化设计;
4、能源:主动配电网的路径优化;
5、交通:大规模交通流路径规划;
6、物流:包裹配送优化、物流仓布局;
7、医疗:疾病诊断与医学图像分析;
8、生物制药:小分子对接筛选;
9、工业制造:生产流程优化、整体质量控制流程优化;
10、电子商务:产品推荐、库存管理;
... ...

 

“世界是数学的。”美国思想家爱默生说:“在它巨大流畅的曲线中没有意外。”

 

要我说,意外还是有的。

 

你瞧,在如何发现世界中的数学、如何用好数学等方面,都藏着意外。

 

本文转载自微信公众号:量子前哨

191
0
0
0
关于作者
相关文章
  • n皇后问题的三种解法
    N皇后问题是一个经典的问题,在一个N*N的棋盘上放置N个皇后,每行一个并使其不能互相攻击(同一 ...
    了解详情 
  • 优化算法----模拟退火算法(Simulated Annealing,SA) ...
    简介 模拟退火算法是80年代初发展起来的一种基于Monte Carlo迭代求解策略的随机性寻优算法 ...
    了解详情 
  • 智能调度,高效赋能:揭秘算力网络资源优化分配之道 ...
    算力网络,简单来说,就是将计算能力像水电一样进行输送的网络。想象一下,我们平时使用的手机、 ...
    了解详情 
在本版发帖返回顶部
快速回复 返回顶部 返回列表