食人者和传教士问题（python实现）-阿南达文事网

食人者和传教士问题（python实现）

食人者和传教士问题

- - 问题描述
  - 解题方法
  - - - 状态空间法，深度优先搜索
  - 代码思路
  - - - 接下来，就是写代码了
  - 运行结果
  - 问题总结
  - - 1.语法错误（毕竟python是自学的，没基础知识储备）
    - 2.粗心
    - 3.思路不严谨
    - - 改错完成，撒花~~~~~~~~
  - 小感悟

问题描述

当然，问题可以也拓展一下：
左岸有m个传教士，c个食人者，船上最多可以装k个乘客
（这个能力有限，还没搞定，但网上有很多大佬的方法，虽然我也没看懂
链接指路：）

解题方法

状态空间法，深度优先搜索

状态及相关量的含义表示

相关操作及使用条件
（该博客只是解决3个食人者，3个传教士，1只船最多只能乘坐2个乘客，所以操作可以简单了解即可）

手动寻找解

代码思路

首先：声明–根据题目要求，只要输出一条有效路径即可，所以需要所有路径的可以离开了（-,-）
其次，感谢其他大佬的代码提供思路，链接指路：
（不过这个代码有点问题，就是closed中的无效结点仍然存在）

1.状态和操作可以用元组表示（m，c，b），（a，b）
2.对状态结点展开所用到的open表和closed表，就用列表 opened=[ ]，closed=[ ]
3.为了保存每一步的操作，使用字典result={ key：value },
key必须不可变，且唯一，和状态元组的特性相似
value即为每个状态对应的操作
4.需要用到的函数：
Isgoal()–判断是否是目标状态；
Islegal()–判断是否是合法状态；
Isopened()–判断是否是已经访问过的结点；
isclosed()–判断是否在closed表中；
Toopen()–将有效结点加入到open表中;
Expand()–对结点进行拓展；
Toresult()–将结点和对应的操作存入result表中；
cino()–判断closed表中的结点是否还有子节点在opened表或closed表中，若没有则在closed表删除对应结点

接下来，就是写代码了

（好刺激，改了一整天，我就是个菜鸡）

# -*- coding: utf-8 -*-
"""
Created on Thu Mar 19 18:06:05 2020@author: Administrator
"""
#m=c=3,k=2
#使用深度优先搜索，在Toopen函数中体现
import operator#判断是否是目标状态
def isgoal(node):if node[0]==0 and node[1]==0 and node[2]==0:return Trueelse:return False#判断是否是合法状态
def islegal(node):if 0<=node[0]<=3 and 0<=node[1]<=3:if node[0]==node[1] or node[0]==3 or node[0]==0:return Trueelse:return Falseelse:return False#判断是否在closed表中
def isclosed(node):global closedflag=0for n in closed:if operator.eq(n,node):flag=1breakif flag==1:return Trueelse:return False
#判断是否在opened表中
def isopen(node):global openedflag=0for n in opened:if operator.eq(n,node):#因为在python3中已经不存在python2中的cmp函数，用operator模块代替flag=1breakif flag==1:return Trueelse:return False#将结点扩展，求子结点
#按照五条可能的操作规则：(1,0),(0,1),(1,1),(2,0),(0,2)
#返回一个包含有五个元组的元组，元组可以作为函数返回值
def Expand(node):b=node[2]node1=()node2=()node3=()node4=()node5=()tnode=()if b==1:node1=(node[0]-1,node[1],0)#注意node是元组，不允许修改，也就是说node1[0]=node[0]-1，这样的写法是错误的，所以直接赋值即可node2=(node[0],node[1]-1,0)node3=(node[0]-1,node[1]-1,0)node4=(node[0]-2,node[1],0)node5=(node[0],node[1]-2,0)else:node1=(node[0]+1,node[1],1)node2=(node[0],node[1]+1,1)node3=(node[0]+1,node[1]+1,1)node4=(node[0]+2,node[1],1)node5=(node[0],node[1]+2,1)tnode=(node1,node2,node3,node4,node5)return tnode#将合法的，且不在closed表中（即还没有被访问过，或者不是之前的有效路径中的已经被删除的）的子结点添加到opened表中
#使用的insert方法在opened表的表头存入结点，使得opened列表相当于栈的功能，后进先出，实现深度优先搜索
def Toopen(tnode):global openedfor m in tnode:if islegal(m) and isclosed(m)==False:opened.insert(0,m)#将合法的，且不在closed表中（即没有被访问过,或者不是之前的有效路径中的已经被删除的）的子结点和得到的对应的操作添加到result字典中
#注意必须要求不在closed表中，否则字典会将之前的值覆盖，如果没有这个条件就会发生“即便这个结点不是有效路径的，也会将其和对应操作存进来，覆盖掉之前有效结点的值”的情况
def Toresult(ltnode):global resultif isclosed(ltnode[0])==False and islegal(ltnode[0]):result[ltnode[0]]=(1,0)if isclosed(ltnode[1])==False and islegal(ltnode[1]):result[ltnode[1]]=(0,1)if isclosed(ltnode[2])==False and islegal(ltnode[2]):result[ltnode[2]]=(1,1)if isclosed(ltnode[3])==False and islegal(ltnode[3]):result[ltnode[3]]=(2,0)if isclosed(ltnode[4])==False and islegal(ltnode[4]):result[ltnode[4]]=(0,2)#判断closed表中的结点的子结点是否在opened表中或在closed表中
#即当结点已被访问，不是目标状态，且不存在子结点或子结点下不存在有效路径，将其从closed表中删除
#因为最后closed表中存放的会是一条有效路径，所以需要将无效结点删除
def cino():global closedfor k in closed:flag1=0for x in Expand(k):if isopen(x) or isclosed(x):flag1=1if flag1==0 :closed.remove(k)node=(3,3,1)#初始结点状态
opened=[]
closed=[]
result={}#使用字典结构，可以利用键值对来存放结点状态和对应的操作，而且，即便是已经访问过，后因为路径无效又被删除的结点，在另一条路径被重新访问时，也可以覆盖原来的值（也就是操作）
opened.insert(0,node)
while opened:nodet=opened.pop(0)#pop操作直接删除指定位置的元素并返回值，取出最开始的元素，后进先出，实现深度优先if isgoal(nodet):closed.append(nodet)for i in range(0,len(closed)):if (i+1)<len(closed):print("step",i+1,"    操作前(传教士，食人者，船的位置)：",closed[i],"    操作（传教士，食人者）：",result[closed[i+1]],"    操作后：",closed[i+1])#已经搜索到目标结点，输出closed表中的有效路径，并从result字典中寻找状态对应的操作并输出breakif isclosed(nodet)==False:closed.append(nodet)#若不在closed表中，将其添加进来snode=Expand(nodet)#求该结点的子结点，用元组返回Toopen(snode)#将有效子结点添加到opened表中Toresult(snode)#将有效结点和对应操作存入result字典中cino()#将closed表中的无效结点删除

运行结果

结果正确。
代码完成，接下来我就吐槽一下我这个菜鸡遇到的问题

问题总结

1.语法错误（毕竟python是自学的，没基础知识储备）

①

这个是测试i+1能不能在这用，显然不能,改为i，(用i+1主要是想控制输出目标状态就停止) 详情如下

②

意思大概是list的index超出范围（为什么是list呢，因为我试了一下用列表来存储结点状态），主要是因为node1现在是空的，所以直接将值添加进node1就行，详情如下：

node1.append(node[0]-1)#append函数直接加载node1的末尾
node1.append(node[1])
node1.append(0)
#或者更简单的
node1=[node[0]-1,node[1],0]

如果还是用元组就更简单了：

node1=(node[0]-1,node[1],0)#其实想一下列表也可以直接这样，哦，我的脑子

③

意思是list是不可hash的，什么意思呢，就是说result是个字典，字典的key必须是不可修改的元素，显然list是修改的，（这个问题也是在将元组用列表存储时发现的），可以用tuple函数转为元组，详情如下：

result[tuple(tnode[0])]=(1,0)#当然状态结点用元组表示就不存在这个问题了

2.粗心

改完语法错误之后，运行，结果什么都没有输出

？？？小朋友，你是否有很多问号？？？
opened和closed居然全为空
检查：语法完美，思路还可以，所以。。。没找到
果然，单步调试吧

哦，天哪，我的脑袋可能是面团捏的，isgoal() 改为 islegal()
(怪不得不输出，也真是难为Toopen了)

3.思路不严谨

解决了语法和粗心，再次运行，有结果了！！！

？不过这个结果好像有点怪呀
（眼神中透着无奈）
这里面操作和操作后的状态大部分都是对应不上的
根据我为数不多的编程经验来看，这个result字典有问题
这是原来的代码：

def Toresult(ltnode):global resultresult[ltnode[0]]=(1,0)result[ltnode[1]]=(0,1)result[ltnode[2]]=(1,1)result[ltnode[3]]=(2,0)result[ltnode[4]]=(0,2)

看看这简短的代码，超级侦探认真办案！
果然，如果后面有个结点A的一个子结点B,已经出现在closed表中了，那么新的Toresult操作就会覆盖原来结点的值，从而改变了closed表中有效状态的对应操作，必须改，详情如下：

改错完成，撒花~~~~~~~~

小感悟

来自一个小透明的结语：
当初学习java的时候，觉得“哇，java好方便哦，那么多的方法都可以直接用了”，现在学了python，觉得“这玩意儿怎么能这么方便！！！”（虽然还没面向对象）。
在这里感谢我的父母，老师，同学，让我能徜徉在知识的海洋，继续努力吧！

食人者和传教士问题（python实现）