史坦因豪斯18點問題的求解算法與結果

劉瀚文

摘要：本文給出了史坦因豪斯18點問題的一個圖論求解模型，并采用Prolog語言描述了相應的求解算法，從而構造性地解決了史坦因豪斯問題。文章分析了該算法在最壞情況下的時間復雜性，并給出了2種形式下史坦因豪斯問題的機器運行結果。

關鍵詞： 史坦因豪斯18點問題； 二部圖； 完美匹配

中圖分類號： TP391

文獻標志碼：A

文章編號：2095-2163（2017）05-0035-03

Abstract：Based on the graph theory， a solving method for Stainhauss 18 points problem is approached in this paper. The algorithm for solving the problem is given on Prolog and the Stainhauss problem is completely solved by the construction method. The complexity of the algorithm in the badest case and the running results are given too.

Keywords：Stainhaus 18 points problem； bipartite graph； perfect match

收稿日期： 2017-08-15

3問題求解程序及其性能分析

[JP2]由求解問題的圖論模型，不難設計出相應的算法和求解程序。下面是問題求解過程的Prolog描述（文中，略去了研發(fā)程序），函數(shù)f（p， q）表示分數(shù)p/q， t（f1， f2）表示區(qū)間[f1， f2]， f1， f2為分數(shù)，stainhaus為求解問題的主謂詞，stainhaus0為其尾遞歸版本，其中使用了一種典型的用變量保存中間結果的技巧。謂詞stainhaus0（N，K0，S0，S）表示目前要構造n=K0+1的解，當n=K0時的解為S0，要求做出n=N時的解S。

當K0

1）構造n=K0+1=K1的二部圖；

2）從該二部圖中尋找完美匹配；

3）基于該完美匹配將原來的部分解S0擴展為S1；

4）尾遞歸調(diào)用stainhaus0（N，K1，S1，S）。

當K0=N時， S0即為S。

程序的性能決定于部分解擴展過程中完美匹配的個數(shù)。為此可得：

程序運行找到史坦因豪斯問題在n=19時的一個解：

[0/1， 1/19]， [2/3， 2/3]， [5/6， 5/6]， [2/5， 7/17]， [1/5， 4/19]， [10/11， 11/12]， [5/9， 5/9]， [1/3， 1/3]， [11/15， 14/19]， [1/10， 2/19]， [7/15， 8/17]， [18/19， 1/1]， [5/18， 2/7]， [11/18， 5/8]， [2/15， 3/19]， [7/9， 15/19]， [1/2， 10/19]， [2/9， 5/19]， [16/19， 17/19]

與Warmus的證明結果不同，其原因在于數(shù)學家們研究的18點問題中所有區(qū)間都定義為開區(qū)間或半開半閉區(qū)間（在前面Warmus給出的解中，其解元素均為半開半閉區(qū)間），在史坦因豪斯問題的原始表達形式中，并沒有限定[0，1]的等分區(qū)間一定為閉區(qū)間或開區(qū)間，而這里給出的解元均為閉區(qū)間，這樣就容許單點區(qū)間的存在，例如上述問題解中的[1/3，1/3]，而這種單點區(qū)間可以在解擴展時向左右兩邊連接，因此解的范圍能夠擴大，這也導致問題在n=19時存在解，研究中通過程序運行也證明了在容許閉區(qū)間的情況下，n=20時史坦因豪斯問題無解。

除問題2中將等分區(qū)間全部理解為閉區(qū)間的形式外，史坦因豪斯問題還可以將所有等分區(qū)間表示為開區(qū)間的形式。這時，程序中構造解的謂詞需作以下修改：

參考文獻

史坦因豪斯. 一百個數(shù)學問題[M]. 上海：上海教育出版社，1980.

[2] [JP2]WARMUSM. A supplementary note on the irregularities of distributions[J]. Journal of Number Theory，1976，8（3）： 260-263.

[3] Weisstein， Eric W. 18-Point Problem， From MathWorld—A Wolfram Web Resource. [EB/OL]. [2017-07-31]. http：//mathworld.wolfram.com/18-PointProblem.html.

[4] GARDNERM. The last recreations： Hydras， eggs， and other mathematical mystifications[M]. New York： Springer-Verlag， 1997.

[5] BERLEKAMP E R， GRAHAM R L. Irregularities in the distributions of finite sequences[J]. Journal of Number Theory， 1970，2（2）：152-161.

[6] CHRISTOFIDESN. Graph theory： An algorithmic approach[M]. NY， USA：Academic Press， 1975.

[7] CLOCKSIN W F， MELLISH C S. Programming in Prolog[M]. NY， USA： Springer-Verlag， 1984.

[8] BONDY J A，MURTY U S R. 圖論及其應用[M]. 吳望名，李念祖，等譯. 北京：科學出版社，1984.

4結束語

本設計將三軸加速度傳感器與輔助作用的傾斜傳感器結合后通過GSM模塊與Lora無線模塊實現(xiàn)2種報警方式：遠程報警和近距離報警。近距離報警是在Lora模塊通信距離范圍內(nèi)，實現(xiàn)接收端的報警提示，在實際應用中可將無線接收端置于家中，作為輔助報警手段，增加了老人跌倒后救助的成功率。本文設計的算法簡潔有效，準確率高，具有較強的實用性。

參考文獻：

邵宇吉，吳其林，朱治鵬，等. 一種新型腰帶計步器的設計研究[J]. 電子測試，2015 （19）：111-112.

[2] 高英梅. 老年人跌倒的原因分析及護理干預[J]. 中國醫(yī)藥指南， 2013，11（27）：263-264.

[3] 王剛. 基于Arduino Uno平臺的跌倒檢測報警系統(tǒng)設計[J]. 單片機與嵌入式系統(tǒng)應用，2015（7）：49-52.

[4] 王剛，溫向明，路兆銘，等. 新興物聯(lián)網(wǎng)技術——LoRa[J]. 信息通信技術，2017（1）：55-59，72.

[5] 劉導. 基于STM32單片機的動力鋰電池管理系統(tǒng)[D]. 保定：河北大學， 2015.

[6] 劉艷，劉文文，王蓮蓮. 老年人跌倒的危險因素及護理干預[J]. 現(xiàn)代醫(yī)藥衛(wèi)生，2015，31（5）：688-690.

[7] 薛源. 基于多傳感器的老人跌倒檢測系統(tǒng)的研究與應用[D]. 武漢：武漢理工大學，2011.

[8] 李飛龍. 基于三軸加速度傳感器跌倒檢測方法的研究[D]. 成都：電子科技大學， 2015.

[9] 孫子文， 孫曉雯. 基于加速度傳感器的人體跌倒檢測方法[J]. 計算機工程與科學， 2017， 39（2）：330-335.

[10]曹玉珍， 蔡偉超， 程旸. 基于MEMS加速度傳感器的人體姿態(tài)檢測技術[J]. 納米技術與精密工程， 2010， 8（1）：37-41.endprint