模拟退火算法解逻辑问题
模拟退火算法解逻辑问题
提出一个挺有意思的问题。
问题
寻找成绩最佳者
A说 不是我
B说 是C
C说 是D
D说 C胡说
（1）已知三个人说的假话 一个为真话 ，问谁是成绩最优的？
（2）已知三个人说的真话 一个为假话 ，问谁是成绩最优的？
分析
我们先用人脑看一下（1）
假如
（1）A说真话。
a:那么最好成绩者不是A；
b:B说的是假话，最好成绩者不是C；
c:C说假话，最好成绩者不是D，只能是B
d:D说C胡说，说的是真话。不成立。
那么A成绩最好。 B说是C;说的是假话，成立。
C说是D；说的是假话，成立。
D说C说的是假话，说的是真话了，不成立。
（2）B说真话
那么最好的成绩者是C
a:A说不是他，是的，不是他，但此时有两个人说真话了。
矛盾，退出。
（3）C说真话
那么最好成绩者是D；
D说不是他，假话，虚伪；
A说不是他，的确不是他，真话，矛盾，退出。
（4）D说真话
C就是胡说的，C说是D，所以最好的成绩者不是D；
B说是C，B应该说假话，因为最好成绩者不是C
A说不是他，A应该说假话，那么最好成绩者是A
成立。
因此，对于（1）来说，最好的成绩者是A。
（分析到此，我的大脑已耗尽80%了``-_-``）
寻找成绩最佳者
A说 不是我
B说 是C
C说 是D
D说 C胡说
（2）已知三个人说的真话 一个为假话 ，问谁是成绩最优的？
我们再用人脑看一下（2）
假如
（1）A说假话。
a:那么最好成绩者是A；
b:B说的是真话，最好成绩者是C；
不成立。
（2）B说假话
那么最好的成绩者不是C
a:A说不是他，是的，不是A。
b:C说是D，那么最好成绩者是D；
c:D说C胡说，矛盾
（3）C说假话
那么最好成绩者不是D；
D说不是他，真话；
A说不是他，的确不是他，真话。
B说是C，那么最好的成绩者是C；
那么最好的成绩者是C
（4）D说假话
C就不是胡说的，C说是D，所以最好的成绩者就是D；
B说是C，B应该说真话，矛盾了；
因此，对于（2）来说，最好的成绩者是D。
我的大脑已经停止工作（待机中。。。。。）
这还就是三四个人，要是一堆人，我就不用活了。于是，我想想，能不能用算法解决此类的问题呢？
算法思路分析
如果使用算法，怎么去分析这个问题呢？毕竟，计算机不会像我们这样进行逻辑分析的。
先分析问题（1）吧。
寻找成绩最佳者
A说 不是我
B说 是C
C说 是D
D说 C胡说
（1）已知三个人说的假话 一个为真话 ，问谁是成绩最优的？
已知的是，三个人说假话，一个人说真话。有多少种可能呢？
假如说，说真话为1，假话为0
【0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0】
总计4种可能。
这四种可能中，只要有矛盾的，就不成立。
因此，我们再定义一个记录矛盾个数的变量
if (矛盾个数>0)
break;
其次，我们还要将问题转化成数学语言。
“A说 不是我”这句话转化成数学语言，是什么样子的呢？
恩，我们还需要定义一个记录最佳成绩者的变量index.
index=[0 1 2 3]最佳成绩者可以是A，B，C，D。
然后，我们进行一个巧妙的设想。对于遗传算法，变量有两个，一个是说真话的人，一个是最佳成绩者。其中Person=(0 ,1 ,2 ,3)表示人（A，B，C，D），index表示最佳成绩者（0,1,2,3）表示（A，B，C，D），适应度函数是谁呢？
适应度函数取矛盾的个数。目标矛盾的个数最小。
啊哈，现在我们就把问题转化成了一个数学模型了。
现在我们进行编码求解吧。
先说一下，我采用了什么算法呢？
一开始，我打算采用遗传算法。但是不行。
因为遗传算法中的交叉根本不能用，变异也只能整数变异。
其次，适应度函数不是连续的。
所以，我采用了模拟退火算法。
程序运行结果
从图中可以看出，运行大约29代的时候，才出现结果。
说真话的是3——D。
最好成绩者0——A。
与我们分析的第一问的结果是一致的。
这次效果比较好，运行8代的时候就出现了结果。
这次运行28代才出现正确的结果。
我们想一下，如果程序一个一个试，需要去试多少次。
4*4=16次。
也就是说，我们通过计算16次的结果，我的这个程序却运行了不止16次。
这是由于我没有去除之前的结果，也就是说，有很多次是重复的。
为了提高效率，可以使用禁忌搜索算法。
有兴趣的朋友可以留言讨论这个问题。
算法不足：
我的算法甚至可以说是瞎蒙的。也的确，因为这是离散的，而且几乎没有规律可循。只能根据已知的规则进行判断。
建议采用禁忌搜索算法。
如果你有其他的想法，我们一起交流讨论。