算法系列（2）：三只水桶等分水问题

内容简介：有一个容积为8升的水桶里装满了水，另外还有一个容积为3升的空桶和一个容积为5升的空桶，如何利用这两个空桶等分8升水？附加条件是三个水桶都没有体积刻度，也不能使用其它辅助容器。

有一个容积为8升的水桶里装满了水，另外还有一个容积为3升的空桶和一个容积为5升的空桶，如何利用这两个空桶等分8升水？附加条件是三个水桶都没有体积刻度，也不能使用其它辅助容器。

这是一道经典题目，一般人都可以在一分钟内给出答案，不过，很多人可能没有注意到这道题的答案不是唯一的。先来看看最常见的一个答案，也是目前已知最快的操作步骤，共需要7次倒水动作：

这里再给出一个稍微复杂一点的答案，这个答案需要8次倒水动作：

到底有多少种答案呢？这里先卖个关子，耐心看完本文你就知道了。

解决问题的思路

如果用人的思维方式，那么解决这个问题的关键是怎么通过倒水凑出确定的1升水或能容纳1升水的空间，考察三只水桶的容积分别是3、5和8，用这三个数做加减运算，可以得到很多组答案，例如：

3 – (5 – 3) = 1

这个策略对应了上面提到的第一种解决方法，而另一组运算：

（3 + 3）- 5 = 1

则对应了上面提到的第二种解决方法。

但是计算机并不能理解这个“1”的重要性，很难按照人类的思维方式按部就班地推导答案，因此用计算机解决这个问题，通常会选择使用“穷举法”。为什么使用穷举法？因为这不是一个典型意义上的求解最优解的问题，虽然可以暗含一个求解倒水次数最少的方法的要求，但就本质而言，常用的求解最优解问题的高效的方法都不适用于此问题。如果能够穷举解空间的全部合法解，然后通过比较找到最优解也是一种求解最优解的方法。不过就本题题意而言，并不关心什么方法最快，能求出全部等分水的方法可能更符合题意。

如果我们把某一时刻三个水桶中存水的容积称为一个状态，则问题的初始状态是8升的水桶装满水，求解的解出状态（最终状态）是8升水桶中4升水，5升水桶中4升水。穷举法的实质就是把从初始状态开始，根据某种状态变化的规则搜索全部可能的状态，每当找到一个从初始状态到最终状态的变化路径，就可以理解为找到了一种答案。这样的状态变化搜索的结果通常是得到一棵状态搜索树，根节点是初始状态，叶子节点可能是最终状态，也可能是某个无法转换到最终状态的中间状态，状态树有多少个最终状态的叶子节点，就有多少种答案。根据以上分析结果，解决本问题的算法关键有三点：首先，建立算法的状态模型；其次，确定状态树的搜索算法（暗含状态转换的规则）；最后，需要一些提高算法效率的手段，比如应用“剪枝”条件避免重复的状态搜索，还要避免状态的循环生成导致搜索算法在若干个状态之间无限循环。

状态和动作的数学模型

建立状态模型是整个算法的关键，这个状态模型不仅要能够描述静止状态，还要能够描述并记录状态转换动作，尤其是对状态转换的描述，因为这会影响到状态树搜索算法的设计。所谓的静止状态，就是某一时刻三个水桶中存水的容积，我们采用长度为3的一维向量描述这个状态。这组向量的三个值分别是容积为8升的桶中的水量、容积为5升的桶中的水量和容积为3升的桶中的水量。因此算法的初始状态就可以描述为[8 ,0, 0]，则终止状态为[4, 4, 0]。

对状态转换的描述就是在两个状态之间建立关联，在本算法中这个关联就是一个合法的倒水动作。某一时刻三个水桶中的存水状态，经过某个倒水动作后演变到一个新的存水状态，这是对状态转换的文字描述，对算法来讲，倒水状态描述就是“静止状态”＋“倒水动作”。我们用一个三元组来描述倒水动作：{from, to, water}，from是指从哪个桶中倒水，to是指将水倒向哪个桶，water是此次倒水动作所倒的水量。本模型的特例就是第一个状态如何得到，也就是[8, 0, 0]这个状态对应的倒水动作如何描述？我们用-1表示未知的水桶编号（上帝水桶），因此第一个状态对应的倒水动作就是{-1, 1, 8}。应用本模型对前面提到的第一种解决方法进行状态转换描述，整个过程如图（1）所示：

