當鴿子飛進大數據的籠子?

苗永梅

（寶雞職業技術學院寶雞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）資助。

苗永梅，女，碩士研究生，講師，研究方向：網絡安全實驗教學。