用三个水桶等分 8 升水的问题(转自gitchat王晓华的达人课)

--write by zhuwx 2019-06-24 20:58:16 +0800 CST

点击量:12

有这样一个智力题目:有三个分别是 3 升、5 升和 8 升容积的水桶,其中容积为 8 升的水桶中装满了水,容积为 3 升和容积为 5 升的水桶是空的,三个水桶都没有体积刻度。现在需要把大水桶中的 8 升水等分成两份,每份都是 4 升水,附加条件是只能使用这 8 升水和另外两个空水桶,不能借助其他容器或更多的水。

问题分析

好莱坞电影《虎胆龙威 3》中,布鲁斯·威利斯饰演的纽约警探约翰·麦克莱恩被恐怖分子点名挑战,让他在指定的时间内完成各种危险指令,否则就威胁炸掉整个纽约市。其中有一个情节就是在一个街心喷泉的边上放了一个容积为 3 加仑的水桶和一个容积为 5 加仑的水桶,让约翰在指定的时间倒腾出来 4 加仑的水,用 4 加仑的水的重量解除炸弹。我们的英雄曾一阵手忙脚乱,不过最终解决了问题。电影中的问题与本课的问题稍有差别,电影中只有两个水桶,但是水可以无限使用。我们的题目有三个水桶,但是只能用 8 升水,不能用额外的水,当然也不能将水洒出来。

这个问题其实并不难,大部分人都可以在一分钟内给出答案,并且这个问题的答案也不止一个。最快的倒水操作如下所示,共需要 7 次倒水动作:

(1)从 8 升水桶中倒 5 升水到 5 升水桶中

(2)从 5 升水桶中倒 3 升水到 3 升水桶中

(3)从 3 升水桶中倒 3 升水到 8 升水桶中

(4)从 5 升水桶中倒 2 升水到 3 升水桶中

(5)从 8 升水桶中倒 5 升水到 5 升水桶中

(6)从 5 升水桶中倒 1 升水到 3 升水桶中

(7)从 3 升水桶中倒 3 升水到 8 升水桶中

那么问题来了,这个题目到底有多少种倒水的方法呢?水从水桶之间倒来倒去,情况太多了,一般人很难记得住这么多倒水动作的序列,但是计算机可以。这不是一个典型意义上的求解最优解的问题,虽然可能暗含了求解倒水次数最少的方法的要求,但就本质而言,常用的求解最优解问题的高效的方法都不适用于此问题。既然这个系列我们都在讲穷举法,这一课我们也用穷举法找出所有正确的倒水动作序列,我们不关心什么方法最快,当然,只要稍加改造,增加最短动作步骤数的判断,我们的算法还能找出最快的倒水动作序列。

算法设计思路

《算法的乐趣》这本书中我们介绍过这个题目,但是偏重于对算法实现代码的解释,很多网友虽然理解了算法实现,但是还是不明白为什么要这么实现。在这里,我们再次讲解这个题目,重点放在算法设计实现的过程,而不是对实现后的算法代码进行解释。

既然要使用穷举法,首先来回忆一下使用穷举法设计算法的两个步骤:

  • 确定问题的解(或状态)的定义,解空间的范围以及正确解的判定条件;
  • 根据解空间的特点选择搜索策略,逐个检验解空间中的候选解是否正确,必要时可辅助一些剪枝算法,排除一些明显不可能是正确解的检验过程,提高穷举的效率。

接下来我们就从这两个步骤入手来介绍如何设计这个穷举算法。

定义问题的状态

穷举法的关键是要确定解空间的范围和模式,然后才能确定以何种方法对解空间进行遍历。要确定解空间,首先要定义问题的解。虽然这个题目的要求是给出一组倒水动作的序列,这个动作序列最终能将 8 升水平分成两个 4 升水的状态,但是单纯考虑对动作的穷举是没有意义的,因为动作需要附加在某个状态上时才能产生结果。现在换个思路,如果把某一时刻三个水桶中的水量视为一个状态,将倒水动作的变化转化为三个水桶中水的状态的变化,则问题迎刃而解。问题的解空间就是水桶状态的全部集合,正确解的判定条件就是容量为 8 升的水桶和容量为 5 升的水桶中各有 4 升水。如果用一个三元组(或是三维向量)分别表示 8 升、5 升和 3 升水桶中的水量,则问题的初始状态就是 [8,0,0],问题的解决状态就是 [4,4,0]。

求解这个问题的算法本质上就是对状态的穷举搜索,这样的状态变化搜索的结果通常是得到一棵状态搜索树,根节点是初始状态,叶子节点可能是最终状态,也可能是某个无法转换到最终状态的中间状态,状态树有多少个最终状态的叶子节点,就有多少种答案。由此可知,解决本问题的算法关键是建立状态和动作的数据模型,并找到一种持续驱动动作产生的搜索方法。

状态树和解空间

倒水动作与静止状态的结合就产生了状态变化,持续的状态变化就产生了一棵状态树,这个状态树上的所有状态就构成了穷举算法的解空间。以初始状态 [8,0,0] 为例,如果与“1号桶倒 5 升水到 2 号桶”动作相结合,就得到了一个新状态 [3,5,0],同样,如果与“1号桶倒 3 升水到 3 号桶”动作相结合,就得到了另一个新状态 [5,0,3]。以此类推,将动作与状态枚举组合后,可以得到如图(1)所示的状态树。

avatar

图(1)倒水问题的状态树

[8,0,0] 是状态树的根,图(1)只画出了这棵状态树的一部分,图中深颜色背景标识出的几个状态是状态树的一个分支,也是一个正确的解的状态转换路径。根据题目的意图,最终的结果是要输出这条转换路径的倒水过程,实际上就是与状态转换路径相对应的动作路径,或动作列表(图(1)中蓝色文字描述的倒水动作序列)。当定义了动作的数学模型后,就可以根据状态图中状态转换路径找到对应的动作列表,依次输出这个路径上每个状态对应的动作就可以得到一个完整的倒水过程。

状态的数据模型

虽然我们定义的状态只有桶中的水量,但是考虑到桶中的水在变化的过程中,需要由桶的容积来确保状态的有效性(比如不能向一个 3 升的水桶倒 4 升水),所以在设计数据结构时,我们以桶为单位,把容积和水量一起考虑,桶的数据模型如下:

class Bucket
{
    ......
    int m_water;  //当前水量
    int m_capicity;  //桶的容积
};

表示三个水桶的三维向量用数组表示,std::vector<...> 是 C++ 的数组,其类型就是前面定义的 Bucket。水的状态就是桶的状态:

class BucketsState
{
......
    std::vector<Bucket> m_buckets;  //桶的向量
    ACTION m_curAction;  //当前状态对应的动作
};

m_curAction 是当前状态绑定的倒水动作,即前一个状态通过这个倒水动作演变成当前状态,它并不是状态穷举过程中的关键属性,记录这个状态对应的倒水动作的目的是为了能够在输出结果时,除了输出三个水桶的状态变化序列,还能够输出对应的倒水动作,使结果输出更有意思一点儿。

倒水动作的数据模型

两个静态的水桶状态(BucketsState)是通过倒水动作建立关联的。这里说的倒水动作必须是合法的倒水动作,因为水桶是没有体积刻度的,因此倒水动作也就不能是任意倒水行为,一个倒水动作合法的前提条件是源水的桶中有水且目的水桶中还有空间。分析一下,实际上就两种情况:一种是目的水桶中的空间足够大,则源水桶中的水全部加到目的水桶中,此时源水桶成为空桶(水量变成 0);另一种情况就是目的水桶中的空间不够大,只能倒入一部分水,此时源水桶中还剩有一部分水。