图1 一个解决方法的状态转换图

为了算法实现过程中方便数据管理，用C/C++语言描述的倒水动作三元组是一个struct，定义如下：

Action数据结构的三个属性分别对应动作三元组中的三个成员。BucketState是状态模型的C/C++语言描述，一维向量bucket_s是三个水桶中水的状态，curAction是与之对应的倒水动作，在状态模型中增加倒水动作对本题的数学模型来说不是必需的，它的存在只是为了算法结果输出的需要，就是要能够描述并记录状态转换动作。BucketState的C/C++语言描述如下所示：

状态树搜索算法

确定了状态模型后，就需要解决算法面临的第二个问题：状态树的搜索算法。一个静止状态结合不同的倒水动作会迁移到不同的状态，所有状态转换所展示的就是一棵以状态[8, 0, 0]为根的状态搜索树，图（2）画出了这个状态搜索树的一部分，其中一个用不同颜色标识出来的状态转换过程（状态树的一个分支）就是本问题的一个解：

图2状态树一部分的展示

状态树的搜索就是对整个状态树进行遍历，这中间其实暗含了状态的生成，因为状态树一开始并不完整，只有一个初始状态的根节点，当搜索（也就是遍历）操作完成时，状态树才完整。树的遍历可以采用广度优先遍历算法，也可以采用深度优先遍历算法，就本题而言，要求解所有可能的等分水的方法，暗含了要记录从初始状态到最终状态，所以更适合使用深度优先遍历算法。状态树的遍历暗含了一个状态生成的过程，就是促使状态树上的一个状态向下一个状态转换的驱动过程，这是一个很重要的部分，如果不能正确地驱动状态变化，就不能实现状态树的遍历（搜索）。

建立状态模型一节中提到的动作模型，就是驱动状态变化的关键因子。对一个状态来说，它能转换到哪些新状态，取决于它能应用哪些倒水动作，一个倒水动作能够在原状态的基础上“生成”一个新状态，不同的倒水动作可以“生成”不同的新状态。由此可知，状态树遍历的关键是找到三个水桶之间所有合法的倒水动作，用这些倒水动作分别“生成”各自相应的新状态。遍历三个水桶的所有可能动作，就是对三个水桶任取两个进行全排列（常用的排列组合算法可以参考《排列组合算法》一文），共有6种水桶的排列组合，也就是说有6种可能的倒水动作。将这6种倒水动作依次应用到当前状态，就可以“生成”6种新状态，从而驱动状态发生变化（有些排列并不能组合出合法的倒水动作，关于这一点后面“算法优化”部分会介绍）。

算法优化和避免状态循环

从图（2）可以看出来，对于三个水桶这样小规模的题目，其整个状态树的规模也是相当大的，更何况是复杂一点的情况，因此类似本文这样对搜索整个状态树求解问题的算法都不得不面对一个算法效率的问题，必须要考虑如何进行优化，减少一些明显不必要的搜索，加快求解的过程。

前文讲过，状态搜索的核心是对三个水桶进行两两排列组合得到6种倒水动作，但是并不是每种倒水动作都是合法的，比如，需要倒出水的桶中没有水的情况和需要倒进水的桶中已经满的情况下，都组合不出合法的倒水动作。除此之外，因为水桶是没有刻度的，因此倒水动作也是受限制的，也就是说合法的倒水动作只能有两种结果：需要倒出水的桶被倒空和需要倒进水的桶被倒满。加上这些限制之后，每次组合其实只有少数倒水动作是合法的，可以驱动当前的状态到下一个状态。利用这一点，就可以对状态树进行“剪枝”，避免对无效（非法）的状态分支进行搜索。

除了通过“剪枝”提高算法效率，对于深度优先的状态搜索还需要防止因状态的循环生成造成深度优先搜索无法终止的问题。状态的循环生成有两种表现形式：一种是在两个桶之间互相倒水；另一种就是图（2）中展示的一个例子，[3, 5, 0] -> [3, 2, 3] -> [6, 2, 0] -> [3, 5, 0]形成一个状态环。要避免出现状态环，就需要记录一次深度遍历过程中所有已经搜索过的状态，形成一个当前搜索已经处理过的状态表，每当生成一个新状态，就先检查是否是状态表中已经存在的状态，如果是则放弃这个状态，回溯到上一步继续搜索。如果新状态是状态表中没有的状态，则将新状态加入到状态表，然后从新状态开始继续深度优先遍历。在这个过程中因重复出现被放弃的状态，可以理解为另一种形式的“剪枝”，可以使一次深度优先遍历很快收敛到初始状态。

算法实现

解决了算法的三个关键点后，剩下的问题就是写出算法了。先看看“剪枝”的实现：

正如前文分析的那样，当需要倒出的水桶是空的或需要倒入的水桶已满时，from->to就不是合法的倒水动作，当然，任何一个水桶也不能向自身倒水，这个是常识，但是计算机不知道，所以 (from != to) 就是告诉它这样不行。

 在状态搜索的过程中需要维护一张已经搜索过的状态列表，算法实现采用STL::Deque来组织这个列表。因为搜索算法的关系，这个列表中的状态是有顺序的，并且每个状态数据内部都记录有这个状态对应的倒水动作，所以遍历这个列表就可以知道当前状态是从初始状态经过怎样的一个倒水过程。如果当前状态就是结果状态，就可以根据这个列表输出整个倒水动作序列。PrintResult()函数输出整个倒水动作序列的：

PrintStates()函数是BucketState的成员函数，负责打印一个状态自身，包括当前桶中水的状态以及倒水动作：

IsProcessedState()函数判断一个状态是否是状态列表中已经存在状态，利用STL库的便利，这个函数的实现也很简单：

实现了“剪枝”判断函数，又知道了状态列表是以什么形式组织的，剩下的工作就是完成状态树的搜索了。状态树的搜索是一个递归的过程：从初始状态开始，由第一个合法的倒水动作得到一个新的状态，记录这个状态，并从这个新状态开始遍历穷举，穷举完成后（无论是否得到结果），取消这个状态，然后从下一个合法的倒水动作再得到一个新状态，然后从这个状态开始遍历穷举，直到遍历完所有合法的倒水动作。

状态搜索的结束条件是什么？算法的广度搜索结束条件是遍历完所有的合法倒水动作，深度搜索的结束条件有两个：一个是得到最终状态（成功的情况），另一个是从某个状态开始所有合法倒水动作得到的新状态都和与已经遍历过的状态列表中的状态重复（失败的情况）。

SearchState()函数就是状态搜索算法的核心，这个函数首先检查当前状态列表的最后一个状态是否是结果需要的最终状态（[4, 4, 0]），如果是最终状态，就表示搜索到一个结果，通过PrintResult()函数遍历状态列表，输出当前结果状态转换的整个过程（倒水动作序列）。如果当前状态不是最终状态，就通过一个两重循环遍历6种可能的倒水动作。

SearchStateOnAction()函数对每种可能的倒水动作检查是否是合法，如果是合法动作就生成一个新的状态，如果这个状态是状态列表中不存在的新状态，则将之加入到状态列表，然后递归地调用SearchState()函数继续对新状态进行深度优先搜索。

SearchStateOnAction()函数的实现如下：

SearchStateOnAction()函数调用了一个很有意思的函数：DumpWater()。DumpWater()函数的主要作用是模拟一次倒水动作，确定能够从from桶中倒多少水到to桶，从而得到一个完整的动作三元组并根据这个动作从current状态生成新的状态next。从from桶向to桶倒水只能有两种情况，一种是from的水被倒空（to桶可能满，也可能不满），另一种是to桶被装满（from桶可能还剩一些水，也可能被倒空），这两个约束在DumpWater()函数中得到了体现：

至此，整个算法就完成了，到底有多少种答案呢？结果是16个答案。我曾经手推过一个倒水的状态转换图，得到了6种结果，看来还是机器更严谨一些。最后，给出算法得到的全部16种答案的倒水过程：

 

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• 通俗易懂--决策树算法、随机森林算法讲解(算法+案例)
• 限流算法之漏桶算法、令牌桶算法
• 什么是Paxos算法？Paxos算法是区块链核心算法之一
• 一文读懂对称加密算法、非对称加密算法和Hash算法
• 算法(六):图解贪婪算法
• 算法篇03：排序算法

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。