《算法的乐趣》第十八节

本节讲述和尚与妖怪过河问题的状态树搜索。状态树遍历靠动作模型驱动，算法定义了10种过河动作，逐一处理动作列表即可完成搜索。

本节讲述和尚与妖怪过河问题的状态树搜索。状态树遍历靠动作模型驱动，算法定义了10种过河动作，逐一处理动作列表即可完成搜索。判断动作是否合法要看船的位置和两岸人数，不合法的动作直接排除，避免出现负数等错误状态。搜索采用深度优先，需处理重复状态：正反动作可能形成状态环路导致死循环，已搜索过的状态可跳过或直接给出结果，起到剪枝作用；已处理状态用双端队列组织。实现上以SearchState()递归搜索，从队列取状态，判断是否为最终状态，否则尝试各动作生成新状态；MakeActionNewState()通过属性加减统一处理动作，省去分支语句。最终得到过河方案共四种。