回溯法解决喝酒问题
先介绍一下回溯法的理论：
可用回溯法解决的问题P，通常能够表达为：
对于已知的、由n元组(x1,x2,……，xn)组成的一个状态空间 E={(x1,x2,……，xn) | xi ∈Si, i=1,2,..,n}，给定关于n元组中的分量的一个约束集D，要求E中满足D的全部约束的所有n元组。其中Si是分量xi的定义域且|Si|有限，i=1,2,...n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。
对于n元组(x1,x2,……，xn)中分量的约束，一般分为两类，一类是显约束，它给出对于n元组中分量的显式限制，比如当i≠j时xi≠xj；另一类是隐约束，它给出对于n元组中分量的隐式限制，比如：f(x1,x2,……，xn)≠ 0，其中f是隐函数。不过隐式显式并不绝对，两者可以相互转换。
解问题P的最朴素的方法是穷举法，即对E中的所有n元组，逐一地检测其是否满足D的全部约束。全部满足，才是问题p的解;只要有一个不满足，就不是问题P的解。显然，如果记m(i)=|S(i+1)|,i=0,1,...n-1，那么，穷举法需要对m=m(0)*m(1)*...*m(n-1)个n元组一个不漏地加以检测。可想而知，其计算量是非常之大的。
我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组(x1,x2,……，xi)满足D中仅涉及到x1,x2,……，xi的所有约束意味着j(j<i)元组(x1,x2,……，xj)一定也满足D中仅涉及到x1,x2,……，xj的所有约束，i=1,2,……,n。换句话说，只要存在O≤j≤n-1，使得(x1,x2,……，xj)违反D中仅涉及到x1,x2,……，xj的约束之一，以(x1,x2,……，xj)为前缀的任何n元组(x1,x2,……,xj,……,xn)一定也违反D中仅涉及到又x1,x2,……，xi的一个约束，其中n≥i≥j。
这个发现告诉我们，对于约束集D具有完备性的问题P，一旦检测断定某个j元组(x1,x2,……,xj)违反D中仅涉及x1,x2,……,xj的一个约束，就可以肯定，以(x1,x2,……,xj)为前缀的任何n元组(x1,x2,……,xj,……,xn)都不会是问题的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比穷举法效率高得多的算法。
回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树。它可这样构造：设Si中的元素可排成x(i,1),x(i,2),……,x(i,m(i-1)),i=1,2,……,n。从根开始，让T的第i层的每一个结点都有m(i)个儿子。这m(i)个儿子到它们的共同父亲的边，按从左到右的次序分别带权x(i+1,1),x(i+1,2),……,x(i+1,m(i)),i=0,1,2,……,n-1。照这种构造方式，E中的一个n元组(x1,x2,……，xn)对应于T中的一个叶结点，T的根到这个叶结点的路上依次的n条边分别以x1,x2,……，xn为其权，反之亦然。另外，对于任意的0≤i≤n-1，E中n元组(x1,x2,……，xn)的一个前缀i元组(x1,x2,……，xi)对应于T中的一个非叶结点，T的根到这个非叶结点的路上依次的i条边分别以了x1,x2,……，xi为其权，反之亦然。特别，E中的任意一个n元组的空前缀()，对应于T的根。
因而，在E中寻找问题P的一个解等价于在T中搜索一个叶结点，要求从T的根到该叶结点的路上依次的n条边相应带的n个权x1,x2,……，xn满足约束集D的全部约束。在T中搜索所要求的叶结点，很自然的一种方式是从根出发逐步深入，让路逐步延伸，即依次搜索满足约柬条件的前缀1元组(xl)，前缀2元组(xl,x2)，前缀i元组(x1,x2,……，xi)，……，直到i=n为止。注意，在这里，我们把(x1,x2,……，xi)应该满足的D中仅涉及x1,x2,……，xi的所有约束当做判断(x1,x2,……，xi)是问题p的解的必要条件，只有当这个必要条件加上条件i=n才是充要条件。为了区别，我们称使积累的判别条件成为充要条件的那个条件(如条件i=n)为终结条件。
在回溯法中，上面引入的树T被称为问题P的状态空间树;树T上的任意一个结点被称为问题p的状态结点;树T上的任意一个叶结点被称为问题P的一个解状态结点;树T上满足约束集D的全部约柬的任意一个叶结点被称为问题P的一个回答状态结点，简称为回答结点或回答状态，它对应于问题P的一个解。
例如8皇后问题，就是要确定一个8元组（x1,x2,..,x8)，xi表示第i行的皇后所在的列，这样的问题很容易应用上面的搜索树模型；然而，有些问题的解无法表示成一个n元组，因为事先无法确定这个n是多少，比如这个喝酒问题，问题的解就是一系列的倒酒喝酒策略，但是事先无法确定究竟需要进行多少步；还有著名的8数码问题（文曲星上的那个9x9方格中移数字的游戏），那个问题也是预先不知道需要移动多少步才能达到目标。不过这并不影响回溯法的使用，只要该问题有解，一定可以将解用有限的变元来表示，我们可以假设n就是问题的一个解的变元的个数，这样就可以继续利用上面的搜索树模型了。事实上，这棵搜索树并非预先生成的，而是在搜索的过程中逐步生成的，所以不知道树的深度n并不影响在树中搜索叶子节点。但是有一点很重要，如果问题根本不存在有限的解，或者问题的状态空间无穷大，那么沿着某条道路从根出发搜索叶节点，可能永远无法达到叶结点，因为搜索树会不断地扩展，然而叶结点也许是确实存在的，只要换一条道路就可以找到，只不过一开始就走错了路，而这条错路是永远无法终止的。为了避免这种情况我们一般都规定状态空间是有限的，这样即使搜索整个状态空间的每个状态也可以在有限时间内完成，否则的话回溯法很可能不适用。
搜索树的每一个节点表示一个状态，节点i要生成节点j必须满足约束集D中的约束条件，我们也可以将这个约束条件称为“状态转移规则”或者“产生规则”（意指从节点i产生节点j的规则，这是从“产生式系统”理论的角度来解释回溯法）。因此回溯法的实质是在一个状态空间中，从起始状态（搜索树的根）搜索到一条到达目标状态（搜索树的叶结点）的路径（就和走迷宫差不多，这是从图论的角度来解释回溯法）。一般来说，为了防止搜索的过程中出现回路，必须记录已经走过的节点（状态），在同一条路径中不能重复走过的节点（状态），这样只要状态空间是有限的，回溯法总是可以终止的。
===========================================================================================
下面我们就根据回溯法来解决这个喝酒问题
（1）状态的表示一个状态用一个7元组表示 X=（x1,x2,x3,x4,x5,x6,x7)；，其中x1~x3分别表示a,b,c三个酒瓶中的酒，x4~x7分别表示A,B,C，D四个人已经喝的酒；
（2）约束条件1。每个人喝的酒不能超过4两； 2。每个瓶中容纳的酒不能超过该瓶的容量； 为了方便设第k个人喝的酒不超过C[k], 第i个酒瓶的容量为C[i]， 则C[1]=C[2]=8, C[3]=3, C[4]=C[5]=C[6]=C[7]=4;约束条件为 0<= X[i] <= C[i];
（3）状态的转移规则（状态产生规则）从某个状态X转移到另一个状态Y有以下几种情况：1。i瓶中的酒倒入j瓶中，并将j瓶装满: Y[i] = X[i] - (C[j]-X[j]) , Y[j] = C[j], i,j∈[1,3]2。i瓶中的酒倒入j瓶中，并将i瓶倒空: Y[i] = 0 , Y[j] = X[j] + X[i] , i,j∈[1,3] 3。某个人j喝光了i瓶中的酒: Y[i] = 0; Y[j] = X[j] + X[i], i∈[1,3], j∈[4,7]当然状态Y必须满足（2）中的约束条件；
（4）初始状态a,b两个瓶中装满酒，c中为空： X0[1]=C[1], X0[2]=C[2], X0[3]=C[3], X0[4]=X0[5]=X0[6]=X0[7]=0；
（5）目标状态所有的瓶中的酒为空，每个人都喝饱了酒： Xn[1]=Xn[2]=Xn[3]=0 , Xn[4]=C[4]， Xn[5]=C[5]， Xn[6]=C[6]， Xn[7]=C[7];
下面给出一个通用的回溯法伪代码：
void DFS_TRY( s ){ if (状态s是目标状态) { 打印结果； 退出； // 如果要求输出所有的解，这里退出函数，如果只要求输出一组解，这里退出整个程序 } for 从状态s根据产生规则产生的每个状态t if (t不在堆栈中) { 状态t压入堆栈； DFS_TRY(t); 状态t弹出堆栈； }}
主程序为：
初始状态s0压入堆栈；DFS_TRY(s0);
然而，对于这个问题，如果单纯地用上面的回溯法解决效率非常的低，几乎无法忍受。所以要改进一下。我们注意到每个状态是一个7元组，而且根据约束条件，所有的合法的状态的个数是8*8*3*4*4*4*4 =49152个，完全可以将所有的状态记录下来，即使穷举所有的状态也是可以忍受的。所以在上面的DFS_TRY中，我们不是在堆栈中寻找已经搜索过的状态，而是在一个状态表中找已经搜索过的状态，如果某个状态在状态表中的标志表明该状态已经搜索过了，就没有必要再搜索一遍。比如，单纯的回溯法搜索出来的搜索树如下所示：
a / \ / \ b c \ / \ / d / \ / \
从a出发，搜索 a - b - d - ... 然后回溯到a, 又搜索到 a - c - d - ..., 因为d在搜索的路径上并没有重复，所以在堆栈中是发现不了d节点被重复搜索的，这样就重复搜索了d和它的子树；如果用一个表格纪录每个节点是否被搜索过了，这样搜索 a - b - d - ...回溯到a, 又搜索到 a - c - d ，这时候查表发现d已经搜索过了，就可以不用再搜索d和它的子树了。
这种用一个表格来记录状态的搜索策略叫做“备忘录法”，是动态规划的一种变形，关于动态规划和备忘录法，请参见:http://algorithm.myrice.com/algorithm/technique/dynamic_programming/index.htm
备忘录法的伪代码：
bool Memoire_TRY( s ){ if (状态s是目标状态) { 记录状态s； return true; // 这里假设只要求输出一组解 } for 从状态s根据产生规则产生的每个状态t if (状态t没有被搜索过) { // 注意这里的改变 标记状态t被访问过； if (DFS_TRY(t)) { 记录状态s； return true; } } return false;}
主程序为：
初始化设置状态表中的所有状态未被访问过初始状态设为s0；if (Memoire_TRY(s0)) 打印记录下来的解;
这样就不需要自己设置堆栈了，但是需要维护一个状态访问表。
下面是按照这种思路写的程序，注意，求出来的不是最优解，但是很容易修改该程序求出最优解。
#include <iostream.h>#include <string.h>
const int CUP_COUNT = 3; // 酒杯的数目const int STATE_COUNT = 7; // 状态变量的维数typedef int State[STATE_COUNT]; // 记录状态的类型const State CONSTR = {8, 8, 3, 4, 4, 4, 4}; // 约束条件const State START = {8, 8, 0, 0, 0, 0, 0}; // 初始状态const State GOAL = {0, 0, 0, 4, 4, 4, 4}; // 目标状态const int MAX_STATE_COUNT = 10*10*10*10*10*10*10; //态空间的状态数目const MAX_STEP = 50; // 假设最多需要50步就可以找到目标
const State key = {3, 5, 3, 3, 2, 0, 0};
bool visited[MAX_STATE_COUNT]; // 用来标记访问过的状态
State result[MAX_STEP]; // 记录结果；int step_count = 0; // 达到目标所用的步数
// 计算状态s在状态表中的位置int pos(const State &s){ int p = 0; for (int i=0; i<STATE_COUNT; i++) { p = p*10 + s[i]; } return p;}
// 判断状态a,b是否相等bool equal(const State &a, const State &b) { for (int i=0; i<STATE_COUNT; i++) if (a[i]!=b[i]) return false; return true;}
void printState(const State &s) { for (int i=0; i<STATE_COUNT; i++) cout << s[i] << " "; cout << endl;}
// 备忘录法搜索bool Memoire_TRY(const State &s, int step){ if (memcmp(s,GOAL,sizeof(s))==0) { // 如果是目标状态 step_count = step; memcpy(result[step-1],s, sizeof(s)); // 记录状态s return true; } int i, j;
// 第一种规则，第i个人喝光杯子j中的酒 for (i=CUP_COUNT; i<STATE_COUNT; i++) if (s[i] < CONSTR[i]) // 如果第i个人还可以喝 for (j=0; j<CUP_COUNT; j++) if (s[j]>0 && s[i] + s[j] <= CONSTR[i]) { // 如果第i个人可以喝光第j杯中的酒 State t; memcpy(t, s, sizeof(s)); t[i] += t[j]; // 第i个人喝光第j杯的酒 t[j] = 0; int tmp = pos(t); if (!visited[pos(t)]) { // 如果状态t没有访问过 visited[pos(t)] =true; // 标记状态t访问过了 if (Memoire_TRY(t, step+1)) { // 从状态t出发搜索 memcpy(result[step-1],s, sizeof(s)); // 记录状态s return true; } // end of if (Memoire_TRY(t, step+1)) } // end of if (!visited[pos(t)]) } // end of if (s[i] + s[j] <= CONSTR[i])
// 第二种规则，将杯子i中的酒倒入到杯子j中去 for (i=0; i<CUP_COUNT; i++) for (j=0; j<CUP_COUNT; j++) if (i != j) { int k = (CONSTR[j] - s[j] < s[i] ? CONSTR[j] - s[j] : s[i] ); // 计算出可以从i中倒入j中的酒的数量 if (k > 0) { // 如果可以倒 State t; // 生成新的状态t memcpy(t, s, sizeof(s)); t[i] -= k; t[j] += k; int tmp = pos(t); if (!visited[pos(t)]) { // 如果状态t没有访问过 visited[pos(t)] =true; // 标记状态t访问过了 if (Memoire_TRY(t, step+1)) { // 从状态t出发搜索 memcpy(result[step-1],s, sizeof(s)); // 记录状态s return true; } // end of if (Memoire_TRY(t, step+1)) } // end of if (!visited[pos(t)]) } // end of if (k > 0) } // end of if (i != j)
return false;} // end of Memoire_TRY
void main(){ memset(visited, false, sizeof(visited)); if (Memoire_TRY(START,1)) { cout << "find a solution: " << endl; for (int i=0; i<step_count; i++) { for (int j=0; j<STATE_COUNT; j++) cout << result[i][j] << " "; cout << endl; } } else cout << "no solution." << endl;}
|
[【技术文档】]回溯法解决喝酒问题（starfish）