冷雨萱武侠八卦：扫地僧是谁？-iShamu
冷雨萱*友情提醒：想让莫愁请您吃饭或者兼职加入各种高科技创业团队的请加李莫愁微信号：lisearchr 注明“约吃饭”或者“进入团队Team“
李莫愁说
过年年了，上班了，莫愁带大家多点无聊的事情。本文选取了北京天安门广场和金庸书院作为试点，通过建立扫地的数学模型，进行了一些假设。扫地看起来是最容易的事情，实际上也是一件非常难的事情。
我们扫地僧大师除了有高深的武功，也有成熟的阅历、非常人的气度，精通医道，通晓佛经，具大智慧，平时除了钻研泡妞吃饭，还帮李莫愁介绍对象。在书院群雄庆贺金庸老爷子93周岁生日的那天，大师在藏经阁席地而坐，开讲科学....
在不同的环境下，我们应该如何扫地？这个问题颇能激发人的好奇心。针对如何扫好地，本文选取了两个人尽皆知的地方来开展优化：一是北京天安门广场，二是金庸书院。前者雄踞帝都，浩浩然也，然游人如织，弃物颇多，为室外场所之代表；后者名冠江南，英才汇聚，而器具遍置，清扫不易，为室内场所之代表。
而以下的数学模型也正试图给出相关的建议（关于模型可能存在的问题和其他注记，请见文末“扫地僧有话说”一节）。在回答这个问题之前，让我们先想想自己是怎么扫地的。这看似颇为平凡，但要清楚表述人们扫地的模式还是相当不易。二维平面上的扫地模式，归纳地来看，大致不外乎以下三种：
1. 合纵连横型：沿一条轴等间隔地清扫，废弃物被近似地集中到另一条与之正交的直线上，最后沿此直线收集。这种模式常见于形状规则且垃圾不多的场所。
2. 蛇形游走型：从起始点开始按一定方式（通常为S型路线）无重复地遍历整个区域，最后结束于终点。这种模式的核心思想就是避免走回头路，但考虑到实际情况，遍历时仍可能带来折返，造成一定的随机性。
3. 四面开花型：选定若干个垃圾较多的区域，将相邻区域的垃圾集中于此，分块收集。这种模式在地形稍复杂或垃圾分布比较集中之处颇为常用。
为了较为精确地开展讨论，我们假定整个场所只有一名扫地僧工作，带着一柄扫把、一个畚箕（容量有限），并在畚箕将满之时前往唯一一个固定的垃圾桶倾倒垃圾。此外，我们设定如下几个变量：
表一模型变量一览
变量名
符号
变量类型
表达式
备注
扫地僧位置
x
自变量
x = (x, y)
下文中按网格的划分，以整数对形式表示之，并取左上为（1,1）
垃圾通量
Q(D, x)
因变量
D为给定区域
清洁率
K(x)
因变量
实际意义保证了此极限存在，下文中取1~6之间的整型离散值
皮鞋成本
s(x)
因变量
本为经济学术语，本文用以描述扫地僧走过的总路程
扫地僧出发点
x0
初始条件
初始清洁率
K0
初始条件
垃圾桶位置
xbin
参量
畚箕容量
W
参量
统一设定
我们没有取时间作为变量，这是因为我们已经默认了扫地僧的移动速度恒定不便，从而扫地时间仅依赖于路程（而非位移，也非某一点的清洁率），于是路程s(x)是本文的重点。为了论述方便，我们仅考虑两种方式的移动：横向或纵向移动时，s(x)增加1；而按对角线移动时，s(x)增加√2。此外，对于畚箕容量W，不妨统一设为15，作为一个恒定的参量。
什么？！！你居然看到这里了？朋友，你居然又耐心读到这里？莫愁佩服你，莫愁一定要请你吃饭，您加 Lisearcher注明“吃”莫愁就一定请您吃饭，无论你在哪里。
? 数据处理
一切就绪后，一个天气晴朗的周六下午，扫地僧即将开始工作。作为专业的扫地僧，他知道他将清扫的场地——天安门广场和金庸书院，分别在哪些区域垃圾较少，哪些区域弃物众多。以下是以2017年3月22日14点整为例的天安门广场人流密度图。此外，扫地僧为了进一步明确工作环境，对这图中的信息进行网格划分，并依此得到以下的清洁率分布图。
图1 2017年3月22日14:00天安门广场人流密度分布图
图2 2017年3月22日14:00天安门广场清洁率分布图
同一时间的金庸书院，各方英杰正庆祝金庸先生九十高寿，热闹非凡。书剑堂、台门、侠居三处地方正待打扫，区块分布和相应的清洁率如下图所示：
图4 2017年3月22日14:00金庸书院清洁率分布图
? 模型设计
在上一节的基础上，扫地僧便可探寻更好的扫地方式了。首先来检验之前提到的三种模式——合纵连横型、蛇形游走型和四面开花型——各有怎样的表现。
1、合纵连横型
首先要解决的是如何确定两条正交轴。容易看到，第一条轴确定一系列平行线，称之为平行轴；而第二条轴（垂直轴）应满足两个条件：必须通过垃圾桶所在区块，且轴两侧的垃圾通量基本相同。另外，取垂直轴所经长度超过S1/2/2的网格为中轴区块。对于天安门广场和金庸书院，分别选取正交轴如下：
确定中轴区块之后，按照合纵连横模式的规则，扫地僧任选一侧，由远及近地沿平行轴将边缘区块的垃圾扫入中轴区块，若畚箕将满，则立刻前往最近的中轴区块再折返。举个例子，考虑金庸书院的（5,1）区块，扫地僧扫到这里时，最近的中轴区块是（3,3），于是他便按（5,1）（4,2）（3,3）移动，畚箕中最后装的垃圾量是2 + 4 = 6 < 15，所以不需半途前往（3,3）。又如（2,10）区块，考虑到地形限制，（6,7）不能达到，于是扫地僧应当沿着（2,10）（3,9）（4,8）（4,7）（4,6）来到中轴区块（4,5），但注意此时畚箕已满（2 + 4 + 4 + 4 + 4 >15），扫地僧在到达（4,7）后不能再清扫（4,6），而是直接来到（4,5）。
类似地计算所有区块，加总即为初次移动距离；在从最远的中轴区块沿垂直轴向着垃圾桶清扫，又得到二次移动距离。结果如下：
天安门广场
出发点：（7,1）终到点：（1,5）
初次移动距离s1：37√2+31√2
二次移动距离s2： 27√2+24
总移动距离s： 64√2+55≈209.51
金庸书院
出发点：（5,10） 终到点：（1,1）
初次移动距离s1：38√2+66
二次移动距离s2：55√2+14
总移动距离s：93√2+80≈304.52
2、蛇形游走型
蛇形游走的思路非常简单，只需沿固定的S型路线从距离垃圾桶最远的区块开始清扫，每当畚箕将满时便立即前往垃圾桶并折返。天安门广场的蛇形游走清扫路线如下：
图5 天安门广场的蛇形游走型清扫线路（红点表示因畚箕将满而折返）
考虑折返的情况，略去少量的计算步骤，我们将最终结果罗列如下：
天安门广场
出发点：（9,1） 终到点：（1,5）
折返点：（8,2）（7,5）（6,1）（5,5）（4,2）（3,4）（2,4）（1,3）
清扫路程s1：44
单程折返距离s2：18√2+12
总路程s = s1 + 2s2= 36√2+68≈154.91
完全类似地，扫地僧又计算出金庸书院的清扫情况。
出发点：（2,10）终到点：（1,1）
折返点：（3,9）（4,7）（3,5）（3,4）（7,4）（9,4）（6,3）（3,3）（1 ,2）（5,2）
清扫路程s1：6√2+43
单程折返距离s2：19√2+24
总路程s = s1 + 2s2= 44√2+91≈197.23
3、四面开花型
扫地僧若按此清扫，则需先确定“花”在何方，即确定将垃圾集中到哪几个小块，最后再统一运走。易见，这些小块本身清洁率要高（即不清洁）且四周垃圾通量较大，他们彼此也应当比较分散。另外，垃圾桶本身显然是集中点。以金庸书院为例，取（1,1）（3,3）和（4,8）为集中点，我们得到下图所示三大区块。
图6 金庸书院的四面开花型清扫分划（红点表示集中点）
区块的划分中，每个网格都必须从属于比它更靠近垃圾桶的集中点所对应的区块。于是，扫地僧先把垃圾集中到各个集中点路程的代价记为垃圾集中路程s1，紧接着，扫地僧再将垃圾从集中点运送到垃圾桶，由于此段路线都需要来回移动，总路程的计算中，垃圾运送距离s2须乘以2。
仍以金庸书院为例，扫地僧对书院做了划分后，选定初始点（2,10），按上述规则可自动生成如下的清扫路线：
图7 金庸书院的四面开花型清扫线路（红点表示集中点）
类似的，天安门广场的情况如下图所示：
图8 天安门广场的四面开花型清扫线路（红点表示集中点）
从而我们有如下的结果：
天安门广场
出发点：（9,1）终到点：（1,5）
集中点：（1,5）（2,4）（5,3）
垃圾集中路程s1：53√2+21
垃圾运送距离s2：11√2+8
总路程s = s1 + 2s2= 75√2+37≈143.07
金庸书院
出发点：（2,10）终到点：（1,1）
集中点：（1,1）（3,3）（4,8）
垃圾集中路程s1：16√2+75
垃圾运送距离s2：23√2+12
总路程s = s1 + 2s2= 62√2+99≈248.68
? 比较与分析
利用上面的数据，为了更清晰地说明三种已有扫地模式的优劣，我们将结果集中反映在下面的图表中。
上面的图表中竖直方向的刻度代表路程。容易看到，路程越短则总时间也越短，从而可以认为较小的总路程体现了较优的扫地方法。上图中，三种已有的扫地模式之间显现出明显的差异：合纵连横的扫地方式——沿一组行线归并后再沿垂直轴清扫——在两个场地中都体现出劣势，且分别比最优解慢46.4%和54.4%，是不可取的，而最关键的原因是这种方式不能保证每一次在平行轴上移动时都运载足够的垃圾，以至于扫地僧将大量的时间浪费在了来回的路程上；蛇形游走的方式在金庸书院的设定下表现出优异的性能，但在天安门广场上却还是会让扫地僧多有一些冤枉路，其原因主要在于折返点有时离垃圾桶很远，导致部分折返路程缺乏效率；最后，四面开花的扫地方式在形状规则、垃圾分布集中的地方——如天安门广场上——有着最高的效率，但总体的结果反映出它的适用性可能会被地形所限。
综合这些讨论，两个关键思想是可以再作发掘的：一是蛇形游走方式中的“无回溯性”，除了折返点之外所有路线都不会往返走动；二是四面开花方式中的“集中效应”，这可以避免长途折返的低效率。
? 终极扫地僧的扫地方法
金庸书院的扫地僧在研究了已有的扫地方式后，从“无回溯性”和“集中效应”入手，提出一种如下的扫地方式：
首先，扫地僧扫地前，利用垃圾通量确定三个集中点（包括垃圾桶所在的网格），划分成三个区块，这一点与四面开花型基本相同；
其次，每次向着集中点清扫垃圾时，局部采用蛇形游走方式，仅在有地形限制的折角处和折返处采用对角移动，从而使往返路程最小化；
最后，分划可能有多种形式，只选取其中是每个区块垃圾通量最接近畚箕容量整数倍的分划方式。
这样，距离确定最终的扫地方式只有一步之遥，扫地僧只需确定出发点即可。和前三种方式一样，我们选定距离终点（也就是垃圾桶所在网格）路径最远的点作为出发点。注意此时不应采用直线距离，否则就相当于默认了扫地僧在某些情况下可以穿过场地以外的区域，而这会给模型带来不必要的麻烦。
在这三个条件之下，给定场地形状和清洁率的分布，扫地僧已经可以得确定的 扫地路线。由此得到的天安门广场和金庸书院的扫地路线分别如下。
图9 天安门广场的最终清扫线路（红点表示集中点）
图10 金庸书院的最终清扫线路（红点表示集中点）
类似于之前的计算，我们可以得到扫地僧在这种扫地方法之下的移动距离，分别是：
天安门广场
出发点：（9,1） 终到点：（1,5）
集中点：（1,5）（2,4）（5,3）
垃圾集中路程s1：47√2+12
垃圾运送距离s2：11√2+8
总路程s = s1 + 2s2= 69√2+28≈125.58
金庸书院
出发点：（2,10）终到点：（1,1）
集中点：（1,1）（3,3）（4,8）
垃圾集中路程s1：13√2+62
垃圾运送距离s2：25√2+12
总路程s = s1 + 2s2= 63√2+86≈175.10
从这些结果中可以看出：终极扫地僧的方法在两处设定中的表现均优于所有其他方法，比最慢的一种分别节省将近一半（40.1%和42.5%）的时间，且路线也比大多数扫法更为简洁。从设计机理上看，扫地僧的这种扫地方法100%优于合纵连横型和四面开花型的方式，并且考虑到折返点的距离，在绝大多数地形中优于蛇形游走的方式，确实是对已有扫地模式的一种改进。
? 扫地僧的建议
在庞杂的分析之后，金庸书院的扫地僧终于可以给众人以扫地的建议了。为了以路线最短且最省时的方式扫地，以下的步骤可能是有益的：
1. 确定局部垃圾通量的极大点作为集中点，通俗地说就是找出最脏的区域，之后的清扫中不断把邻近的垃圾集中到这些区域；
2. 正常清扫时沿S型路线蛇形前进，畚箕将满时才用最近路线走到集中点；
3. 最后，把各个集中点的垃圾运送到垃圾桶。
? 扫地僧有话说
如何更好地扫地本身是一个模糊的问题，本文很大程度上带有娱乐成分。数学这一学科，尽管体现在数学建模中，其严谨性仍是不容破坏的，从而笔者必须声明文中的一些结果可能并不令人满意。
文中为了能够描述这个问题而作了诸多假设，如只能用扫把和畚箕，扫地速度恒定，且网格化后的路线近似等于真实路线等等。这些假设是对真实情况的简化，与现实生活中的扫地有相似之处，但显然还有不小的距离。对于最后一个假设，在一定的限制条件下，原则上可以通过Ascoli引理证明其合理性，即不断取分划的加细，得到的路径曲线族一致收敛。
正如前面所说，任何模型都面临着过度简化和难以求解的双重矛盾，虽然笔者尽可能地两者取其中，两害取其轻，但不管怎样，数学模型的力量在目前尚是薄弱的，对现实的解释力也十分有限。扫地本身源自现实，提高生活舒适度的方式大约有两种，一是在现有的条件上进行最优化，二是创造新的工具。前者体现在扫地中，如我们的终极扫地僧模型所示，在其他方面则有各种不断完善的金融衍生品；后者体现在扫地中如清扫机器人和各种自动清洁装置，在历史上则如电子、微电子器件的诞生。前者改善生活，后者常常使效率成倍提高，进而创造新的生活模式。扫地模型本身好坏并不重要，但所有理智的扫地僧都应当看到，单纯的思想实验性质的模型有着相当的局限性；笔者在文章的最后加上这句拙见：只有以谦卑的态度认识到数学模型和人类思维的局限，也许才算是真正开悟的“扫地僧”。古墓派
莫愁一声轻啸，纵下屋去，扑向饭桌，在狗年请您吃饭，你居然看到这里了，那就扫个二维码，填个表格，莫愁请您吃饭
莫愁饭局，欢迎约莫愁吃饭
科学解决不了的事情，
让我们用吃饭来解决