当鸽子飞进大数据的笼子∗

苗永梅

（宝鸡职业技术学院宝鸡721304）

当鸽子飞进大数据的笼子∗

苗永梅

（宝鸡职业技术学院宝鸡721304）

网购频繁，包裹数量剧增，为物流派件增加了难度。受鸽笼原理启发，将派件信息由个人转向收发点，确定鸽笼数，寻找合适的Ramsey数，确定鸽子数量，以保证发往同一地点的包裹数量较大，从而减少货运成本。

鸽笼原理；Ramsey定理；Ramsey数；包裹分拣

Class NumberTP311.13

1 引言

德国数学家狄利克雷1834年提出的“抽屉原理”，又叫“鸽笼原理［1］，是一个基本的数学原理。可以简单的描述为有n+1只鸽子，飞进n个鸽笼时，至少有一个鸽笼内有两只鸽子。

电子商务交易中，商家将商品卖给消费者，就如同鸽子飞进笼子如图1。由于消费者数量不确定，导致鸽笼数不确定。2016天猫双11全天累计订单6.57亿件。当鸽子飞进大数据的笼子，鸽子数和笼子数该如何确定，将成为优化包裹分拣的关键因素。

图1鸽笼——电商对接模型

2 鸽笼数确定方法

包裹由商家到消费者的送达过程呈星型放射状结构，形成一对多的映射，笼子数多于鸽子数；根据实际情况对笼子数进行限制，使其满足鸽子数大于笼子数，从而应用鸽笼原理解决物流中的包裹分拣问题。

2.1 鸽笼定理

设qi是正整数（i=1，2，···，n），q≥q1+q2+…+qn-n+1，如果把q个物体放入n个盒子中，则必存在一个i，使得第i个盒子中至少有qi个物体。对式子q1+q2+…+qn-n+1可变形为式（1）：

将多出的1个加入其中任何一个qi盒子可满足条件。

2.2 推论

讨论：当q一定，盒子数n越大，盒子中放置的物体数量越少，盒子数n越小，盒子中放置的物体数量越多，应用鸽笼原理解决问题，关键在于灵活地设计鸽笼数量［2］。

2.3 划分区域构造鸽笼数

构造鸽笼数有多种方法［3］：分割区间、分割图形、划分数组、划分余数；根据物流情况，应用划分区域构造鸽笼数。

全国有23个省，661个市，2.861个县区，14677个乡镇，14亿人口，网购消费者遍布各地。如果把鸽笼数选择越少，飞入的鸽子数就多，同一路经运送的货物数量就多，节约物流成本。

对消费者根据地区分类，14亿人分属23个省、661个市、2.861个县区、14677个乡镇。将物流送达呈现的星型结构图2（a）（对应14亿消费者）变成树型结构图2（b）（对应地区），逐级发送。图2（a）中的A1、A2、A3属于同一省份不同地区，在发货的第一分段可以一起打包如图2（b），发往同一省份；后面货物发送以同样树型结构逐级嵌套。

图2物流发送模型

根据实际情况，树型结构每一层数量不等，鸽笼数也随着对应变化。如第一层对应省份23个，鸽笼数确定为23个；第二层，9个市（以陕西省为例），鸽笼数确定为9个，第三层，12个县区（以宝鸡市为例）…，逐级划分；其它以此类推，将大数据的笼子数量由无限变有限，满足鸽笼原理的前提条件。

3 鸽子数确定方法

确定鸽笼数从消费者集合讨论，鸽子数的确定（发货数量），从商家集合分析；发货数量至少达到多少件以后，会出现发往同一地区的2件包裹？且期望随着发货数量的增多，发往同一地区的包裹数量增幅变大。借用鸽笼原理的一个重要推广Ramsey定理来解决这个问题。

3.1 Ramsey定理

1930英国逻辑数学家F.P.Ramsey在其论文《形式逻辑上的一个问题》［4］证明了R（3，3）=6，提出Ramsey定理；依据Ramsey定理来寻找Ramsey数，以确定鸽子数。

Ramsey数定义：

设a，b为正整数，令R(a，b)是保证有a个人彼此相识或者有b个人彼此不相识所需要的最少人数，则称R(a，b)为Ramsey数。

Ramsey定理要解决这样的问题：找一个最小的数n（Ramsey数），使得n个人中必定有a个人相识或b个人互不相识。将定义中的彼此相识理解为发往同一地点的包裹，不相识理解为发往不同地点的包裹；如果有24件包裹，23个省份，应用鸽笼原理，必有两件包裹发往同一省份，可表示为R(2，23)，求得的R(a，b)数对物流包裹分拣更有意义。

3.2 探讨R(a，23)值

随着a值继续增大，对R(a，b)进行求解，是一个很困难的问题，需要在数学公式中计算R(a，b)的上界和下界［5］。裴超平用图的分割原理计算一些Ramsey数［6］，云微、张岚、王世祥提出基于数据库的部分Ramsey数R(3，b)下界的随机排序构造方法［7］。

借鉴前人成果和Ramsey定理，结合实际情况，将问题简化为求R(a，23)（b的值确定为23）的值根据实际情况，b的值确定为23，可将问题简化为求R(a，23)的值。Ramsey数计算如下：

