野人传教士过河问题
摘要：北京时间3月12日下午，谷歌人工智能AlphaGo与韩国棋手李世石今日进行了第三场较量，最终AlphaGo战胜李世石，连续取得三场胜利。随着又一次的人工智能与人类智能的世纪大战，我们不禁要思索，人工智能，是在呼唤上帝还是在召唤恶魔？此时正是时候研究一下人工智能相关理论，而本文主要论述计算机科学与技术专业大三下专业课《人工智能》第一个实验算法。
关键字：人工智能，搜索问题，树的深度优先搜索TheMissionariesandCannibalsProblemAbstract:BeijingtimeonMarch12intheafternoon,GoogleAlphaGoandartificialintelligence,thethirdfieldofthesouthKoreanchessplayerleese-doltoday,finallybeatleese-dolAlphaGo,wonthreeconsecutivevictory.
Again,asthecenturyofartificialintelligenceandhumanintelligencewar,wecannothelpbuttothink,artificialintelligence,incallingupongodorsummondemons?Nowisthetimetostudytherelatedtheory,artificialintelligence,thispapermainlydiscussesthecomputerscienceandtechnologyunderthejuniorinprofessionalclass"artificialintelligence"inthefirstexperimentalgorithm。
Keywords:artificialintelligence,search,depthfirstsearchtree
1.问题重述 在河的左岸有N个传教士、N个野人和一条船，传教士们想用这条船把所有人都运过河去，但有以下条件限制：（1）修道士和野人都会划船，但船每次最多只能运K个人；（2）在任何岸边野人数目都不能超过修道士，否则修道士会被野人吃掉。
假定野人会服从任何一种过河安排，请规划出一个确保修道士安全过河的计划。2.问题分析 2.1约束条件： ① M≧C 任何时刻两岸、船上都必须满足传教士人数不少于野人数（M=0时除外，既没有传教士） ② M+C≦K 船上人数限制在K以内
2.2求解： 传教士与野人全部安全渡到对岸的解决方案3.求解过程 3.1变量假设： 设N=3，K=2（三个M和三个C，每次渡河二人以下） L：左岸，R：右岸， B：是否有船（0：无船，1：有船） 3.2状态表示 定义：用三元组（ML，CL，BL）表示左岸状态，其中： 0≦ML,CL≦3，BL∈｛0,1｝ 如：（0，3，1）表示左岸有三个野人，船在左岸。 从（3，3，1）到（0，0，0）的状态转换 状态空间：32种状态，其中： 12种不合理状态：如（1，0，1）说明右岸有2个M，3个C； 4种不可能状态：如（3，3，0）说明所有M和C都在左岸，而船在右岸 ∴可用的状态共16种，组成合理的状态空间 状态空间具体描述 3.2操作集 定义：Pmc操作：从左岸划向右岸Qmc操作：从右岸划向左岸
船上人数组合（m，c）共5种（1，0）,（1，1）,（2，0）,（0，1）,（0，2）
∵每一种船上的人数组合同时对应P，Q二种操作
∴系统共有5×2＝10种操作（规则）
如：P10：if（ML，CL，BL=1）then（ML-1，CL，BL-1）
如果船在左岸，那么一个传教士划船到右岸
Q01：if（ML，CL，BL=0）then（ML，CL+1，BL+1）
如果船在右岸，那么一个野人划船回到左岸
总共有10种操作
F={P10,P20,P11,P01,P02,Q10,Q20,Q11,Q01,Q02} P10 if(ML,CL,BL=1) then(ML–1,CL,BL–1) P01 if(ML,CL,BL=1) then(ML,CL–1,BL–1) P11 if(ML,CL,BL=1) then(ML–1,CL–1,BL–1) P20 if(ML,CL,BL=1) then(ML–2,CL,BL–1) P02 if(ML,CL,BL=1) then(ML,CL–2,BL–1) Q10 if(ML,CL,BL=0) then(ML+1,CL,BL+1) Q01 if(ML,CL,BL=0) then(ML,CL+1,BL+1) Q11 if(ML,CL,BL=0) then(ML+1,CL+1,BL+1) Q20 if(ML,CL,BL=0) then(ML+2,CL+2,BL+1) Q02 if(ML,CL,BL=0) then(ML,CL+2,BL+1) 3.3控制策略 最短路径有4条，由11次操作构成。(P11、Q10、P02、Q01、P20、Q11、P20、Q01、P02、Q01、P02)(P11、Q10、P02、Q01、P20、Q11、P20、Q01、P02、Q10、P11)(P02、Q01、P02、Q01、P20、Q11、P20、Q01、P02、Q01、P02) (P02、Q01、P02、Q01、P20、Q11、P20、Q01、P02、Q10、P11) 3.4状态空间图 状态空间图是一个有向图，图中的节点代表状态，节点之间的连线代表操作，箭头代表状态的转换方向。 3.5状态空间的一般搜索过程 OPEN表：用于存放刚生成的节点 CLOSE表：用于存放将要扩展或已扩展的节点 1)把初始节点S0放入OPEN表,并建立只含S0的图,记为G OPEN：=S0,G：=G0（G0=S0） 2)检查OPEN表是否为空,若为空则问题无解,退出 LOOP：IF（OPEN）=（）THENEXIT（FAIL） 3)把OPEN表的第一个节点取出放入CLOSE表,记该节点为节点n N：=FIRST（OPEN）,REMOVE（n,OPEN）,ADD（n,CLOSE） 4)观察节点n是否为目标节点,若是,则求得问题的解,退出 IFGOAL（n）THENEXIT（SUCCESS） 5)扩展节点n,生成一组子节点.把其中不是节点n先辈的那些子节点记作集合M,并把这些节点作为节点n的子节点加入G中.EXPAND（n）-->M（mi）,G：=ADD（mi,G） 针对M中子节点的不同情况,分别进行如下处理 对于那些未曾在G中出现过的M成员设置一个指向父节点（n）的指针,并把它放入OPEN表 对于那些先前已在G中出现过的M成员,确定是否要修改指向父节点的指针 对于那些先前已在G中出现,并且已经扩展了的M成员,确定是否需要修改其后继结点指向父节点的指针 6)按某种搜索策略对OPEN表中的节点进行排序 7)转第2步 针对本题，设置OPEN、CLOSED两个队列分别存放待扩展节点和已扩展节点； 对每个生成的新节点，要检查上述两表中是否已存在，是否是非法节点； (合法节点满足： ML=0||ML=3||ML=CL)
每扩展一个节点应记录产生合法后继节点的操作，以便最后给出操作序列； 4.程序设计 4.1数据结构 节点状态用列表(m，c，b)表示，其中m表示传教士在左岸的人数； c表示野人在左岸的人数；b表示船是否在左岸，当b=1时，表示船在左岸，当b=0时，表式船在右岸。
初始状态： (3，3，1) 目标状态： (0，0，0） 操作算子： 船上人数组合（m，c）共5种（1，0），（1，1），（2，0），（0，1），（0，2） 因此算法有10种 1) 从右岸向左岸过1个传教士，0个野人 2) 从右岸向左岸过1个传教士，1个野人 3) 从右岸向左岸过2个传教士，0个野人 4) 从右岸向左岸过0个传教士，1个野人 5) 从右岸向左岸过0个传教士，2个野人 6) 从左岸向右岸过1个传教士，0个野人 7) 从左岸向右岸过1个传教士，1个野人 8) 从左岸向右岸过2个传教士，0个野人 9) 从左岸向右岸过0个传教士，1个野人 10) 从左岸向右岸过0个传教士，2个野人
状态节点： typedefstructst { intm； //传教士 intc； //野人 intb； //船左 }state； //状态
将有效的状态节点存储在树中
Tree 中的节点
typedefstructhnode { state s； structhnode*left； structhnode*right； }node；
Open表，closed表用队列存储
//定义队列中的节点typedefstructQueuenode{ node *np； struct Queuenode*next；}Qnode； //队列中节点
//定义队列typedefstructQueue{ Qnode*front； Qnode*rear；}queue；
4.2代码设计
4.2.1面向对象的迭代方法
#includeusingnamespacestd;typedefstructMCNode{intm;intc;intb;intnum;structMCNode*next;structMCNode*last;}MCNode;classList{private:MCNode*head;MCNode*rear;MCNode*current;public:List();friendbooloperator==(MCNode&node1,MCNode&node2);voidpush_front(MCNodecNode);voidpush_back(MCNodecNode);voidpop_front();voidpop_back();MCNode&front();MCNode&back();voidprint_list();boolhit_target(MCNode&cNode);boollegal(MCNode&cNode);boolempty();boolexist(MCNode&cNode);};List::List(){head=newMCNode();rear=head;head->m=3;head->c=3;head->b=1;head->num=0;head->last=NULL;head->next=NULL;}booloperator==(MCNode&node1,MCNode&node2){if(node1.m==node2.m&&node1.c==node2.c&&node1.b==node2.b)returntrue;elsereturnfalse;}voidList::push_front(MCNodecNode){(*head).last=newMCNode();head->last->next=head;head=head->last;head->m=cNode.m;head->c=cNode.c;head->b=cNode.b;head->num=cNode.num;head->last=NULL;}voidList::push_back(MCNodecNode){(*rear).next=newMCNode();rear->next->last=rear;rear=rear->next;rear->m=cNode.m;rear->c=cNode.c;rear->b=cNode.b;rear->num=cNode.num;rear->next=NULL;}voidList::pop_front(){if(head->next!=NULL){head=head->next;head->last=NULL;}else{head=NULL;rear=NULL;}}voidList::pop_back(){if(rear->last!=NULL){rear=rear->last;rear->next=NULL;}else{head=NULL;rear=NULL;}}MCNode&List::front(){return*head;}MCNode&List::back(){return*rear;}voidList::print_list(){MCNodecurrent;current=*head;while(true){cout人工智能实验二报告（含代码说明）
实验目的实验硬件，软件平台Prolog学习问题的选取一、实验目的1.熟悉PROLOG的运行环境，进行PROLOG的基本编程练习；了解PROLOG语言中常量、变量的表示方法。PROLOG的简单程序结构，掌握分析问题、询问解释技巧；进行事实库、规则库的编写，并在此基础上进行简单的询问。2.求解图搜索问题。任选一个以下实际应用题目：爱因斯坦的超级问题、字谜问题、汉诺塔问题、八数码问题、八皇后问题、农夫过河问题、传教士与野人问题。二、实验的硬件、软件平台硬件：计算机软件：操作系统：WINDOWS／Linux应用软件：Prolog
三．Prolog的学习1.prolog的用途。主要用在人工智能和计算机语言的研究领域，prolog和LISP是两个主要的研究人工智能算法的工具，基本的写法是确定物件与物件之间的关系，询问目标的方式来查询各个物件之间的关系，系统会自动进行匹配和回溯，找出正确的答案，有自己的知识库。2.安装配置对应系统的SWI-Prolog。
Windows安装SWI-Prolog，64位版本。打印语句打印出第一句话helloworld，后面会跟着一句true，Prolog调用时会查询自己的知识库，判断知识库中这句话是否为真，打印出判断结果。退出语句为halt.每句话以“.”结尾，halt退出SWI-Prolog。3.语法的熟悉。程序由一组事实，规则和问题组成，根据事实推导出隐藏的规则，并且提出查询的问题，得到问题的答案。使用记事本编辑图的关系，并且保存下来，记录路径，通过路径来查询，点击file的consult来查询，也可以输入文件路径来查询。
对应的家谱，yuan:母亲，yuqing:女儿，di:父亲，xin:奶奶，jianbo：爷爷。
每一行代表一个子句，带有“：-”的是规则，不带有“：-”的是事实，以小写英文字母开头的是原子，以大写字母开头的是变量，原子是常量，它的值是不可以改变的，变量的值可以改变，在Prolog里面，“，”表示逻辑关系的且，“；”表示逻辑关系的或。
Consult让SWI-Prolog加载后面文件路径的程序，然后编译，文件存在，输出true，输入grandmother查询yuqing的祖母是谁，结果为xin,虽然我们没有直接输入这个关系，但是Prolog根据我们给出的规则生成，输入father（di,yuqing）,yuqing的父亲是di,查询prolog的知识库，存在这个子句关系，输出结果为true。Prolog的表相关知识：表是Prolog的一种数据结构，数字中序列，集合，数组，记录都可以使用表来表示，最大的特点是长度不固定，可以改变，可以增加或者删除一个元素，通过表可以方便地构建堆栈，队列，链表，树等动态数据结构，十分方便好用。同时，表可以分为头尾两个部分，表头是第一个元素，表尾是最后一个元素，通过[header|tail]来进行划分，它可以按照你的划分方式来划分元素，进行灵活地匹配。Prolog查询的方式：（1）匹配，prolog试图从自己的知识库里找出最符合你的规则或者是事实。（2）变量重命名，给变量重命名保证变量不重复。（3）回溯，使用深度优先的算法寻找答案，直到查询完所有可能的情况，如果依然不能证实，那么返回“false”。4.Prolog的过程性意义和描述性意义Prolog通过过程性意义来确定解决问题的步骤，描述性意义在于描述问题中各个物体之间的关系，Prolog进行搜索知识库回溯规则来解决问题，并且输出判断的结果，或是二者之间的关系。四．问题的选取1.题目描述事实：1、在一条街上,有5座房子,喷了5种颜色.2、每个房里住着不同国籍的人3、每个人喝不同的饮料,抽不同品牌的香烟,养不同的宠物
提示：1、英国人住红色房子2、瑞典人养狗3、丹麦人喝茶4、绿色房子在白色房子左面5、绿色房子主人喝咖啡6、抽PallMall香烟的人养鸟7、黄色房子主人抽Dunhill香烟8、住在中间房子的人喝牛奶9、挪威人住第一间房10、抽Blends香烟的人住在养猫的人隔壁11、养马的人住抽Dunhill香烟的人隔壁12、抽BlueMaster的人喝啤酒13、德国人抽Prince香烟14、挪威人住蓝色房子隔壁15、抽Blends香烟的人有一个喝水的邻居问题：谁养鱼?
2.问题分析使用目标导向分析，我们需要写出prolog程序来解答这个问题，程序由文字编辑器输入，根据题目中给出的已知条件，写出对应的规则，事实，最后推导出问题的答案。根据题目意思，在爱因斯坦问题中，五所房子相邻在一起，房子的颜色不同，房客的国籍不同，养的宠物不同，抽烟，饮料也不同，通过给出的15个事实，需要推导出养鱼的人的具体信息，从而使得所有信息成立。（1）对于房子来说，根据提示4，有的房子在另一所的左边；（2）提示8中，有的房子在5所房子中间，5所房子是相邻排列的；（3）提示10，11，14中，有的房子A在另一所房子B的隔壁；（4）根据三条总结，我们可以制定相应的规则，来实现房子处于左边，房子处于中间，房子处在第一位，房子在隔壁；
（5）每所房子的房客都有五个特点，我们可以设定谓词person(Color,Country,Drink,Cigar,Pet）,五个属性对应五个特点，每个房子的属性都不一样。（6）使用house（A，[]）来表示房子在五所房子中的位置信息，从左到右排列，处于一个长度为5的列表中，每个列表元素代表着一所房子，下划线“_”表示当前属性待定。
（7）根据题目的意思，使用逻辑且，输入所有的事实。
（8）在满足所有的前提的情况下，求出最后需要得到问题的表示形式，得到正确的布局和答案即可。
3.结果运行
在保存文本文件的时候保存为大写字母开头，然后保存为.pl格式，在文本中编辑的时候，注释使用“/**/”表示，由于SWI-prolog不能识别中文，加了中文注释后一直运行不通过，所以把注释换为了英文才得到正确的结果。在事实陈述的时候，使用“，”表示逻辑且，“.”表示事实陈述结束。运行的结果中，通过consult来建立连接，true表示连接成功，输入solve（A）查看列表中的具体内容，A表示变量，是一个列表参数，表示所有的房子的排列，打印的结果里面，满足了所有的条件，可以看到德国人German的宠物是金鱼。
房子的排列情况：