本文参考 佳佳原创的博客 及 wizyoung的代码 ，感谢二位。
野人过河问题有很多场景，有说美女和野人的，有说传教士和野人的，有说地主和仆人的…… 手动滑稽）
m 个美女和 n 个野人要过河，只有一条船，船最多可以载 b 个人。任何情况下（河的两岸、船上）只要野人的数量大于美女的数量，野人就会吃掉美女。问，怎样在保证安全的情况下，尽可能快地让所有人过河或者列出所有可行的路线；若无解直接返回。
分析
初看到这个问题，先是带了几个具体数值进去，手动模拟过河，对过河场景有了点感觉，但还是很盲目。佳佳原创的博客 里用数学语言对问题进行了描述：锁定河的一岸，初始状态是河左岸有 m 个美女， n 个野人，目标状态是河左岸 0 个美女，0 个野人；再用 1 0 表示船的状态，1 表示船在左岸，0表示在右岸。这样问题就变成了将 [m, n, 1] 转换为 [0, 0, 0]，限制条件是要保证美女的安全、船不能超载。
算法实现
如何实现算法呢？wizyoung 用的是A*算法（对此我只简单地了解了下，没有深入）。代码的关键在于启发函数（虽然函数很简单），它返回的是从状态 s 到终态的最佳路径代价估计。
def h(s):
return s.missionary + s.beast - boat_limit * s.b
代码定义了 open_list 来保存已经生成但是还没考察的状态，closed_list 来保存已经考察过的状态。在 A_star 中遍历 open_list 获取当前状态，然后根据船的位置及人员组成情况生成新的状态，代码中用 上船 表示。我认为原代码中这一部分可稍作改进（好像又觉得不太对，暂时保留吧） ：
# 上船到下一个状态 i表示上船的传教士人数，j表示上船的野人人数 回左岸的时候一个人接就可以
for i in range(1 + min(current_state.missionary, boat_limit) if current_state.b == 1 else 2):
for j in range(1 + min(current_state.beast, boat_limit) if current_state.b == 1 else 2):
# 非法和不安全的情况
if i + j <= 0 or i + j > boat_limit or (i != 0 and i < j):
continue
#当前船在左岸
if current_state.b == 1:
new_state = State(current_state.missionary - i, current_state.beast - j, 0)
# 当前船在右岸
if current_state.b == 0:
new_state = State(current_state.missionary + i, current_state.beast + j, 1)
如果新状态安全且没有回滚，那么将新状态的父亲状态设为当前状态，新状态的实际代价为当前状态实际状态加一：
if safe(new_state) and not back(new_state, current_state):
print('新状态：%s' % new_state.node)
new_state.father = current_state
new_state.g = current_state.g + 1
new_state.f = new_state.g + h(current_state)
然后看新状态是否在 open_list 和 closed_list 中存在了，如果且新状态代价估计小于旧状态的，则删除对应的旧状态。最后将新状态添加到 open_list 继续循环。
我对着 wizyoung 的代码敲了一遍以加深理解，并做了些小改动。 再次感谢二位。