请选择 进入手机版 | 继续访问电脑版

【C++】人工智能实验一 猴子摘香蕉/传教士与野人(含完整代码与状态迁移图

[复制链接]
三兄弟沙发谢洪江 发表于 2020-12-31 19:23:53 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
文章目次



一、猴子摘香蕉问题

1、问题形貌

使用一阶谓词逻辑求解猴子摘香蕉问题:房内有一个猴子,一个箱子,天花板上挂了一串香蕉,其位置如图1所示,猴子为了拿到香蕉,它必须把箱子搬到香蕉下面,然后再爬到箱子上。请界说须要的谓词,列出问题的初始化状态(即下图所示状态),目的状态(猴子拿到了香蕉,站在箱子上,箱子位于位置b)。
(附加:从初始状态到目的状态的谓词演算过程。)

2、解题思路

猴子按照先到箱子所在位置/从箱子上趴下来→把箱子搬到香蕉下面→爬上箱子摘香蕉的逻辑进行着。
所以需要编写四个行动逻辑——走到箱子所在位置、从箱子上趴下来、把箱子搬到香蕉上面、爬上箱子摘香蕉。
使用一个布局界说猴子、箱子、香蕉、相对箱子的位置状态——
猴子在A点则标-1,猴子在B点则标0,猴子在C点则标1
箱子在A点则标-1,箱子在B点则标0,箱子在C点则标1
香蕉在A点则标-1,香蕉在B点则标0,香蕉在C点则标1
猴子爬上箱子则标1,没爬上则标-1
  1. struct State{        int monkey; /*-1:Monkey at A;0: Monkey at B;1:Monkey at C;*/        int box;        /*-1:box at A;0:box at B;1:box at C;*/        int banana; /*Banana at B,Banana=0*/        int monbox; /*-1: monkey on the box;1: monkey  the box;*/};struct State States[150];
复制代码
输入一个初始状态(a, b, c, d)
根据问题,确定终止状态是猴子摘到香蕉{(x,x,x,0)}(x 属于 {0,-1, 1})。
使用递归调用的方式搜索路径,每次递归前先判断当前状态是否与之前的状态重复,若重复则认为形成一个环路,回到上一步寻找其他方式通往新的状态。
3、实验结果及分析

实验结果一


分析:
初始时,猴子站在A位置,箱子在C位置,香蕉在B位置,猴子没有站在箱子上。
猴子摘香蕉的步调如下:
猴子走去C位置→猴子把箱子从C位置搬到B位置→猴子爬上箱子→猴子摘到香蕉
实验结果二


分析:
初始时,猴子站在A位置,箱子在B位置,香蕉在B位置,猴子没有站在箱子上。
猴子摘香蕉的步调如下:
猴子走去B位置→猴子爬上箱子→猴子摘到香蕉
实验结果三


分析:
初始时,猴子站在A位置,箱子在A位置,香蕉在B位置,猴子站在箱子上。
猴子摘香蕉的步调如下:
猴子从箱子上趴下来→猴子把箱子从A位置搬到B位置→猴子爬上箱子→猴子摘到香蕉
4、实验结果

当传教士与野人为五人,船最多允许三人过河时,程序运行结果如下

解的状态迁移图
1、550->441->440->331->330->221->220->111->110->001

2、550->441->440->331->330->221->220->011->110->001

3、550->441->540->331->330->221->220->111->110->001

4、550->441->540->331->330->221->220->011->110->001

5、实验代码

[code]#include "stdafx.h"#include#include#include using namespace std;struct State{        int monkey; /*-1:Monkey at A;0: Monkey at B;1:Monkey at C;*/        int box;        /*-1:box at A;0:box at B;1:box at C;*/        int banana; /*Banana at B,Banana=0*/        int monbox; /*-1: monkey on the box;1: monkey  the box;*/};struct State States[150];char* routesave[150];/*function monkeygoto,it makes the monkey goto the other place*/void monkeygoto(int b, int i){        int a;        a = b;        if (a == -1)        {                routesave = "Monkey go to A";                States[i + 1] = States;                States[i + 1].monkey = -1;        }        else if (a == 0)        {                routesave = "Monkey go to B";                States[i + 1] = States;                States[i + 1].monkey = 0;        }        else if (a == 1)        {                routesave = "Monkey go to C";                States[i + 1] = States;                States[i + 1].monkey = 1;        }        else        {                printf("parameter is wrong");        }}/*end function monkeyygoto*//*function movebox,the monkey move the box to the other place*/void movebox(int a, int i){        int B;        B = a;        if (B == -1)        {                routesave = "monkey move box to A";                States[i + 1] = States;                States[i + 1].monkey = -1;                States[i + 1].box = -1;        }        else if (B == 0)        {                routesave = "monkey move box to B";                States[i + 1] = States;                States[i + 1].monkey = 0;                States[i + 1].box = 0;        }        else if (B == 1)        {                routesave = "monkey move box to C";                States[i + 1] = States;                States[i + 1].monkey = 1;                States[i + 1].box = 1;        }        else        {                printf("parameter is wrong");        }}/*end function movebox*//*function climbonto,the monkey climb onto the box*/void climbonto(int i){        routesave = "Monkey climb onto the box";        States[i + 1] = States;        States[i + 1].monbox = 1;}/*function climbdown,monkey climb down from the box*/void climbdown(int i)//如果初始状态猴子在箱子上,则需要趴下来{        routesave = "Monkey climb down from the box";        States[i + 1] = States;        States[i + 1].monbox = -1;}/*function reach,if the monkey,box,and banana are at the same place,the monkey reach banana*/void reach(int i){        routesave = "Monkey reach the banana";}/*output the solution to the problem*/void showSolution(int i)//打印{        int c;        printf("%s \n", "Result to problem:");        for (c = 0; c<i + 1; c++)        {                printf("Step %d : %s \n", c + 1, routesave[c]);        }        printf("\n");}/*perform next step*/void nextStep(int i){        int c;        int j;        //凌驾一定步数,判断为有问题        if (i >= 150)        {                printf("%s  \n", "steplength reached 150,have problem ");                return;        }        //判断是否跟之前的状态相同,若相同则大概陷入循环,需要退出        for (c = 0; c中间状态->目的状态。</p> 例:当输入n=2,c=2时,输出:221->200->211->010->021->000;
此中:X1体现起始岸上的牧师人数;X2体现起始岸上的野人人数;X3体现小船现在位置(1体现起始岸,0体现目的岸)。
3、实验要求

写出算法的设计思想和源程序,并有用户界面实现人机交互(控制台大概窗口都可以),进行输入和输出结果,如:
Please input n: 2 Please input c: 2
Optimal Procedure: 221->200->211->010->021->000
Successed or Failed?: Successed
4、解题思路

针对“传教士与野人”实验,输入不同的传教士与野人数目,允许过河的最大人数,可以得到不同的结果。在输出所有可行路径之后,输出最优路径,即所花次数最少的结果。
这题使用DFS算法,运用递归来写DFS算法,搜索扫描大概的路径,若可行则打印出来,同时比力当前路径是否比已存储的最短路径短,若是,则当前路径存储为最短路径,若否则跳过。
5、实验代码

[code]// 传教士与野人.cpp #include using namespace std;#define maxNum 150struct op{        int M;        //牧师过河人数        int C;        //野人过河人数};struct State{        int minister;        //起始岸上的牧师人数        int savage;                //起始岸上的野人人数        int side;                //side=0,船在初始岸,side=1,船在对岸};int n;                //牧师和野人数目int c;                //小船最多能载的人数int op_num;        //有多少种过河方式int min_road=999;//最短路径struct op opNum[maxNum];struct State States[maxNum];struct State StatesMin[maxNum];//安全状态int isSafe(int i){        if (States.minister == 0 || States.minister == n || States.minister == States.savage)                return 1;        return 0;}//最终目的int isGoal(int i){        if (States.minister == 0 && States.savage == 0)                return 1;        return 0;}//判断是否跟之前的状态重复int isRepeat(int i){        for (int j = 0; j < i; j++)        {                if (States.minister == States[j].minister&&States.savage == States[j].savage&&States.side==States[j].side)                        return 1;        }        return 0;}//可选择的过河方式void OpNum(){        for(int i=0;i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )