人工智能实验报告.doc

华北电力大学实 验 报 告| 实验名称 图搜索问题求解 课程名称 人工智能及应用 | 专业班级： 学生姓名： 学 号： 成 绩：指导教师： 李继荣 实验日期： 2014.5华 北 电 力 大 学 实 验 报 告一、实验目的及要求熟悉PROLOG语言的特点和某种PROLOG编程环境；掌握编写与调试简单的PROLOG程序的方法。通过设计、编写和调试了解PROLOG编译器；掌握PROLOG语言中常量、变量的表示方法和PROLOG进行事实库、规则库的编写方法。加深对逻辑程序运行机理的理解，掌握PROLOG语言的特点，熟悉其编程环境。针对实际应用问题，分析题目背景，利用编程实现图搜索技术的问题求解方法，以牢固掌握图搜索技术的基本原理和常用算法，加深对图搜索技术的理解。实验要求采用PROLOG编程求解8*8骑士周游问题以及农夫、狼、羊、菜问题。采用熟悉的高级语言编程实现“过河问题”、“九宫格”等问题的求解。二、所用仪器、设备计算机、TRINCPROLOG及高级语言程序设计环境。三、实验原理1. 8*8骑士周游问题求解，以squre（x，y）表示骑士的位置，然后寻找一条是否存在的路径判断是否存在此路径的周游方法。通过x与y的值的范围，判断是否可以向左右方向移动，达到求解周游的问题。2. 农夫、狼、羊、菜问题求解，采用宽度优先搜索算法，寻找一条安全的路径，农夫把三物品从河的一岸送到对岸，设计状态state（x，y，z，w）表示当前四物所处在的状态，按照算法寻找出最后的路径。3. 四皇后问题解决，封装Queen类，包括皇后个数，以及皇后位置是否正确而的判断方法，然后再主方法中调用方法即可。4. 极大极小方法求解井字棋问题，对状态空间采用最大最小值搜索，计算机在生成的子节点中选择评估函数值最大的节点，而计算机在选择着数时使人选择评估函数值最小的节点，也就是对计算机一方最不利的节点。四、实验方法与步骤1. 8*8骑士周游问题，通过当前点的坐标范围判断是否可以向“加一”，“加二” 方向移动，而实现8*8周游问题的解决。通过对横纵坐标的范围，确定是否可以对其进行移动而得到判断，只需要写好对应的坐标变化，然后与当前要移动的坐标是否合一，而确定是否存在这样的路径。Path（）则是对于在两坐标判断是否存在其中的路径然后对其蕴含式的解析。当path（x，y）的x与y参数相同是则退出。实现算法：move(squre(Row,Column),squre(New_Row,New_Column):- Row=6,New_Row is Row+2,Column=7,New_Column is Column+1.move(squre(Row,Column),squre(New_Row,New_Column):- Row=2,New_Column is Column-1.move(squre(Row,Column),squre(New_Row,New_Column):- Row=3,New_Row is Row-2,Column=3,New_Row is Row-2,Column=2,New_Column is Column-1.move(squre(Row,Column),squre(New_Row,New_Column):- Row=7,New_Row is Row+1,Column=6,New_Column is Column+2.move(squre(Row,Column),squre(New_Row,New_Column):- Row=3,New_Column is Column-2.move(squre(Row,Column),squre(New_Row,New_Column):- Row=2,New_Row is Row-1,Column=2,New_Row is Row-1,Column=3,New_Column is Column-2.been(squre(0,0).path(X,X).path(X,Y):-move(X,Z),not(been(Z),dynamic(knight_tour,been/1),asserta(knight_tour,been(Z),path(Z,Y).2. 农夫、狼、羊、菜过河问题，定义状态state（x，y，z，w）表示四个物体当前所在的位置（河东还是河西用e跟w表示），move（state（x，y，z，w），state（u，v，w，g）表示从和的一岸向另一岸移动，当然移动必须满足要求，移动之后的状态必须处在一个安全的状态，用unsafe（state（）来检测所处位置是否安全，并且是农夫与移动的物体一起移动，采用go（start，goal）表示从现在开始的状态以及要达到的目标态而进行路径搜索，path(Open_queue,Closed_set,Goal)表示移动路径所需要满足的条件之一，即就是本宽度算法中的open，closed表，当然在本算法中涉及到队列的各种方法，拼接，判空等操作都需要在算法中给予具体的实现。具体实现的算法为：move(state(X,X,G,C),state(Y,Y,G,C):-opp(X,Y).move(state(X,W,X,C),state(Y,W,Y,C):-opp(X,Y).move(state(X,W,G,X),state(Y,W,G,Y):-opp(X,Y).move(state(X,W,G,C),state(Y,W,G,C):-opp(X,Y).unsafe(state(X,Y,Y,C):-opp(X,Y).unsafe(state(X,W,Y,Y):-opp(X,Y).opp(e,w).opp(w,e).go(Start,Goal):-empty_queue(Empty_open_queue), enqueue(Start,nil,Empty_open_queue,Open_queue), empty_set(Closed_set), path(Open_queue,Closed_set,Goal).path(Open_queue,_,_):-empty_queue(Open_queue), write(No solution found with these rules).path(Open_queue,Closed_set,Goal):- dequeue(State,Parent,Open_queue,_),State=Goal, write(A solution is found:),nl, printsolution(State,Parent,Closed_set).%printsolution1(Closed_set).path(Open_queue,Closed_set,Goal):- dequeue(State,Parent,Open_queue,Rest_open_queue), get_children(State,Rest_open_queue,Closed_set,Children), add_list_to_queue(Children,Rest_open_queue,New_open_queue), union(State,Parent,Closed_set,New_closed_set), path(New_open_queue,New_closed_set,Goal).get_children(State,Rest_open_queue,Closed_set,Children):- bagof(Child,moves(State,Rest_open_queue,Closed_set,Child),Children).moves(State,Rest_open_queue,Closed_set,Next,State):- move(State,Next),not(unsafe(Next), not(member_queue(Next,_,Rest_open_queue), not(member_set(Next,_,Closed_set).%printsolution1(L):-empty_set(L).%printsolution1(H|T):-printsolution1(T),write(H),nl.printsolution(State,nil,_):-write(State),nl.printsolution(State,Parent,Closed_set):-member_set(Parent,Grandparent,Closed_set), printsolution(Parent,Grandparent,Closed_set), write(State),nl.empty_set().member_set(State,Parent,State, Parent|_).member_set(X,_|T):-member_set(X,T).empty_queue().enqueue(E,E).enqueue(E,H|T,H|Tnew):-enqueue(E,T,Tnew).dequeue(State,Parent,State,Parent|T,T).add_list_to_queue(List,Queue,New_queue):-append(Queue,List,New_queue).append(X,Y,Z):-X=,Z=Y.append(X,Y,Z):-X=A|B,Z=A|W,append(B,Y,W).member(X,X|T).member(X,_|T):-member(X,T).member_queue(Element,Queue):-member(Element,Queue).union(,Set,Set).union(H|T,S,Snew):- union(T,S,S2),add_if_not_in_set(H,S2,Snew).add_if_not_in_set(X,S,S):-member(X,S),!.add_if_not_in_set(X,S,X|S).3. 四皇后问题，在类中封装方法，bool bCanPlace(int k)，oid BackTrack(int k)，void PrintX(void)，实现实现对皇后位置的检测，最后打印出结果为每行皇后的位置的列即就是为一个有效的序列。主要方法：class Queenfriend int nQueen(int); private:bool bCanPlace(int k);void BackTrack(int k);void PrintX(void);int n,*x,sum;bool Queen: bCanPlace(int k)/判断是否合法bool bOk = true;for(int i =1 ; i k; i+)if (abs(k-i) = abs( xk - xi) | (xk = xi) )bOk = false;break;return bOk;4. 极大极小值求井字棋问题，void Init()棋盘初始化函数，void PrintQP()打印棋盘函数void UserInput()用户输入落子位置函数，这三份方法程序中当前的棋局进行读写操作；nt IsWin(State s) 判断当前棋局是否有一方获胜，并判断哪一方获胜的函数，int e_fun(State s)评估函数值计算函数，当前的棋局进行判断；int AutoDone()极大极小值算法主函数，计算机决定在哪个位置落子所采用的核心算法，并且可以判断计算机落子前后棋局的状态，如果在搜索树的深度范围内能判断哪一方必胜，则可提前打印输赢信息，并结束本棋。主要方法：int IsWin(State s) /有人赢了吗？返回0表示没有人赢，返回-1表示人赢了，返回1表示计算机赢了for(int i=0;i3;i+)if(s.QPi0=1&s.QPi1=1&s.QPi2=1)return 1;if(s.QPi0=-1&s.QPi1=-1&s.QPi2=-1)return -1;for(i=0;i3;i+)if(s.QP0i=1&s.QP1i=1&s.QP2i=1)return 1;if(s.QP0i=-1&s.QP1i=-1&s.QP2i=-1)return -1;if(s.QP00=1&s.QP11=1&s.QP22=1)|(s.QP20=1&s.QP11=1&s.QP02=1)return 1;if(s.QP00=-1&s.QP11=-1&s.QP22=-1)|(s.QP20=-1&s.QP11=-1&s.QP02=-1)return -1;return 0;int e_fun(State s)/评估函数bool flag=true;for(int i=0;i3;i+)for(int j=0;j3;j+) if(s.QPij=0)flag=false;if(flag)return NO_BLANK;if(IsWin(s)=-1)return -MAX_NUM;/如果计算机输了，返回最小值if(IsWin(s)=1)return MAX_NUM;/如果计算机赢了，返回最大值int count=0;/该变量用来表示评估函数的值/将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为1for(i=0;i3;i+)for(int j=0;j3;j+) if(s.QPij=0)tmpQPij=1; else tmpQPij=s.QPij;/电脑一方/计算每一行中有多少行的棋子连成3个的for(i=0;i3;i+)count+=(tmpQPi0+tmpQPi1+tmpQPi2)/3;/计算每一列中有多少列的棋子连成3个的for(i=0;i3;i+)count+=(tmpQP0i+tmpQP1i+tmpQP2i)/3;/斜行有没有连成3个的？count+=(tmpQP00+tmpQP11+tmpQP22)/3;count+=(tmpQP20+tmpQP11+tmpQP02)/3;/将棋盘中的空格填满对方的棋子，既将棋盘数组中的0变为-1for(i=0;i3;i+)for(int j=0;j3;j+) if(s.QPij=0)tmpQPij=-1; else tmpQPij=s.QPij;/对方/计算每一行中有多少行的棋子连成3个的for(i=0;i3