《算法的乐趣》第十六节

本节讨论用穷举算法解决倒水问题的状态建模与搜索方法。倒水动作与静止状态结合产生状态变化，持续变化形成一棵状态树，以[8,0,0]为根，树上所有状态构成解空间……

本节讨论用穷举算法解决倒水问题的状态建模与搜索方法。倒水动作与静止状态结合产生状态变化，持续变化形成一棵状态树，以[8,0,0]为根，树上所有状态构成解空间，其中一条从根到目标状态的分支即为答案，输出时按状态转换路径还原成动作列表。

倒水动作用三元组{from,to,water}描述，包含倒出桶、倒入桶和倒水量，只有倒出桶有水且倒入桶有空间才是合法动作；初始状态的动作用-1表示未知来源，记作{-1,1,8}。

搜索算法可选深度优先或广度优先：广度优先不易出现状态环路但占内存多，深度优先省内存但需处理重复状态。本题要求记录完整路径，故采用深度优先遍历。遍历时对三个桶两两全排列得到6种倒水动作，再用CanTakeDumpAction()判断合法性（不能倒向自身、倒出桶非空、倒入桶未满）。为避免环路和提高效率，用双端队列记录已搜索状态，新状态若已存在则跳过回溯，否则加入记录并继续递归搜索。终止条件为出现最终状态[4,4,0]或动作组合遍历完毕。找到结果时由PrintResult()输出过程，DumpWater()负责执行实际倒水并绑定动作三元组生成新状态。