人工智能与及应用

1、实验报告|实验名称图穆索问题求解课程名称人工智能及应用一、实验目的及要求熟悉PROLOG语言的特点和某种 PROLOG编程环境；掌握编写与调试简单的 PROLOG程序的方法。通过设计、编 写和调试了解 PROLOG编译器；掌握PROLOG语言中常量、 变量的表示方法和PROLOG进行事实库、规则库的编写方法。加深对逻辑程序运行机理的理解，掌握PROLOG语言的特点, 熟悉其编程环境。针对实际应用问题，分析题目背景，利用 编程实现图搜索技术的问题求解方法，以牢固掌握图搜索技 术的基本原理和常用算法，加深对图搜索技术的理解。实验要求采用PROLOG编程求解8*8骑士周游问题以及 农夫、狼、羊、菜问

2、题。采用熟悉的高级语言编程实现“过 河问题”、“九宫格”等问题的求解。二、所用仪器、设备计算机、TRINC - PROLOG及高级语言程序设计环境。三、实验原理1 . 8*8骑士周游问题求解，以 squre (x, y)表示骑士的 位置，然后寻找一条是否存在的路径判断是否存在此 路径的周游方法。通过 x与y的值的范围，判断是否 可以向左右方向移动，达到求解周游的问题。2 .农夫、狼、羊、菜问题求解，采用宽度优先搜索算法， 寻找一条安全的路径，农夫把三物品从河的一岸送到 对岸，设计状态state (x, y, z, w)表示当前四物所处在的状态，按照算法寻找由最后的路径3 .四皇后问题解决，封装

3、 Queen类，包括皇后个数，以及皇 后位置是否正确而的判断方法，然后再主方法中调用方法 即可。4 .极大极小方法求解井字棋问题，对状态空间采用最大最小 值搜索，计算机在生成的子节点中选择评估函数值最大的 节点，而计算机在选择着数时使人选择评估函数值最小的 节点，也就是对计算机一方最不利的节点。四、实验方法与步骤1. 8*8骑士周游问题，通过当前点的坐标范围判断是否可以向“加一”，“加二”方向移动，而实现 8*8周游问题的解决。通过对横纵坐标的范围，确定是否可以对 其进行移动而得到判断，只需要写好对应的坐标变化， 然后与当前要移动的坐标是否合一，而确定是否存在 这样的路径。Path ()则是对

4、于在两坐标判断是否存 在其中的路径然后对其蕴含式的解析。当path (x, y)的x与y参数相同是则退由。实现算法：move(squre(Row,Column),squre(New_Row,New_Colum n)：-Row=<6,New_Row is Row+2,Column=<7,New_Columnis Column+1.move(squre(Row,Column),squre(New_Row,New_Colum n)：-Row=<6,New_Row is Row+2,Column>=2,New_Column is Column-1.move(squre(Row,

5、Column),squre(New_Row,New_Colum n):-Row>=3,New_Row is Row-2,Column=<7,New_Column is Column+1.move(squre(Row,Column),squre(New_Row,New_Colum n):-Row>=3,New_Row is Row-2,Column>=2,New_Column is Column-1.move(squre(Row,Column),squre(New_Row,New_Colum n):-Row=<7,New_Row is Row+1,Column=&l

6、t;6,New_Column is Column+2.move(squre(Row,Column),squre(New_Row,New_Colum n):-Row=<7,New_Row is Row+1,Column>=3,New_Column is Column-2.move(squre(Row,Column),squre(New_Row,New_Colum n):-Row>=2,New_Row is Row-1,Column=<6,New_Columnis Column+2.move(squre(Row,Column),squre(New_Row,New_Colum

7、 n)：-Row>=2,New_Row is Row-1,Column>=3,New_Columnis Column-2.been(squre(0,0).path(X,X).path(X,Y):-move(X,Z),not(been(Z),dynamic(knig ht_tour,been/1),asserta(knight_tour,been(Z),p ath(Z,Y).2.农夫、狼、羊、菜过河问题，定义状态state (x, y,z, w)表示四个物体当前所在的位置(河东还是河西用 e 跟 w 表示)，move (state (x, y, z, w), state(u, v,

8、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,

9、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_

10、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:"),n

11、l,printsolution(State,Parent,Closed_set).%printsolution1(Closed_set).path(Open_queue,Closed_set,Goal):-dequeue(State,Parent,Open_queue,Rest_open_qu eue),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,N

12、ew_closed_s et),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,S tate):-move(State,Next),not(unsafe(Next),not(member_queue(Next,_,Rest_o

13、pen_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_se

14、t),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,ParentT,T).add_list_to_queue(List,Queue,New_queue):-appen d(Queue,List,New_queue).append(X,Y,Z):-X

15、=,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,Qu eue).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.四皇后问题，在类中封装方

16、法，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 &l

17、t; 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) 判断当前棋局 是否有一方获胜，并判断哪一方获胜的函数，inte_fun(State s)评估函数值计算函数，当前的棋局进行判断；int AutoDone()极大极小值算法主函数，计算机决定在哪个位置落子所采用

18、的核心算法，并且可 以判断计算机落子前后棋局的状态，如果在搜索树的 深度范围内能判断哪一方必胜，则可提前打印输赢信 息，并结束本棋。主要方法：int IsWin(State s) / 有人赢了吗？返回 0表示没有 人赢，返回-1表示人赢了，返回1表示计算机赢了 (for(int i=0;i<3;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;i<3;i+)(if(s.

19、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.QP

20、11=-1&&s.QP0 2=-1)return -1;return 0;)int e_fun(State s)/评估函数(bool flag=true;for(int i=0;i<3;i+)for(int j=0;j<3;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;/该变量用来表示评估函数的值/将棋盘中的空格

21、填满自己的棋子，既将棋盘数组中的0变为1for(i=0;i<3;i+)for(int j=0;j<3;j+)if(s.QPij=0)tmpQPij=1;else tmpQPij=s.QPij;/电脑一方/计算每一行中有多少行的棋子连成3个的for(i=0;i<3;i+)count+=(tmpQPi0+tmpQPi1+tmpQPi2)/3 ;/计算每一列中有多少列的棋子连成3个的for(i=0;i<3;i+)count+=(tmpQP0i+tmpQP1i+tmpQP2i)/3；/斜行有没有连成3个的？count+=(tmpQP00+tmpQP11+tmpQP22)/3;count+=(tmpQP20+tmpQP11+tmpQP02)/3 ;/将棋盘中的空格填满对方的棋子，既将棋盘数组中 的0变为-1 for(i=0;i<3;i+)for(int j=0;j<3;j+)if(s.QPij=0)tmpQPij=-1;else tmpQPij=s.QPij;/对方/计算每一行中有多少行的棋子连成3个的for(i=0;i<3;i+)count+=(tmpQPi0+tmpQPi1+tmpQPi2)/3;/计算