人工智能实验报告

1、华北电力大学实 验 报 告| 实验名称 图搜索问题求解 课程名称 人工智能及应用 | 专业班级： 学生姓名： 学 号： 成 绩：指导教师： 李继荣 实验日期： 2014.5一、实验目的及要求熟悉PROLOG语言的特点和某种PROLOG编程环境；掌握编写与调试简单的PROLOG程序的方法。通过设计、编写和调试了解PROLOG编译器；掌握PROLOG语言中常量、变量的表示方法和PROLOG进行事实库、规则库的编写方法。加深对逻辑程序运行机理的理解，掌握PROLOG语言的特点，熟悉其编程环境。针对实际应用问题，分析题目背景，利用编程实现图搜索技术的问题求解方法，以牢固掌握图搜索技术的基本原理和常用算

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

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

4、，而确定是否存在这样的路径。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

5、,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,Col

6、umn),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表示）

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

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

9、eue(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:),n

10、l, 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_se

11、t,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,_,Re

12、st_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,Close

13、d_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,

14、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. 四皇后问题，在

15、类中封装方法，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

16、 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()极大极小值算法主函数，计算机决定在哪个位置落子所采

17、用的核心算法，并且可以判断计算机落子前后棋局的状态，如果在搜索树的深度范围内能判断哪一方必胜，则可提前打印输赢信息，并结束本棋。主要方法：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

18、&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(Is

19、Win(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;/计算每一列中有多少列的棋子

20、连成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;i+)count+=(tmpQPi0+tmpQPi

21、1+tmpQPi2)/3;/计算每一列中有多少列的棋子连成3个的for(i=0;i3;i+)count+=(tmpQP0i+tmpQP1i+tmpQP2i)/3;/斜行有没有连成3个的？count+=(tmpQP00+tmpQP11+tmpQP22)/3;count+=(tmpQP20+tmpQP11+tmpQP02)/3;return count;五、实验结果图一 八骑士周游结果一图二 八骑士周游结果二图三 农夫、狼、羊、菜问题结果图四 四皇后的一个解图五 下棋过程截图六、讨论与结论通过本次实验，对在人工智能课上学习的内容有了更加深刻的理解，真正的学习必须得自己在实践中寻找问题发现问题，最终

22、解决问题，我们要的不是一个答案，而是发现答案的过程，在不断的出错中不断的进步才是学习的进步。通过在实验中对课上学习的内容的实践，真正的体会算法的作用图搜索算法的作用，在一般的计算方式下，计算模式是多么不科学，时间耗费，是否最优的达到时间以及空间的复杂度，解决实际的问题，首先的抽象出问题的数学模型，转化为数学计算，最后运用程序设计语言设计数据模型，将问题抽象解决。当然在这个过程中，需要付出时间与精力，在本实验的过程中，由于对prolog语言不太熟悉，所以在真正的写算法的过程中遇到了很多的问题，并且在编写的过程中也是出现了很多的错误，最后通过向老师请教，一步一步的改进与进步，最终实现了部分功能。高

23、级语言设计部分，因为比较的了解，相对来说比较的容易一些。下午13：0017：00度。全体员工都必须自觉遵守工作时间，实行不定时工作制的员工不必打卡。3.1.2.2打卡次数：一日两次，即早上上班打卡一次，下午下班打卡一次。3.1.2.3打卡时间：打卡时间为上班到岗时间和下班离岗时间； 3.1.2.4因公外出不能打卡：因公外出不能打卡应填写外勤登记表,注明外出日期、事由、外勤起止时间。因公外出需事先申请，如因特殊情况不能事先申请，应在事毕到岗当日完成申请、审批手续，否则按旷工处理。因停电、卡钟（工卡）故障未打卡的员工，上班前、下班后要及时到部门考勤员处填写未打卡补签申请表，由直接主管签字证明当日的

24、出勤状况，报部门经理、人力资源部批准后，月底由部门考勤员据此上报考勤。上述情况考勤由各部门或分公司和项目文员协助人力资源部进行管理。3.1.2.5手工考勤制度3.1.2.6手工考勤制申请：由于工作性质，员工无法正常打卡（如外围人员、出差），可由各部门提出人员名单，经主管副总批准后，报人力资源部审批备案。3.1.2.7参与手工考勤的员工，需由其主管部门的部门考勤员(文员)或部门指定人员进行考勤管理，并于每月26日前向人力资源部递交考勤报表。3.1.2.8参与手工考勤的员工如有请假情况发生，应遵守相关请、休假制度，如实填报相关表单。3.1.2.9 外派员工在外派工作期间的考勤,需在外派公司打卡记录

25、;如遇中途出差,持出差证明,出差期间的考勤在出差地所在公司打卡记录;3.2加班管理3.2.1定义加班是指员工在节假日或公司规定的休息日仍照常工作的情况。A现场管理人员和劳务人员的加班应严格控制，各部门应按月工时标准，合理安排工作班次。部门经理要严格审批员工排班表，保证员工有效工时达到要求。凡是达到月工时标准的，应扣减员工本人的存休或工资；对超出月工时标准的，应说明理由，报主管副总和人力资源部审批。 B因员工月薪工资中的补贴已包括延时工作补贴，所以延时工作在4小时（不含）以下的，不再另计加班工资。因工作需要，一般员工延时工作4小时至8小时可申报加班半天，超过8小时可申报加班1天。对主管(含)以上

26、管理人员，一般情况下延时工作不计加班，因特殊情况经总经理以上领导批准的延时工作，可按以上标准计加班。3.2.2.2员工加班应提前申请，事先填写加班申请表，因无法确定加班工时的，应在本次加班完成后3个工作日内补填加班申请表。加班申请表经部门经理同意，主管副总经理审核报总经理批准后有效。加班申请表必须事前当月内上报有效，如遇特殊情况，也必须在一周内上报至总经理批准。如未履行上述程序，视为乙方自愿加班。3.2.2.3员工加班，也应按规定打卡，没有打卡记录的加班，公司不予承认；有打卡记录但无公司总经理批准的加班，公司不予承认加班。3.2.2.4原则上，参加公司组织的各种培训、集体活动不计加班。3.2.

27、2.5加班工资的补偿：员工在排班休息日的加班，可以以倒休形式安排补休。原则上，员工加班以倒休形式补休的，公司将根据工作需要统一安排在春节前后补休。加班可按1：1的比例冲抵病、事假。3.2.3加班的申请、审批、确认流程3.2.3.1加班申请表在各部门文员处领取，加班统计周期为上月26日至本月25日。3.2.3.2员工加班也要按规定打卡，没有打卡记录的加班，公司不予承认。各部门的考勤员(文员)负责加班申请表的保管及加班申报。员工加班应提前申请，事先填写加班申请表加班前到部门考勤员(文员)处领取加班申请表，加班申请表经项目管理中心或部门经理同意，主管副总审核，总经理签字批准后有效。填写并履行完审批手续后交由部门考勤员(文员)保管。3.2.3.3部门考勤员（文员）负责检查、复核确认考勤记录的真实有效性并在每月2