人工智能---水壶问题

人工智能问题----水壶问题
有两个水壶，容量分别为3升和4升，但都没有刻度，有一水龙头往水壶里加水。问怎样才可以在4升的水壶内装2升水?

回溯法：【递归实现】
#include<iostream> using namespace std; struct List{ int x; //中间过程A壶水量 int y;
//中间过程B壶水量 int step; //记录步数 List *Last_Node; //指向路径上一节点 List *Next; //指向路径下一节点
}; int A_Capacity,B_Capacity,End_Capacity; //A壶容量、B壶容量、最终状态B壶水量 bool
Find[100][100],Check[100][100]; //记录该节点是否检索、记录该节点状态是否曾经出现 bool Get_Load =
false; //是否存在路径 //函数说明 void Find_Load(List *In); //查找路径 void Show(List *In);
//展示路径 void Find_Load(List *In) { if(Find[In->x][In->y] == true)
//如果该节点已经给检索，直接退出 return ; else //当前节点未被检索 Find[In->x][In->y] = true;
//把该节点状态设置为已检索 if(In->y == End_Capacity) //判断该节点是否为所求结果，若是把结果变量置为true，并退出 {
Get_Load = true; return ; } List *P = new List(); //创建新节点
//以下所列为六种规则，规则顺序按先后，可自己调整规则执行顺序，所得结果可能不同 //规则一：往A倒水 if(In->x+In->y <=
A_Capacity) //当A、B水量壶不大于A容量 { P->x = In->x+In->y; //更新A、B壶水量【作为一个新节点】 P->y = 0;
P->step = In->step; //记录步数 if(Check[P->x][P->y] == false) //检查该节点是否曾经出现 {
In->Next = P; //把新节点插入链表中 P->Last_Node = In; P->Next = NULL; Check[P->x][P->y]
= true; //把该节点标记为已出现 P->step++; //步数加一 Find_Load(P); //递归对新节点继续查找最终结果
if(Get_Load == false) //上一级递归结束无法找到最终结果，把当前节点从链表中剔除，继续后面规则的查找 { In->Next =
NULL; } } } else { P->x = A_Capacity; //按规则重置数据进行检索，后面各规则雷同 P->y =
In->x+In->y-A_Capacity; P->step = In->step; if(Check[P->x][P->y] == false) {
In->Next = P; P->Last_Node = In; P->Next = NULL; Check[P->x][P->y] = true;
P->step++; Find_Load(P); if(Get_Load == false) { In->Next = NULL; } } }
if(Get_Load == true) //已找到结果，退出查找。【可能存在更加优的路径未给查找出来】 return ; //规则二：往B倒水 //P =
In; if(In->x+In->y <= B_Capacity) { P->x = 0; P->y = In->x+In->y; P->step =
In->step; if(Check[P->x][P->y] == false) { In->Next = P; P->Last_Node = In;
P->Next = NULL; Check[P->x][P->y] = true; P->step++; Find_Load(P); if(Get_Load
== false) { In->Next = NULL; } } } else { P->x = In->x+In->y-B_Capacity; P->y =
B_Capacity; P->step = In->step; if(Check[P->x][P->y] == false) { In->Next = P;
P->Last_Node = In; P->Next = NULL; Check[P->x][P->y] = true; P->step++;
Find_Load(P); if(Get_Load == false) { In->Next = NULL; } } } if(Get_Load ==
true) return ; //规则三：A倒出水 //P = In; P->x = 0; P->y = In->y; P->step = In->step;
if(Check[P->x][P->y] == false) { In->Next = P; P->Last_Node = In; P->Next =
NULL; Check[P->x][P->y] = true; P->step++; Find_Load(P); } if(Get_Load ==
false) { In->Next = NULL; } else return ; //规则四：B倒出水 //P = In; P->x = In->x;
P->y = 0; P->step = In->step; if(Check[P->x][P->y] == false) { In->Next = P;
P->Last_Node = In; P->Next = NULL; Check[P->x][P->y] = true; P->step++;
Find_Load(P); } if(Get_Load == false) { In->Next = NULL; } else return ;
//规则五：A装满水 //P = In; P->y = In->y; P->x = A_Capacity; P->step = In->step;
if(Check[P->x][P->y] == false) { In->Next = P; P->Last_Node = In; P->Next =
NULL; Check[P->x][P->y] = true; P->step++; Find_Load(P); } if(Get_Load ==
false) { In->Next = NULL; } else return ; //规则六：B装满水 //P = In; P->x = In->x;
P->y = B_Capacity; P->step = In->step; if(Check[P->x][P->y] == false) {
In->Next = P; P->Last_Node = In; P->Next = NULL; Check[P->x][P->y] = true;
P->step++; Find_Load(P); } if(Get_Load == false) { In->Next = NULL; } else
return ; } void Show(List *In) { if(Get_Load == false) //最终都找不结果
cout<<"找不到路径!\n"; else //存在结果，按链表检索输出，知道链表结束 { if(In->Next != NULL) {
cout<<"第"<<In->step<<"步："<<In->x<<"\t"<<In->y<<endl; Show(In->Next); } else
cout<<"第"<<In->step<<"步："<<In->x<<"\t"<<In->y<<endl; return ; } } void main() {
cout<<"请设置A、B的容量！\n"; cout<<"A的水量："; cin>>A_Capacity; cout<<"B的水量：";
cin>>B_Capacity; cout<<"结果状态B壶水量："; cin>>End_Capacity; List *P = new
List();//创建链表 P->x = A_Capacity; //头节点赋值【代码规定开始A壶装满水，B壶为空，且最初节点为第0步】 P->y = 0;
P->step = 0; P->Next = NULL; P->Last_Node = NULL; Check[P->x][P->y] = true;
//把头节点设置为已出现 Find_Load(P); //回溯查找可行路径 Show(P); //展示结果 }
数组实现:
#include<iostream> using namespace std; struct Kittle { int x; //A号水壶的水量 int
y; //B号水壶的水量 int step; //此状态为第几步 int last_x,last_y; //上一状态下的A、B水壶里的水量 }; void
Begin(); void Find_Target(int Cap); void Continue_Find(Kittle In); void
Show(int X,int Y); int A_Capacity,B_Capacity,End_Capacity;
//A号水壶的容量、B号水壶的容量、结果状态B的容量 bool Find[100][100],Check[100][100];
//每种状态是否已经进行检索、每种状态下的出现情况 int Time=2; //次数 bool Seek_Out = false; //判断是否找到目标
Kittle Num[1000]; //保存各步的数据 void Begin() { Num[1].x = A_Capacity; //初始A水壶水满
Num[1].y = 0; //初始B水壶为空 Num[1].step = 0; //初始状态为第0步 Check[A_Capacity][0] =
true;//(A_Capacity,0)已经出现 Find_Target(End_Capacity); //寻找目标 } void
Find_Target(int Cap) { int k=1; Continue_Find(Num[k]); if(Seek_Out == false) {
cout<<"找不到路径！"; } else { Show(Num[Time-1].last_x,Num[Time-1].last_y);
cout<<"第"<<Num[Time-1].step<<"步：\t"<<Num[Time-1].x<<"\t"<<Num[Time-1].y<<endl;
} } void Continue_Find(Kittle In) { if(Find[In.x][In.y]) //此状态已经给查找 return ;
Find[In.x][In.y] = true; //标记该状态为已查找 if(In.y == End_Capacity) Seek_Out = true;
Kittle p = In; //备份 //往B加水 if(In.x+In.y <= B_Capacity) //A、B里的水量和少于或等于B的容量 {
p.y = In.x+In.y; //更新B水量 p.x = 0; //A水量置空 if(Check[p.x][p.y] == false)//该状态未给检查
{ //作为新的情况存档 Num[Time] = p; Num[Time].step++; Num[Time].last_x = In.x;
//记录上一步水状态 Num[Time].last_y = In.y; p = Num[Time]; Time++; //次数递增
Check[p.x][p.y] = true; //标记为已查找 Continue_Find(p); //递归查找新的情况 } } else
//A、B里的水量和大于B的容量 { p.y = B_Capacity; //B装满 p.x = In.x+In.y-B_Capacity; //A剩余水量
if(Check[p.x][p.y] == false) //判断该情况是否出现 { //作为新情况存档 Num[Time] = p;
Num[Time].step++; Num[Time].last_x = In.x; //记录上一步水状态 Num[Time].last_y = In.y;
p = Num[Time]; Time++; //次数递增 Check[p.x][p.y] = true; //标记为已查找
Continue_Find(p); //递归查找新的情况 } } //如果已经寻找到结果直接退出，不进行后面的查找 if(Seek_Out == true)
return ; p = In; //恢复p的数据 //往A加水 if(In.x+In.y <=A_Capacity) //A、B里的水量和少于或等于A的容量
{ p.x = In.x+In.y; p.y = 0; if(Check[p.x][p.y] == false) { //作为新情况存档 Num[Time]
= p; Num[Time].step++; Num[Time].last_x = In.x; //记录上一步水状态 Num[Time].last_y =
In.y; p = Num[Time]; Time++; //次数递增 Check[p.x][p.y] = true; //标记为已查找
Continue_Find(p); //递归查找新的情况 } } else //A、B里的水量和大于A的容量 { p.x = A_Capacity; p.y
= In.x+In.y-A_Capacity; if(Check[p.x][p.y] == false) { //作为新情况存档 Num[Time] = p;
Num[Time].step++; Num[Time].last_x = In.x; //记录上一步水状态 Num[Time].last_y = In.y;
p = Num[Time]; Time++; //次数递增 Check[p.x][p.y] = true; //标记为已查找
Continue_Find(p); //递归查找新的情况 } } //如果已经寻找到结果直接退出，不进行后面的查找 if(Seek_Out == true)
return ; p = In; //A倒水 p.x = 0; if(Check[p.x][p.y] == false) { //作为新情况存档
Num[Time] = p; Num[Time].step++; Num[Time].last_x = In.x; //记录上一步水状态
Num[Time].last_y = In.y; p = Num[Time]; Time++; //次数递增 Check[p.x][p.y] = true;
//标记为已查找 Continue_Find(p); //递归查找新的情况 } //如果已经寻找到结果直接退出，不进行后面的查找 if(Seek_Out ==
true) return ; p = In; //B倒水 p.y = 0; if(Check[p.x][p.y] == false) { //作为新情况存档
Num[Time] = p; Num[Time].step++; Num[Time].last_x = In.x; //记录上一步水状态
Num[Time].last_y = In.y; p = Num[Time]; Time++; //次数递增 Check[p.x][p.y] = true;
//标记为已查找 Continue_Find(p); //递归查找新的情况 } //如果已经寻找到结果直接退出，不进行后面的查找 if(Seek_Out ==
true) return ; p = In; //A满上 p.x = A_Capacity; if(Check[p.x][p.y] == false) {
//作为新情况存档 Num[Time] = p; Num[Time].step++; Num[Time].last_x = In.x; //记录上一步水状态
Num[Time].last_y = In.y; p = Num[Time]; Time++; //次数递增 Check[p.x][p.y] = true;
//标记为已查找 Continue_Find(p); //递归查找新的情况 } //如果已经寻找到结果直接退出，不进行后面的查找 if(Seek_Out ==
true) return ; p = In; //B满上 p.y = B_Capacity; if(Check[p.x][p.y] == false) {
//作为新情况存档 Num[Time] = p; Num[Time].step++; Num[Time].last_x = In.x; //记录上一步水状态
Num[Time].last_y = In.y; p = Num[Time]; Time++; //次数递增 Check[p.x][p.y] = true;
//标记为已查找 Continue_Find(p); //递归查找新的情况 } } void Show(int X,int Y) { int k = 1;
if(Num[k].x == X && Num[k].y == Y) //查找符合的记录 {
cout<<"第"<<Num[k].step<<"步：\t"<<Num[k].x<<"\t"<<Num[k].y<<endl; return ; }
while(k < Time) { if(Num[k].x == X && Num[k].y == Y) {
Show(Num[k].last_x,Num[k].last_y);
cout<<"第"<<Num[k].step<<"步：\t"<<Num[k].x<<"\t"<<Num[k].y<<endl; break; } k++; }
} void main() { cout<<"请设置A、B的容量！\n"; cout<<"A的水量："; cin>>A_Capacity;
cout<<"B的水量："; cin>>B_Capacity; cout<<"结果状态B壶水量："; cin>>End_Capacity; Begin(); }

• « 上一篇：Intellij IDEA 2018配置Java运行环境
• » 下一篇：VS2017移动开发（C#、VB.NET）Smobiler开发平台——Numeric控件