一个合法的倒水动作包含三个要素:源水桶编号、目的水桶的编号和倒水的量(体积)。我们用一个三元组来描述倒水动作:{from, to, water},from 是指源水桶的编号,to 是指目的水桶的编号,water 是此次倒水动作所倒的水量。倒水动作的数据结构定义如下:

typedef struct
{
    int from;
    int to;
    int water;
}ACTION;

某一时刻三个水桶的状态,经过某个倒水动作后演变到一个新的状态,这是状态变化的过程。根据 BucketsState 的定义,每当穷举遍历得到一个结果状态时,演变过程中的一些列状态和对应的倒水动作如图(2)所示:

enter image description here

图(2)状态演变过程与倒水动作关系图

设计搜索算法

水桶的状态都是静止的,从初始状态到最终状态的变化需要一种“推动力”,接下来需要找到一种“推动力”推动状态发生变化。这个“推动力”就是隐含在问题描述中的“倒水动作”,每个动作实施的结果就是从一个水桶倒水到另一个水桶,水桶中水的状态就发生变化了,于是状态也就变化了。如果能找到一种方式,持续地促使倒水动作发生,使得状态能不停地随动作变化,那就等于找到了本问题的解空间搜索方法。

由图(1)所示,本问题的解空间是一棵状态树,因此遍历搜索的算法就是树的遍历算法(在之前介绍的例子中,Google 方程式的遍历是线性空间的遍历)。状态树最初只有一个根节点,整棵树的展开是随着搜索算法逐步展开的。对于树状结构的搜索,可以采用深度优先搜索(DFS)算法,也可以采用广度优先搜索(BFS)算法,两种方法各有优缺点,广度优先搜索的优点是不会因为状态的重复出现而导致搜索时出现状态环路,缺点是需要比较多的存储空间记录中间状态。深度优先搜索的优点是在同一时间只需要存储从根节点到当前搜索状态节点这一条路径上的状态节点,需要的存储空间比较小,缺点是对搜索过程中因出现重复状态导致的状态环路要做特殊处理,避免因状态搜索时出现死循环的情况。

状态树的搜索就是对整个状态树进行遍历,这中间其实暗含了状态的生成,因为状态树一开始并不完整,只有一个初始状态的根节点,当搜索(也就是遍历)操作完成时,状态树才完整。就本题而言,要求解所有可能的等分水的方法,暗含了要记录从初始状态到最终状态,所以更适合使用深度优先遍历算法。

状态树的遍历

状态树的遍历就是促使状态树上的一个状态向下一个状态转换的驱动过程,这是一个很重要的部分,如果不能正确地驱动状态变化,就不能实现这个穷举算法。上面中提到的动作模型,就是驱动状态变化的关键因子。对于一个状态来说,它能转换到哪些新状态,取决于它能应用哪些倒水动作,一个倒水动作能够在原状态的基础上“生成”一个新状态,不同的倒水动作可以“生成”不同的新状态。由此可知,状态树遍历的关键是找到三个水桶之间所有合法的倒水动作,用这些倒水动作分别“生成”各自相应的新状态。

遍历三个水桶的所有可能倒水动作,就是对三个水桶任取两个进行全排列,这种排列的结果可以得到 6 种水桶的排列关系,《算法的乐趣》这本书中给的例子代码就是采用一个两重循环的结构组合出这 6 种倒水动作。实际上,三个水桶就只有 6 个固定的倒水动作,分别是:1→2、1→3、2→1、2→3、3→1 和 3→2,我们可以用一个一维表来存储这 6 个动作,算法处理时直接遍历这个一维表就可以枚举全部倒水动作。这和本课程基础部分介绍的方向遍历的思想类似,是一种一致性处理方法。

std::pair<int, int> 是一个整数对类型,其中 first 属性代表第一个整数,second 属性代表第二个整数,action_table 是由 std::pair<int, int> 类型组成的数组,注意代表水桶编号的数字已经调整为从 0 开始编号。

