史坦因豪斯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（p， q）表示分数p/q， t（f1， f2）表示区间[f1， f2]， f1， f2为分数，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）尾递归调用stainhaus0（N，K1，S1，S）。

当K0=N时， S0即为S。

程序的性能决定于部分解扩展过程中完美匹配的个数。为此可得：

程序运行找到史坦因豪斯问题在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的证明结果不同，其原因在于数学家们研究的18点问题中所有区间都定义为开区间或半开半闭区间（在前面Warmus给出的解中，其解元素均为半开半闭区间），在史坦因豪斯问题的原始表达形式中，并没有限定[0，1]的等分区间一定为闭区间或开区间，而这里给出的解元均为闭区间，这样就容许单点区间的存在，例如上述问题解中的[1/3，1/3]，而這种单点区间可以在解扩展时向左右两边连接，因此解的范围能够扩大，这也导致问题在n=19时存在解，研究中通过程序运行也证明了在容许闭区间的情况下，n=20时史坦因豪斯问题无解。

除问题2中将等分区间全部理解为闭区间的形式外，史坦因豪斯问题还可以将所有等分区间表示为开区间的形式。这时，程序中构造解的谓词需作以下修改：

参考文献

史坦因豪斯. 一百个数学问题[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无线模块实现2种报警方式：远程报警和近距离报警。近距离报警是在Lora模块通信距离范围内，实现接收端的报警提示，在实际应用中可将无线接收端置于家中，作為辅助报警手段，增加了老人跌倒后救助的成功率。本文设计的算法简洁有效，准确率高，具有较强的实用性。

参考文献：

邵宇吉，吴其林，朱治鹏，等. 一种新型腰带计步器的设计研究[J]. 电子测试，2015 （19）：111-112.

[2] 高英梅. 老年人跌倒的原因分析及护理干预[J]. 中国医药指南， 2013，11（27）：263-264.

[3] 王刚. 基于Arduino Uno平台的跌倒检测报警系统设计[J]. 单片机与嵌入式系统应用，2015（7）：49-52.

[4] 王刚，温向明，路兆铭，等. 新兴物联网技术——LoRa[J]. 信息通信技术，2017（1）：55-59，72.

[5] 刘导. 基于STM32单片机的动力锂电池管理系统[D]. 保定：河北大学， 2015.

[6] 刘艳，刘文文，王莲莲. 老年人跌倒的危险因素及护理干预[J]. 现代医药卫生，2015，31（5）：688-690.

[7] 薛源. 基于多传感器的老人跌倒检测系统的研究与应用[D]. 武汉：武汉理工大学，2011.

[8] 李飞龙. 基于三轴加速度传感器跌倒检测方法的研究[D]. 成都：电子科技大学， 2015.

[9] 孙子文， 孙晓雯. 基于加速度传感器的人体跌倒检测方法[J]. 计算机工程与科学， 2017， 39（2）：330-335.

[10]曹玉珍， 蔡伟超， 程旸. 基于MEMS加速度传感器的人体姿态检测技术[J]. 纳米技术与精密工程， 2010， 8（1）：37-41.endprint