1、 问题描述及实验要求
请用A*算法实现野人过河问题，（1）分析设计估价函数f（2）采用C语言或Python编程实现（代码中适当加注释，输出具有可读性）。
问题描述：设有m个传教士和n个野人来到河边，打算乘一只船从左岸渡到右岸去，该船每次最多载3人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡河过去？试采用宽带优先和深度优先方法分析搜索过程。（说明：传教士和野人都会划船，测试：m=n=3）
2、 算法描述
- 构造状态空间
这个题目的状态空间秒数为一组整数对（a，b，flag）。 - a是左边岸上剩下的传教士数
b是左边岸上剩下的野人数目
flag取值为1时，船在左岸；flag取值为0是，船在右岸。
所以，初始状态为（m，n，1），目的状态为（0，0，0）。
- 设计节点的数据结构
可以想象到，这个题目应该采用树形结构来解，所以如何建立每个节点的数据结构就是难点。这里我是用Python写的算法，结点的数据结构如下：
class Point: def __init__(self, a, b, flag): self.a = a # 左岸传教士数量 self.b = b # 左岸野人数量 self.flag = flag # flag = 1: 船在左岸；flag = 0: 船在右岸 self.father = None self.node = [a, b, flag] self.g = 0 self.f = 0 # f = g+h
比较重要的是Point结点的father属性，指明了子节点与父节点的关系，保证了树形结构的准确性。g属性代表节点的深度，f是启发信息。
- 代码运行介绍
i 首先定义了传教士数目、野人数目、open表、closed表，声明了Point类，定义了初始节点init（3，3，3）和目的节点（0，0，0）。
ii 在开始进行A_star算法之前，先定义几个函数：
1） safe：判断该节点内在左岸、右岸、船舶上的传教士数目是否大于野人数目或者有一方为0；
2） equal：判断两个节点是否相同。这里防止组合“爆炸”（老师上课说的）或者说是死循环。这里是为了检测OPEN表和CLOSED表写的函数；
3） back：判断该节点是否是父节点，防止节点重复；
4） in_list：判断这个节点是否在某个表中。用来判断新生成的节点是否在OPEN表或者CLOSED表中。
5） h：启发信息。返回的是该节点时，左岸剩下的野人数与传教士数减去船的容量乘以flag，即：s.a + s.b –K * s.flag。因为作为启发信息，从起点到目标节点时，此时用的h启发信息是经过推导的最小步骤数，相当于h*。
6） open_sort：根据节点的f属性的大小，对OPEN表里面的节点排序
iii 开始编写BFS算法和DFS算法：
1） 首先，先把初始节点init放入到OPEN表中，然后遍历OPEN表；
2） 如果OPEN中取出的节点是目的节点goal，那么结束遍历；否则把这个节点从OPEN表取出，放入CLOUSED表；
3） 然后根据此节点，来得到它的子节点，它的子节点要满足几个规则：符合题目规定的安全问题；不是父节点；不在OPEN表中；不在CLOUSED表中；
4） 把该节点的f属性、father属性、g属性指定好。判断该new节点是否已经出现在open表中，如果已经出现了而且它的f属性值更好，说明它更优，那么把之前的移除，把这个插入。Open表同理。如果该new节点在open表和closed表都没有，那么把它直接插入到open表。最后根据f属性的值，对open表的节点排序。
iV 最后打印一下路径，就可显示出解。
3、 代码
import operator A = 3 # 传教士数量 B = 3 # 野人数量 K = 3 # 最大乘坐人数量 OPEN = [] # open表 CLOSED = [] # closed表 class Point: def __init__(self, a, b, flag): self.a = a # 左岸传教士数量 self.b = b # 左岸野人数量 self.flag = flag # flag = 1: 船在左岸；flag = 0: 船在右岸 self.father = None self.node = [a, b, flag] self.g = 0 self.f = 0 # f = g+h init = Point(A, B, 1) # 初始节点 goal = Point(0, 0, 0) # 目标节点 # 启发函数 def h(s): return s.a + s.b - K * s.flag # 判断传教士是否安全 def safe(s): if s.a > A or s.a < 0 or s.b > B or s.b < 0 or (s.a != 0 and s.a < s.b) or (s.a != A and A - s.a < B - s.b): return False else: return True def equal(a, b): if a.node == b.node: return True # 判断当前状态与父状态是否一致 def back(new, s): if s.father is None: return False return equal(new, s.father) # 将open_list以f值进行排序 def open_sort(l): the_key = operator.attrgetter('f') # 指定属性排序的key l.sort(key=the_key) # 扩展节点时在open表和closed表中找原来是否存在相同mcb属性的节点 def in_list(new, l): for item in l: if new.node == item.node: return True, item return False, None def A_star(s): global OPEN, CLOSED OPEN = [s] CLOSED = [] while OPEN: # open表非空 get = OPEN[0] # 取出open表第一个元素get if get.node == goal.node: # 判断是否为目标节点 return get OPEN.remove(get) # 将get从open表移出 CLOSED.append(get) # 将get加入closed表 # 以下得到一个get的新子节点new并考虑是否放入open for i in range(A): # 上船传教士 for j in range(B): # 上船野人 # 船上非法情况 if i + j == 0 or i + j > K or (i != 0 and i < j): continue if get.flag == 1: # 当前船在左岸，下一状态统计船在右岸的情况 new = Point(get.a - i, get.b - j, 0) else: # 当前船在右岸，下一状态统计船在左岸的情况 new = Point(get.a + i, get.b + j, 1) if not safe(new) or back(new, get): # 状态非法或new折返了 pass # 如果要拓展的节点满足以上情况，将它的父亲设为当前节点，计算f，并对open_list排序 else: new.father = get new.g = get.g + 1 # 与起点的距离 new.f = get.g + h(get) # f = g + h # 如果new在open表中 if in_list(new, OPEN)[0]: old = in_list(new, OPEN)[1] if new.f < old.f: # new的f<open表相同状态的f OPEN.remove(old) OPEN.append(new) open_sort(OPEN) else: pass # 继续，如果new在closed表中 elif in_list(new, CLOSED)[0]: old = in_list(new, CLOSED)[1] if new.f < old.f: # 将old从closed删除，并重新加入open CLOSED.remove(old) OPEN.append(new) open_sort(OPEN) else: pass else: OPEN.append(new) open_sort(OPEN) print('OPEN表：') for o in OPEN: print(o.node,o.g,o.f) # 递归打印路径 def printPath(f): if f is None: return printPath(f.father) print(f.node) if __name__ == '__main__': final = A_star(init) if final: print('有解，解为：') printPath(final) else: print('无解！')
4、 实验结果分析
实验结果截图：
图1-A算法解决野人渡河
图2-A算法结果分析
5、 实验体会
A*算法有助于提高算法的效率，但是如何构建启发函数是关键。
在我看来，只要启发函数的值与初始状态到最终状态的趋势一致，那么这个启发函数就是可行的。比如，传教士与野人这题，趋势就是，传教士与野人的人数都是趋于减少，所以我设置启发函数为，两者的和，是可行的。
但是还要考虑到启发函数的值要尽量小的问题。
然而，最有效的启发函数，还是需要推导出公式来的。随便找的可能也行，但是效果可能不会好，效率也不会高。本题的启发函数是m+n-2,这是按照最小的步数，推导出来的结果。