std::vector<std::pair<int, int>> action_table = { {0, 1},{0, 2},{1, 0},{1, 2},{2, 0},{2, 1} };

for (const auto& act : action_table)
{
    BucketsState next;
    /*从from到to倒水,如果成功,next返回倒水后的状态*/
    if (current.TakeAction(act.first, act.second, next))
    {
        ......
    }
}

剪枝和优化(重复状态判断)

上面提到,采用深度优先搜索状态树,会遇到重复的状态而导致的状态环路。比如,假设某一时刻从 1 号桶倒 3 升水到 3 号桶,下一个时刻又从 3 号桶倒 3 升水到 1 号桶,此时水桶的状态就又回到了之前的状态,这就形成了一个状态环路。有时候状态环路可能复杂一点,几个状态之后才出现重复状态,图(1)就展示了一种复杂一点的状态环路。在状态 [3,5,0]→[3,2,3]→[6,2,0]→[3,5,0] 的转换过程中,[3,5,0] 状态再次出现形成状态环路。如果对这种情况不做处理,状态搜索就会在某个状态树分支陷入死循环,永远无法到达正确的结果状态。除此之外,如果对一个状态树分支上的某个状态经过搜索,其结果已经知道,则在另一个状态树分支上搜索时再遇到这个状态时,可以直接给出结果,或跳过搜索,以便提高搜索算法的效率。在这个过程中因重复出现被放弃或跳过的状态,可以理解为另一种形式的“剪枝”,可以使一次深度优先遍历很快收敛到初始状态,从图(1)可以看出来,这样重复出现的状态还是很普遍的情况。

考虑到上述两种情况,需要对当前深度遍历过程中经过的搜索路径上的所有已经搜索过的状态做一个记录,形成一个当前正在处理的状态序列表。考虑到算法实现过程中,这个表要在其中的一端进行频繁的插入和删除操作,我们用一个 std::deque 来存储当前搜索的状态序列,states 初始化时只有一个初始状态节点:

std::deque<BucketsState> states;
BucketsState init = { { b_capicity[0], b_init[0] },
                      { b_capicity[1], b_init[1] },
                      { b_capicity[2], b_init[2] } };

states.push_back(init); //插入初始状态

每次因为动作组合生成新状态时,都检查一下是否在这个记录中有状态相同的记录,如果存在状态相同的记录则跳过这个新状态,回溯到上一步继续处理下一个状态。如果新状态是状态表中没有的状态,则将新状态加入到状态表,然后从新状态开始继续深度优先遍历。

if (!IsProcessedState(states, next))
{
    states.push_back(next);
    SearchState(states); //从新的位置继续搜索
    states.pop_back();
}  

代码实现

至此,用穷举法设计倒水问题算法的分析全部完成,主要就是围绕穷举法的两个关键点展开的,这也是所有穷举算法设计分析的通用模式。接下来的代码实现不需要过多文字,主要是结合具体代码来理解上述设计的方法是如何实现具体的算法。事实上,如果理解了上述算法分析过程,读者应该能够自己设计出来算法实现,不一定是用 C++,可以是其他编程语言;同样,也不一定用本课例子代码中的方式定义数据结构,读者可以用自己惯用的方式定义数据结构。尽管如此,为了满足很多读者的好奇心,我在这里还是给出主体部分的代码实现。

搜索算法代码