由定理［8］：R(a，2)=a、R(a，b)=R(b，a)

即：R(2，23)=R(23，2)=23

苏文龙［9］在论文《4个经典Ramsey数的R(3，q)的新下界》中给出R(3，23)的新下界136，即R(3，23)≥136；吴康［10］通过构造素数阶循环图找到R(4，23)新下界272，即R(4，23)≥272；罗海鹏［11］通过构造素数阶循环图得到了R(5，23)新下界422，即R(5，23)≥422。求Ramsey数是一个无止境的科学探索过程，在此只做方法借用和数值引用。

4 结语

将电子商务中的具体实例物流打包，借用数学模型鸽笼原理来优化，使原来呈星型的物流派送变成逐级发送的树型结构，节约物流成本。同时讨论当商家至少卖出多少件商品时，存在发往同一地点的包裹，即寻找Ramsey数。

求Ramsey数是一个复杂的过程，随a，b值的不同R(a，b)发生变化，且其值是一个范围，存在上、下界。论文应用Ramsey定理来求Ramsey数，提出确定鸽子数的方法，求出R(2，23)≥23，参考其它学者成果R(3，23)≥136、R(4，23)≥272、R(5，23)≥422；对R(a，23)其它值的探索将是论文后续研究的内容。

［1］卢开澄，卢华明.组合数学（第4版）［M］.北京：清华大学出版社，2014. LU Chengcheng.LU Huaming.Combinatorial mathematics（fourth edition）［M］.Beijing：Tsinghua university press，2014.

［2］翁绍铬.鸽笼原理映射及鸽笼设计［J］.天津纺织工学院学报，1995，14：135. WENG Shaoge.The pigeonhole principle mapping and pi⁃geonhole design［J］.Journal of Tianjin Textile Institute，1995，14：135.

［3］郑惠敏.鸽笼原理的秒用［J］.知识文库，2016（13）：166. ZHENG Huimin.The principle of the pigeon cage with［J］.Knowledge library，2016（13）：166.

［4］RAMSEY F P.On a problem of formal logic［J］.Proc Lond Math Soc，1930，30：264-286.

［5］欧阳丽娜.一种求解Ramsey数的DNA计算机算法［J］.软件导刊，2014（9）：48-50. OUYANG Lina.Computer algorithm for solving Ramsey number［J］.Software daokan，2014（9）：48-50.

［6］裴超平.用图的分割原理计算一些Ramsey数［J］.同济大学学报，2016，44（3）：471-472. PEI Chaoping.Calculated by segmentation principle dia⁃gram of some of the Ramsey number［J］.Journal of Tongji University，2016，44（3）：471-472.

［7］云微，张岚，王世祥.基于数据库的部分Ramsey数R（3，l）下界的随机排序构造方法［J］.湘潭大学自然科学学报，2016，38（2）：5-8. YUN Wei，ZHANG Lan，WANG Shixiang.Part of the data⁃base based on the number of Ramsey R（3，l）of the lower bounds of the random sort method［J］.Natural Science Journal of Xiangtan University，2016，38（2）：5-8.

［8］卢光辉，孙世新，杨国武.组合数学及其应用［M］.北京：清华大学出版社，2016. LU Guanghui，SUN Shixin，YANG Guowu.Combinatorial mathematics and its application［M］.Beijing：Tsinghua University press，2016.

［9］苏文龙，吴康，罗海鹏.4个经典Ramsey数的R（3，q）的新下界［J］.广西科学，2006，13（3）：161-163. SU Wenlong，WU Kang，LUO Haipeng.4 classic Ramsey number of R（3，q）of the new lower bound［J］.Guangxi science，2006，13（3）：161-163.

［10］吴康.苏文龙.罗海鹏.经典Ramsey数R（4，23）的下界［J］.广东技术师范学院学报，1997（4）：6-7. WU Kang，SU Wenlong，LUO Haipeng.The lower bound of classical Ramsey number R（4，23）［J］.Journal of Guangdong Polytechnic Normal University，1997（4）：6-7.

［11］罗海鹏，苏文龙.经典Ramsey数R（5，23）和R（5，24）的新下界［J］.甘肃科学学报，1998（3）：22-24. LUO Haipeng，SU Wenlong.The lower bound of classical Ramsey number R（4，23）［J］.Journal of Guangdong Polytechnic Normal University，1998（3）：22-24.

When Dove Flew Into the Big Data Cage

MIAO Yongmei
（Baoji Vocational Technology College，Baoji721304）

frequent online shopping，the number of parcels soared，increased difficulty for logistics.Inspired by the pigeon⁃hole principle，the individual pieces of information will be sent to receive points to determine the pigeon cage number，looking for appropriate Ramsey number，determine the number of dove，to ensure that the package sent to the same place a large quantity，so as to reduce the cost of freight.

pigeonhole principle，Ramsey theorem，Ramsey number，parcel sorting

TP311.13

10.3969/j.issn.1672-9722.2017.07.028

2017年1月10日，

2017年2月18日

国家自然科学基金（编号：51405382）；陕西省职教学会课题“互联网+”创新教育对策研究（编号：SZJG-1629）资助。

苗永梅，女，硕士研究生，讲师，研究方向：网络安全实验教学。