15-求解

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

2.3.2　求解

现在万事俱备了。回想一下，当用搜索函数 bfs() 、 dfs() 和 astar() 求解问题时，返回的是一个 Node ，最后会用 node_to_path() 将其转换为导出解法的状态列表。对求解传教士和食人族问题而言，我们还需要一种方案将这个列表转换为能打印出来供人理解的一系列步骤。

函数 display_solution() 将解题步骤转换为打印输出——可供阅读的解法。它的工作原理是记录最终状态的同时迭代遍历解题步骤中的所有状态。它会查看最终状态与当前正在迭代状态之间的差异，以找出每次渡河的传教士和食人族的人数及其方向。具体代码如代码清单2-34所示。

代码清单2-34　missionaries.py（续）

def display_solution(path: List[MCState]):
    if len(path) == 0: # sanity check
        return
    old_state: MCState = path[0]
    print(old_state)
    for current_state in path[1:]:
        if current_state.boat:
            print("{} missionaries and {} cannibals moved from the east bank to the 
                   west bank.\n"
            .format(old_state.em - current_state.em, old_state.ec - current_state.ec))
        else:
            print("{} missionaries and {} cannibals moved from the west bank to the
                  east bank.\n"
            .format(old_state.wm - current_state.wm, old_state.wc - current_state.wc))
        print(current_state)
        old_state = current_state

MCState 知道如何用 __str__() 来美观地打印出对其自身的总结， display_solution() 函数充分利用了这一事实。

最后一件需要完成的事情就是解决传教士和食人族问题。因为我们已经实现了一些通用的搜索函数，所以只要顺手复用一下这些函数就可解出了。本方案将采用 bfs() ，因为 dfs() 需要把值相同而引用不同的状态都标记为相等状态，而 astar() 需要启发式信息。具体代码如代码清单2-35所示。

代码清单2-35　missionaries.py（续）

if __name__ == "__main__":
    start: MCState = MCState(MAX_NUM, MAX_NUM, True)
    solution: Optional[Node[MCState]] = bfs(start, MCState.goal_test, MCState.successors)
    if solution is None:
        print("No solution found!")
    else:
        path: List[MCState] = node_to_path(solution)
        display_solution(path)

很高兴看到通用的搜索函数使用起来如此地灵活，能轻松地适用于多种问题的求解。输出结果应该类似于如下所示（有删节）：

On the west bank there are 3 missionaries and 3 cannibals.
On the east bank there are 0 missionaries and 0 cannibals.
The boast is on the west bank.
0 missionaries and 2 cannibals moved from the west bank to the east bank.
On the west bank there are 3 missionaries and 1 cannibals.
On the east bank there are 0 missionaries and 2 cannibals.
The boast is on the east bank.
0 missionaries and 1 cannibals moved from the east bank to the west bank.
...
On the west bank there are 0 missionaries and 0 cannibals.
On the east bank there are 3 missionaries and 3 cannibals.
The boast is on the east bank.

Previous 上一篇本节目录 Next 下一篇

15-求解

2.3.2 求解

2.3.2　求解