水壶问题的人工智能解法

一、问题

现有8升、5升、3升的容器各一个，均无任何度量标记，其中8升的容器装满啤酒，其他两个为空。要求用上述容器倒来倒去，分成两份4升的啤酒。

二、分析

此问题是个很典型的模型，涉及人工智能搜索策略最简单的实现方法。

用状态空间法，该问题求解的过程为：

（1）定义状态空间。本文用三个有序整数（X，Y，Z）表示三个容器的啤酒量。X表示8升容器的啤酒量，X＝0，……，8；Y表示5升容器的啤酒量，Y＝0，……，5；Z表示3升容器的啤酒量，Z＝0，……，3。初始状态为（8，0，0），它是搜索树的根节点，而目标状态为（4，4，0），我们要做的，就是找出一条或者多条从根节点通往（4，4，0）节点的路径。

（2）确定一组操作。用来求解该问题的算子可以用如下6条规则描述。

①由8升容器向3升容器倒啤酒（注意：要满足前提条件，即８升容器有啤酒、３升容器未满。由于没有刻度，操作的末状态不是将８升容器倒空就是将３升容器倒满，以下规则也一样。）

②由8升容器向5升容器倒啤酒

③由3升容器向8升容器倒啤酒

④由3升容器向5升容器倒啤酒

⑤由5升容器向8升容器倒啤酒

⑥由5升容器向3升容器倒啤酒

这六条规则，事实上就是搜索树上从当前节点生成下一个节点的方法。

（3）选择搜索策略。

根据上面的规则，就可以得到一个搜索策略。但显然，不能无限制的使用，否则，搜索树会趋向于无限的庞大，加入了很多明显可以排除的无用状态，丝毫无益于问题的解决。要限制生成新的状态，首先要明确什么状态是应该保留的，例如图1：

我们可以看到，粗线和虚线显示的两条路径，都出现了循环，显然这除了降低效率之外没有任何用处。因此，对搜索树剪枝的一个基本原则就是：在一条路径上，一个节点只能出现一次。另外，搜索树的深度也不能没有限制，否则会需要过长的时间。

三、实现

程序采用C++实现，在VC++6下编译通过。

搜索树定义如下：

class BeerTree

{

typedef struct _BeerTreeNode

{

long lNodeIndex;//节点编号

long lParentNodeIndex;//父节点编号

int NodeType;//节点状态

int iContainer8;//8升容器装啤酒量

int iContainer5;//5升容器装啤酒量

int iContainer3;//3升容器装啤酒量

}BeerTreeNode;

//最初，节点的NodeType=NO_EXTRACTED,经过规则生成新节点后NodeType=EXTRACTED或LEAF

//1.所有规则生成的节点都为以前路径上存在的节点,生成结束NodeType=LEAF.

//2.根据规则生成的节点为4 4 0,达到目标NodeType=LEAF.

//3.其它情况,此节点被处理完成NodeType标记为EXTRACTED.

public:

BeerTree();

BeerTree(long lLength,long iGrowLength);

void Output();

~BeerTree();

private:

BeerTreeNode *Root;

long lTotalLength;

long lGrowLength;

long lCurrIndex;

BeerTreeNode tempResult[TREE_LEVEL+1];

void WorkOutTree();

void ProduceNode(int level);

int AddNode(long NodeIndex,_BeerTreeNode btnAdd);

int CheckNode(BeerTreeNode btnCheck);

};

搜索树储存在动态数组中，动态树组在初始情况分配一大小，当其容量不能满足要求时，动态改变其长度，使其容量适应需要。动态数组数据线性排列，查找迅速，又不受容量限制，是一种很好的存储方式。在BeerTree的构造函数和析构函数以及AddNode函数中，动态数组实现如下：

BeerTree::BeerTree()

{

if((Root=(BeerTreeNode*)malloc(100*sizeof(BeerTreeNode)))==NULL)

{

printf("Init BeerTree Failed!\n");

exit(0);

}

lTotalLength=100;

lGrowLength=100;

lCurrIndex=0;

WorkOutTree();

}

BeerTree::BeerTree(long lLength,long lGrow)

{

if((Root=(BeerTreeNode*)malloc(lLength*sizeof(BeerTreeNode)))==NULL)

{

printf("Init BeerTree Failed!\n");

exit(0);

}

lTotalLength=lLength;

lGrowLength=lGrow;

lCurrIndex=0;

WorkOutTree();

}

