现在来看计算机的解法。但是如果人类都觉得困难,计算机要怎么解呢?回答是死算,把所有的可能性都翻一遍。如果所有的可能行动都搜寻过了而还是没有找到合理的过河方案,那就证明这个题目是无解的。为此,需要编制一个程序让计算机去把所有可能性都穷举一遍。
为了便于用文字说明问题,下面就用竖线|代表河流,G代表传教士,R代表野人,B代表小船。这些代号组合起来,就表示游戏的一种状态。例如GGRR|GRB表示两个传教士和两个野人在河流的左岸,一个传教士和一个野人在河流的右岸,小船也在右岸。我们知道,这个状态是安全的。再比如,GRRB|GGR表示一个传教士和两个野人在左岸,小船也在左岸,而两个传教士和一个野人在河流的右岸。并且,这个状态是不安全的,左岸那个传教士会被旁边的两个野人吃掉。
而这些人乘船渡河的行动,就造成游戏在不同的状态之间的切换。例如,开始状态为GGGRRRB|,一个传教士和一个野人乘船渡河到对岸,游戏状态就变成GGRR|GRB。如果一个行动不会使状态变得不安全,我们就说这个行动是安全的。
为了行文方便,再用一些代号指称这些状态(代号:=状态)和行动。B(G)表示一个传教士渡河,B(R)表示一个野人渡河,B(GR)表示一个传教士和一个野人一起渡河,其余类推。另外,S1-->B1-->S2表示行动B1把状态S1变为S2。
开始的时候,大家都在河流的左边,表示为
Begin:=GGGRRRB|
我们希望通过一系列的安全行动,使得游戏状态变为
End=:|GGGRRRB
为此,从Begin出发,考虑所有的可能行动所能达成的状态;再从新得到的那些安全状态出发,对它们中的每一个都考虑可能的行动,这样会到达另外一些安全状态,其中有一些已经在前面出现过,可以忽略不计,而另外一些是还没有出现过的新状态。之后就是反复在新安全状态的基础上考虑可能的行动,直至到达End状态宣布游戏胜利结束,或者因无法添加新安全状态而宣布游戏无解。
在详细的演示之前,这里还有一个疑问,为什么上面的办法是可行的。即,为何如果有解这种办法一定能找到解,为何无解则能证明无解。这个问题就留给读者去思考了。提示:游戏的状态总数(包括不安全的)是有限的;另外,从每个状态出发,最多有五个可能的行动(包括不安全的):B(G), B(R), B(GG), B(RR), B(GR)。
那么,从Begin出发能够得到哪些状态呢?如下所示:
Begin-->B(G)-->GGRRR|GB;不安全
Begin-->B(R)-->S11:=GGGRR|RB;新状态
Begin-->B(GG)-->GRRR|GGB;不安全
Begin-->B(RR)-->S12:=GGGR|RRB;新状态
Begin-->B(GR)-->S13:=GGRR|GRB;新状态
接下来:
S11-->B(R)-->Begin;老状态
S12-->B(R)-->S21:=GGGRRB|R;新状态
S12-->B(RR)-->Begin;老状态
S13-->B(G)-->S21:=GGGRRB|R;老状态(重复出现的新状态)
S13-->B(R)-->GGRRRB|G;不安全
因此接下来就只有一个状态S21:=GGGRRB|R需要考虑了:
S21-->B(G)-->S13;老状态
S21-->B(R)-->S12;老状态
S21-->B(GG)-->GRR|GGRB;不安全
S21-->B(RR)-->S31:=GGG|RRRB;新状态
S21-->B(GR)-->GGR|GRRB;老状态
接下来:
S31-->B(R)-->S41:=GGGRB|RR;新状态
S31-->B(RR)-->S21;老状态
接下来:
S41-->B(G)-->GGR|GRRB;不安全
S41-->B(R)-->S31;老状态
S41-->B(GG)-->S51:=GR|GGRRB;新状态
S41-->B(GR)-->GG|GRRRB;不安全
接下来:
S51-->B(G)-->GGRB|GRR;不安全
S51-->B(R)-->GRRB|GGR;不安全
S51-->B(GG)-->S41;老状态
S51-->B(RR)-->GRRRB|GG;不安全
S51-->B(GR)-->S61:=GGRRB|GR;新状态
现在又只有一个新状态S61:=GGRRB|GR了:
S61-->B(G)-->GRR|GGRB;不安全
S61-->B(R)-->GGR|GRRB;不安全
S61-->B(GG)-->S71:=RR|GGGRB;新状态
S61-->B(RR)-->GG|GRRRB;不安全
S61-->B(GR)-->S51:=GR|GGRRB;老状态
接下来:
S71-->B(G)-->GRRB|GGR;不安全
S71-->B(R)-->S81:=RRRB|GGG;新状态
S71-->B(GG)-->S61;老状态
S71-->B(GR)-->GRRRB|GG;不安全
接下来:
S81-->B(R)-->S71;老状态
S81-->B(RR)-->S91:=R|GGGRRB;新状态
接下来:
S91-->B(G)-->S101:=GRB|GGRR;新状态
S91-->B(R)-->S102:=RRB|GGGR;新状态
S91-->B(GG)-->GGRB|GRR;不安全
S91-->B(RR)-->S81;老状态
S91-->B(GR)-->GRRB|GGR;不安全
接下来:
S101-->B(G)-->S91;老状态
S101-->B(R)-->G|GGRRRB;不安全
S101-->B(GR)-->End;胜利!
S102-->B(R)-->S91;老状态
S102-->B(RR)-->End;胜利!
当然,程序不是按照上面的方式编写的,那样等于人为告诉计算机怎么玩这个游戏了。这里只是演示一下计算机解题过程中所经历的一些步骤。其实上面这个过程可以画成一张图。而计算机使用的就是一种称为“图搜索”的穷举算法。读者们请自己画着玩玩,会很有意思的。(改天有空了,我也画一张贴上来)
在这里,计算机没有使用任何类似于棋谱的东西。后面我要给出一个更加复杂的游戏,并解释计算机如何利用类似于棋谱的“知识”帮助它更快地找到答案。
(今天发现写错了,已更正
)
[
本帖最后由 火车是运茶的 于 2009-4-17 22:38 编辑 ].