用盲目搜索解决传教士与野人过河问题

1.实验目的

通过本实验理解并体会宽度优先搜索和深度优先搜索的基本算法和编程实现，学会建立状态空间图，并用搜索的方法来解决问题。

2.实验内容

使用Python设计程序求解传教士与野人过河问题，分别使用宽度优先搜索和深度优先搜索来实现问题求解。

实验参考代码说明：

（1）复习Python中列表元素的添加方法append（）和pop（），比较一下pop（）和pop（0）的区别。(www.xing528.com)

（2）在参考代码中，文件State.py中设计了一个状态类State。它包括一些基本属性，比如状态变量“m”、“c”、“dir”和State相关的一些参数、参数值限制和缺省值等，以及一些基本方法，比如状态值的合法性判断方法is Valid方法，依据规则产生合法的后继节点的successor方法、add ValidSuccessors方法等。

（3）Python中没有结构体，所以一般用类来代替C语言中的结构体。类属于面向对象的程序设计，具有更多的优点。因此，将方向和参数也定义成类，并存储在文件Constants.py中。

（4）Graph.py中实现了宽度优先搜索和深度优先搜索两种方法。

（5）主文件Main.py中用了一个列表moves来获取船上所有合法的载人情况，列表中的元素是“（m，c）”元组。该列表作为参数传入State类，供successors方法调用。Main.py文件中还实现了两个函数runBFS和runDFS，且这两个函数使用Graph类和State类作为参数。