SearchState() 函数实现状态树的搜索遍历,是整个算法的核心。SearchState() 函数每次都是处理 state 队列中最后加入的那个状态(通过 states.back() 得到),将其视为当前状态。对这个当前状态的处理有两部分内容组成:第一部分 IsFinalState() 函数判断当前状态序列中最后一个状态是否就是最终结果状态,如果是就输出一组状态序列(以及对应的倒水动作);如果当前状态序列中最后一个状态不是结果状态,则转入第二部分开始搜索新的状态。搜索新状态的方法是遍历 action_table 表,尝试从 first 指定的水桶向 second 指定的水桶倒水,如果 TakeAction() 返回成功,说明倒水动作成立,可以通过本次倒水动作产生一个新状态(记录在 next 中)。然后对 next 进行检查,判断其是否是 states 队列中已经处理过的状态,如果 states 队列中已经存在这个状态,则不记录这个状态,继续对下一个动作进行尝试。如果 next 是个新状态,则将其加入到 states 队列中,并通过递归调用 SearchState() 函数实现深度优先遍历。

void SearchState(std::deque<BucketsState>& states)
{
    BucketsState current = states.back(); /*每次都从当前状态开始*/
    if(IsFinalState(current)) //判断是否到达[4,4,0]状态
    {
        PrintResult(states); //输出一组结果
        return;
    }
    //遍历倒水动作搜索新的状态
    for (const auto& act : action_table)
    {
        BucketsState next;
        /*从from到to倒水,如果成功,next返回倒水后的状态*/
        if (current.TakeAction(act.first, act.second, next))
        {
            if (!IsProcessedState(states, next)) //新状态next不是重复状态
            {
                states.push_back(next); //新状态next加入队列
                SearchState(states); //从新的位置继续搜索
                states.pop_back(); //新状态next和已经搜索完毕,回溯到上一级
            }
        }
    }
}

倒水动作代码

倒水动作的具体代码实现在 BucketsState::TakeAction() 函数中,这也是一个很有意思的实现细节,能倒水的前提是 from 对应的桶中有水且 to 对应的桶中还有空间。具体能倒多少水由 from 中的水和 to 中的空间共同决定,最后在返回新状态 next 之前,把产生的倒水动作记录到 next 中。

/*从from到to倒水,返回成功,得到新的状态next*/
bool BucketsState::TakeAction(int from, int to, BucketsState& next)
{
    next = *this; //复制当前状态

    Bucket& bfrom = next.GetBucket(from);
    Bucket& bto = next.GetBucket(to);
    if ((bfrom.GetWater() > 0) && !bto.IsFull())
    {
        //能倒的水量由from剩的水量和to剩的空间决定
        int dump_water = (bfrom.GetWater() > bto.GetSpace()) ? bto.GetSpace() : bfrom.GetWater();
        bto.AddWater(dump_water);
        bfrom.DumpWater(dump_water);
        next.SetAction(dump_water, from, to); //记录当前倒水动作(输出结果需要)

        return true;
    }

    return false;
}

总结

总结一下,这一课我们介绍了一种树状空间的穷举搜索方法,这个问题和一般的遍历穷举不同之处在于问题的状态是静态的,需要一个“动作”才能完成状态的转换,产生新的状态。因此遍历算法实际上不是直接对状态进行遍历,而是对“动作”进行遍历,然后将动作与状态叠加,从而产生新的状态。这一课的算法实现有三个重点希望大家可以理解到,第一个重点是通过循环处理 action_table 表实现对动作的遍历,这是个常用的技巧,希望大家掌握(可以对比书中的2重循环代码理解 action_table 表的好处)。第二个重点是状态搜索的主体算法实现 SearchState() 函数,这里用了递归实现方式,利用 C++ 的 std::queue 队列提供的 push() 和 pop() 接口实现了状态的深度优先搜索和回溯(其他编程语言都提供了队列的实现,转换起来并不难理解)。第三个重点是很有意思的倒水动作 TakeAction() 函数,它实现了对倒水过程中出现的两种情况的处理,即能不能倒水、能倒多少水,同时还记录了此次倒水产生的 ACTION。

好了,本课的问题也来了,就是电影中的题目,没有刻度的 3 加仑水桶和 5 加仑水桶各一个,水无限使用,可以随时倒掉,也可以随时装满,请你替约翰找找到底有几种倒腾出 4 升水的方法?