BeerTree::~BeerTree()

{

try

{

free((void*)Root);

}

catch(...)

{

printf("Release BeerTree Failed!\n");

exit(0);

}

}

int BeerTree::AddNode(long NodeIndex,BeerTreeNode btnAdd)

{

if(lCurrIndex>=lTotalLength-1)

{

if((Root=(BeerTreeNode*)realloc((void*)Root,

(lTotalLength+lGrowLength)*sizeof(BeerTreeNode)))==NULL)

{

printf("Realloc Memory Error!\n");

exit(0);

}

lTotalLength+=lGrowLength;

printf("Resizing TotalLength = %d\n",lTotalLength);

}

Root[lCurrIndex].iContainer8=btnAdd.iContainer8;

Root[lCurrIndex].iContainer5=btnAdd.iContainer5;

Root[lCurrIndex].iContainer3=btnAdd.iContainer3;

Root[lCurrIndex].lParentNodeIndex=NodeIndex;

Root[lCurrIndex].NodeType=NO_EXTRACTED;

Root[lCurrIndex].lNodeIndex=lCurrIndex;

lCurrIndex++;

return 0;

}

接下来，让我们来看看规则是如何实现的，这里只列出规则１，其他规则和它大同小异，规则之间执行没有先后顺序。

tempNode=Root[i];

c8left=8-tempNode.iContainer8;

c5left=5-tempNode.iContainer5;

c3left=3-tempNode.iContainer3;

if(tempNode.NodeType==LEAF||tempNode.NodeType==EXTRACTED)

continue;

//target node :

if(tempNode.iContainer8==4&&tempNode.iContainer5==4)

{

Root[i].NodeType=LEAF;

continue;

}

//part 1 : rule 1 :

tempNode=Root[i];

if(tempNode.iContainer8!=0&&c3left!=0)

{

water=tempNode.iContainer8-c3left;

if(water>=0)

{

tempNode.iContainer8=tempNode.iContainer8-c3left;

tempNode.iContainer3=3;

}

else

{

tempNode.iContainer3=tempNode.iContainer3+tempNode.iContainer8;

tempNode.iContainer8=0;

}

if(CheckNode(tempNode)!=-1)

{

AddNode(Root[i].lNodeIndex,tempNode);

IsExtracted=true;

}

}

函数CheckNode负责判断按照生成规则生成的新节点是否符合筛选条件，就是判断从根节点到当前节点的路径上是否已经存在了新生成的节点。实现如下：

int BeerTree::CheckNode(BeerTreeNode btnCheck)

{

BeerTreeNode node=btnCheck;

int number=0;

if((btnCheck.iContainer8==8)&&

(btnCheck.iContainer5==0)&&

(btnCheck.iContainer3==0))

{

return -1;

}

else

{

while(node.lParentNodeIndex!=-1)

{

tempResult[number].iContainer8=node.iContainer8;

tempResult[number].iContainer5=node.iContainer5;

tempResult[number].iContainer3=node.iContainer3;

node=Root[node.lParentNodeIndex];

number++;

}

for(int k=0;k

{

for(int q=k+1;q

{

if((tempResult[k].iContainer3==tempResult[q].iContainer3)&&

(tempResult[k].iContainer5==tempResult[q].iContainer5))

{

return -1;

}

}

}

}

return 0;

}

搜索树的生成。采用广度优先逐层生成节点，经过测试，深度TREE_LEVEL设为20较好。函数如下：

void BeerTree::WorkOutTree()

{

int level=0;

BeerTreeNode RootNode;

RootNode.iContainer8=8;

RootNode.iContainer5=0;

RootNode.iContainer3=0;

RootNode.lNodeIndex=0;

RootNode.lParentNodeIndex=-1;

RootNode.NodeType=NO_EXTRACTED;

AddNode(-1,RootNode);

for(level=0;level

{

ProduceNode(level);

}

}

要注意的是，在类BeerTree的构造函数中已经调用了WorkOutTree函数，所以在main函数中我们只要将对象实例化，然后就可以直接调用BeerTree的Output()输出结果了，main函数如下：

int main(int argc, char* argv[])

{

BeerTree BTree=BeerTree(200,100);

BTree.Output();

return 0;

}