自学BFS笔记-POJ3414 Pots 双桶取水问题

        在搜素算法当中，广度优先搜索BFS（Breadth First Search）大概是最简单、暴力的一种搜索算法，本文将以POJ3414题为例，作为典型记录一下单纯的BFS题可能遇到的情况（多接口和记录路径），下面先放题目：

你有有两个罐子，分别是A升和B升的体积。可以执行以下操作:
    FILL(i)从水龙头中填充罐i(1≤i≤2);
    DROP(i)罐i排空到排水管;
    POUR(i,j)从罐i倒到罐j;在这个操作之后，要么罐子j是满的(而且罐子i可能还有一些水)，要么罐子i是空的(它的所有内容都被移动到罐子j)。

        编写一个程序，找出这些操作的最短可能序列，使其中一个罐子恰好产生C升的水。
Input:
第一行也是唯一一行是数字A、B、C。这些都是1 ~ 100之间的整数，且C≤max(A、B)。
Output:
输出的第一行必须包含操作序列K的长度，接下来的K行必须描述一个操作。如果有几
个最小长度的序列，输出其中任何一个。如果无法达到预期的结果，文件的第一行也
是唯一一行必须包含单词“impossible”。

Sample Input
3 5 4
Sample Output
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1) 

        先分析题目，本题是很经典的BFS题，主要有以下特征：明确的起点状态（A,B都空）和终点状态（其中一个中的水量＝C），有限个值位移方向（FILL,DROP和POUR），以及明确的边界条件（两个桶的容积），同时要求找到最优解（步骤最短）。

        本题需要储存状态（两个水桶当前的水量），这个状态本身就是多接口的（有两个桶），随后需要记录步骤，本文重在解释BFS记录步骤的思路（类单链表）。先解释一下本题需要的接口。

        首先，在BFS中，每一个父结点会根据值位移函数提供的方向派生出多个子结点，例如在本题中，值位移函数事实上提供了6个状态改变方向（Fill(i),Fill(j),Drop(i),Drop(j),Pour(i,j),Pour(j,i)）因此每一个父结点（前一状态）会派生出6个子节点（后一状态），简化这个问题，即1会派生出234567，而A会派生出BCDEFG，我们只需要给它们每一个结点一个独一无二的标识符（下标），同时在子结点中储存父结点的下标，这样我们就可以根据最终状态一路追踪到最早的父结点，这里的思想有点类似于“并查集”，但笔者做此题时还未接触并查集的概念，因此用单链表作比喻。下面给出值位移函数和接口：

        状态和操作链（BFS单位元）：

class pot{		//BFS*-对于多入口的复杂BFS，需要类/结构体来储存入口 
	public:
		int x , y;	//当前两个瓶子的剩余水量(状态) 
		int pos;		//记录当前状态在操作链p中的下标
		int step;		//当前步数 		 
};
class process{		//操作链
	public:
		int pre;		//记录上一个操纵的下标 
		string op;		//记录操作 
};

        值位移函数：

void Fill(int i){
	switch(i){
		case 1:	k1 = v1;	return;
		case 2: k2 = v2;	return;
	}
} 
void Drop(int i){
	switch(i){
		case 1: k1 = 0;		return;
		case 2: k2 = 0;		return;
	}
}
void Pour(int i, int j){
	switch(i){
		case 1:if(k1+k2<=v2){
				    k2 += k1;	
				    k1 = 0;	
			   }
			   else{
			   		k1 = k1+k2-v2;
			   		k2 = v2;
			   }return;
		case 2:if(k2+k1<=v1){
				    k1 += k2;	
					k2 = 0; 	
			   }
			   else{
			   		k2 = k1+k2-v1;
			   		k1 = v1;
			   }return;
	}
}
string dev(int k, int i, int j){
	switch(k){
		case 0: Fill(i);	return "Fill(1)";
		case 1: Fill(j);	return "Fill(2)";
		case 2: Drop(i);	return "Drop(1)";
		case 3: Drop(j);	return "Drop(2)";
		case 4: Pour(i,j);	return "Pour(1,2)";
		case 5: Pour(j,i);	return "Pour(2,1)";
	}
}

        对于BFS，一个很重要的模块是“标记访问”，标记访问过的状态，避免被后来的访问覆盖状态，由于不同题目的状态是五花八门的，但字符串基本可以解决大部分问题，所以常用map来标记访问，在本题中，将剩余水量a，b组成字符串来标记访问，首先给出组合函数：

string combAB(int a,int b)	//把整数a、b整合为 "a,b"  的字符串形式(不包括引号)，用于标记状态
{
	string s;
	{	ostringstream oss;
		oss<

        由于完成BFS后，对步骤的追述是倒序的，而最后输出需要正序输出，用栈stack可以简单地解决这个问题。

        最后放出源码：

#include
using namespace std;
int v1 , v2;		//瓶子容量
int c;		//目标水量
int k1 , k2;		//瓶子内含水量
 
class pot{		//BFS*-对于多入口的复杂BFS，需要类/结构体来储存入口 
	public:
		int x , y;	//当前两个瓶子的剩余水量(状态) 
		int pos;		//记录当前状态在操作链p中的下标
		int step;		//当前步数 		 
};
class process{		//记录操作链 
	public:
		int pre;		//记录上一个操纵的下标 
		string op;		//记录操作 
};
string combAB(int a,int b)	//把整数a、b整合为 "a,b"  的字符串形式(不包括引号)，用于标记状态
{
	string s;
	{	ostringstream oss;
		oss< q;		//BFS-核心队列  
	put head , next;
	process p[1000];
	map vis;		//BFS-访问标记
	head.x = 0;
	head.y = 0;
	head.pos = 0;
	q.push(head);
	int ptr = 0;		//记录操作下标： 
	while(!q.empty()){
		head = q.front();
		q.pop();
		for(int k=0;k<6;k++){
			k1 = head.x;
		    k2 = head.y;             
			string st = dev(k,1,2);			//临时储存操作 
			string str = combAB(k1,k2);
			if(vis[str])	continue;
			next.pos = ptr++;
			p[next.pos].pre = head.pos;
			p[next.pos].op = st;		//未被跳过，入列 
			next.x = k1;
			next.y = k2;
			next.step = head.step + 1;
			vis[str] = true;
			q.push(next);
			if(next.x==c || next.y==c){
				cout< s;		//用栈完成倒序输出 
				int k = next.pos;
				for(int i=0;i>v1>>v2>>c;
	BFS();
} 

        本篇博客写得比较草率，因为BFS是相对入门的搜索技术，只需要掌握以下要点：

        1、构建合适的核心队列queue，队列的类型应该和单位元一致。

        2、BFS需要访问标记，避免丢失最优解。

        3、确立值位移函数，它决定了子节点的个数。

        4，确立边界，越界的子节点是不被允许的。