《算法的乐趣》第十七节

本节先总结了上一章的水桶分水问题：手工画状态图推演到第六种方法就放弃了，改用算法穷举，最终找到16种倒水方法，其中最快的一种只需7步。

本节先总结了上一章的水桶分水问题：手工画状态图推演到第六种方法就放弃了，改用算法穷举，最终找到16种倒水方法，其中最快的一种只需7步。

随后进入妖怪与和尚过河问题：三个和尚和三个妖怪要乘一条只能载两人的小船过河，任何一侧和尚数量少于妖怪时就会被吃掉，目标是让全部安全过河。求解思路是把某一时刻和尚、妖怪和船的位置组合定义为"状态"，从初始状态出发穷举所有可能的状态转换，找到通向最终状态的路径。状态用五元组表示（两岸和尚数、妖怪数和船的位置），初始为[3,3,0,0,左岸]，目标为[0,0,3,3,对岸]。过河动作共10种（单人或双人、和尚或妖怪、去或回），通过统一的动作表把差异转化为数量加减，避免大量分支判断。搜索采用深度优先遍历，只用一个队列保存当前分支的状态，逐个状态尝试10种动作生成新状态，直至到达最终状态并输出过河过程。