14-表达问题

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

2.3.1　表达问题

这里将通过一个记录西岸情况的数据结构将问题表达出来。西岸有多少名传教士和食人族？独木舟在西岸吗？只要有了西岸的情况，就可以计算出东岸的情况了，因为人不在西岸就在东岸。

首先要创建一个助手变量，便于记录传教士或食人族的最多人数。然后将定义主类。具体代码如代码清单2-30所示。

代码清单2-30　missionaries.py

from __future__ import annotations
from typing import List, Optional
from generic_search import bfs, Node, node_to_path
MAX_NUM: int = 3
class MCState:
    def __init__(self, missionaries: int, cannibals: int, boat: bool) -> None:
        self.wm: int = missionaries # west bank missionaries
        self.wc: int = cannibals # west bank cannibals
        self.em: int = MAX_NUM - self.wm  # east bank missionaries
        self.ec: int = MAX_NUM - self.wc  # east bank cannibals
        self.boat: bool = boat
    def __str__(self) -> str:
        return ("On the west bank there are {} missionaries and {} cannibals.\n" 
                "On the east bank there are {} missionaries and {} cannibals.\n"
                "The boat is on the {} bank.")\
         .format(self.wm, self.wc, self.em, self.ec, ("west" if self.boat else "east"))

类 MCState 依据西岸的传教士和食人族的数量、独木舟的位置进行初始化。它还知道如何把自己美观地打印出来，这在以后显示问题的解时会很有用。

如果在现有的搜索函数范围内使用该函数，就意味着必须定义一个函数用于测试某个状态是否就是目标状态，并定义另一个函数用于从任一状态查找后续步骤。正如求解迷宫问题一样，测试目标的函数相当简单。这里的目标就是到达一种满足条件的状态，即所有传教士和食人族都到达了东岸。测试目标的函数将作为 MCState 的方法加入。具体代码如代码清单2-31所示。

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

def goal_test(self) -> bool:
    return self.is_legal and self.em == MAX_NUM and self.ec == MAX_NUM

为了创建查找后续步骤的函数，必须遍历从西岸到东岸的所有可能的移动步骤，并检查每一步移动是否会生成满足条件的状态。回想一下，满足条件的状态就是食人族的人数在两岸都没有超过传教士的人数。为了检测这一点，可以定义一个助手属性（作为 MCState 的方法）检查状态是否满足条件。具体代码如代码清单2-32所示。

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

@property
def is_legal(self) -> bool:
    if self.wm < self.wc and self.wm > 0:
        return False
    if self.em < self.ec and self.em > 0:
        return False
    return True

为了表达清楚，实际的 successors 函数有点儿啰唆。它从独木舟所在的河岸出发，将尝试加入所有可能的1人或2人的过河组合。一旦所有可能的移动方案全部添加完毕，该函数就会通过列表推导式（list comprehension）过滤出确实满足条件的解。此函数还是属于 MCState 的一个方法。具体代码如代码清单2-33所示。

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

def successors(self) -> List[MCState]:
    sucs: List[MCState] = []
    if self.boat: # boat on west bank
        if self.wm > 1:
            sucs.append(MCState(self.wm - 2, self.wc, not self.boat))
        if self.wm > 0:
            sucs.append(MCState(self.wm - 1, self.wc, not self.boat))
        if self.wc > 1:
            sucs.append(MCState(self.wm, self.wc - 2, not self.boat))
        if self.wc > 0:
            sucs.append(MCState(self.wm, self.wc - 1, not self.boat))
        if (self.wc > 0) and (self.wm > 0):
            sucs.append(MCState(self.wm - 1, self.wc - 1, not self.boat))
    else: # boat on east bank
        if self.em > 1:
            sucs.append(MCState(self.wm + 2, self.wc, not self.boat))
        if self.em > 0:
            sucs.append(MCState(self.wm + 1, self.wc, not self.boat))
        if self.ec > 1:
            sucs.append(MCState(self.wm, self.wc + 2, not self.boat))
        if self.ec > 0:
            sucs.append(MCState(self.wm, self.wc + 1, not self.boat))
        if (self.ec > 0) and (self.em > 0):
            sucs.append(MCState(self.wm + 1, self.wc + 1, not self.boat))
    return [x for x in sucs if x.is_legal]

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

14-表达问题

2.3.1 表达问题

2.3.1　表达问题