用回溯法编程求解爱因斯坦谜题.pdf

《用回溯法编程求解爱因斯坦谜题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学术探讨·裁鲈发采用回溯法编程求解爱因斯坦谜题谢玉庚(中国石化中原石油化工有限责任公司，河南濮阳457004)[摘要]本文模拟人工智能的思路，用回溯法编程求解爱因斯坦谜题，使总排列数下降了7个数量级，极大提高了解题速度。程序编写了线索输入函数，把迷题线索存入向量中，可随意修改线索的内容、数量及顺序，进而对新的谜题进行重新求解，而不用修改剪枝函数的代码。适用性好。[关键词]爱因斯坦谜题：回溯法：拼图；人工智能：向量中图分类号：TPl8文献标识码：A文章编号：1008．6609(2016)10—0050—021引言爱因斯坦谜题又称Zebra谜题“】，

2、是一道很有趣的逻辑推理题，基本内容如下：有一排五间房子，每一问房子的颜色都不同，在这些房子里住着五个不同国籍的人，每个人喂养了不同的宠物，喜欢不同的饮料，抽不同的雪茄。目的是最后要找到养鱼的人。这是一个能够进行人工求解的谜题。有很多人尝试用计算机来求解问题。文献[2]列举了人工图表法和SAT求解法。文献[2]本身论述了定理证明器PVS求解法，都可以在有限的时间里取得较好的结果。文献[3】提供了编程求解法，需要在(51)5个排列中找到答案，这是个天文数字，如果能调整好合适的线索顺序，也许可以找到令人满意的求解速度。网络上也逐渐给出了具体的编程求解方

3、案如文献[4】，其基本思路属于回溯法”】，速度也很快，但不能像文献[2]所述的那些辅助办法那样具有较广泛的适用性。综合以上文献及程序，本文根据图表解题思路结合拼图的概念用回溯法及向量技术”3编写了求解爱因斯坦谜题的程序，取得了进一步的良好效果。2人工解题思路画好5行5列的空表格，先根据线索8、9、14填入固定的元素“挪威人”、“蓝色”、“牛奶”。然后根据第一条线索尽可能从最左侧的列填入其它活动的元素，再分析判断剩下的空格可否满足第二条线索，依此类推。如果不能继续满足下一个线索，则右移上一个线索的列位置，继续分析，直至符合所有的线索就可以找出谜题的

4、出答案。以下估算这种思路的排列数：首先，线索8、9、14固定了相关元素内容。其排列数都是第一个线索“英国人住红房子”只能在第3列至第5列任选其一，排列数为3。第二个线索“瑞典人养狗”可在第2、4、5列任选其一，排列数为3，依此类推，如表1所示为部分估算过程。表1表格拼图求解爱因斯坦谜题l2345国家：9，挪威2，瑞典人1，英国人颜色：14，蓝色1，红房子饮料：8，牛奶烟：宠物：2，养狗按照这种思路，本人估算的排列数总数为3。3。2+3+1t4t1+1s1，4，2+2。l+1"1=3456个，这种估算因人而异，但其数量级相差不大。这个问题的最大排列

5、数是(51)5是250亿，比这种拼图法高了7个数量级。这种思路实际上是把25个小方格的拼图简化成16个小图案的拼图，其中有12个小图案是可以左右移动的，但是因为有上下行交错占位的排斥关系，其总排列数会进一步减少。看来这种思路的确很“划算”。3具体的程序设计实现用5行5列的字符串数组stringhouses[5][5]代表5个房子，存储国家、颜色、饮料、香烟、宠物5种属性及其内容。数组初始化：线索8、9、14无需分析，用函数voidsettle．ment(int，int，string)把它们的内容直接分配到相应的数组元素作者简介：谢玉庚(1972-

6、)，男，陕西白水人，本科，工程师，研究方向为设备管理信息化。一50．学术探讨·裁萨技术里，其他的元素为空，程序中用字符串“”表示。其他12条线索每个都分为两个子因素，其列范围都可以从0到5，绿色除外。但还是需要根据不同的逻辑确定各个子因素各自的列范围。在分析过程中，有些线索的第一子因素已经在前面的线索中出现过，其列范围被视为已固定，不需进行列范围的试探，用voidinitfactorsl(int)函数处理。例如线索4和5都出现了绿房子。第二子因素的列范围确认比较复杂，其逻辑包括“自己”、“隔壁”、“左面”、“左隔壁”等类型，用函数voidinit

7、fac．tors2(int)处理。将结构structhint的对象加入向量vectorhints中，便于用while循环语句对其剪枝函数voidsearch(intl进行回溯分析。当同时满足两个子因素时，用向前试探标志factorl记录内层子因素是否完成列循环。线索号condnum加1，通过search(condnum)进入下一个线索，进行向前试探分析。不能同时满足两个子因素时进行回溯分析。线索号condnum减1后，用search(condnum)回溯到上一个线索的分析，如果其内层的子因素列循环尚未完成，则根据facto

8、rl的值穿透外层循环先进行内层循环，否则按照正常逻辑从外层循环向内层循环逐步分析。会经常发生连续回溯的情况。程序用while语句对sea