人工智能实验报告.docx
《人工智能实验报告.docx》由会员分享，可在线阅读，更多相关《人工智能实验报告.docx（11页珍藏版）》请在冰点文库上搜索。
人工智能实验报告
华北电力大学
实验报告
|
|
实验名称图搜索问题求解
课程名称人工智能及应用
|
|
专业班级：
软件1102学生姓名：
夏明轩
学号：
201109020221成绩：
指导教师：
李继荣实验日期：
2014.5
（实验报告如打印，纸张用A4，左装订；页边距：
上下2.5cm,左2.9cm,右2.1cm；字体：
宋体小四号，1.25倍行距。
）
验证性、综合性实验报告应含的主要内容：
一、实验目的及要求
二、所用仪器、设备
三、实验原理
四、实验方法与步骤
五、实验结果与数据处理
六、讨论与结论（对实验现象、实验故障及处理方法、实验中存在的问题等进行分析和讨论，对实验的进一步想法或改进意见）
七、所附实验输出的结果或数据
设计性实验报告应含的主要内容：
一、设计要求
二、选择的方案
三、所用仪器、设备
四、实验方法与步骤
五、实验结果与数据处理
六、结论（依据“设计要求”）
七、所附实验输出的结果或数据
*封面左侧印痕处装订
一、实验目的及要求
熟悉PROLOG语言的特点和某种PROLOG编程环境；掌握编写与调试简单的PROLOG程序的方法。
通过设计、编写和调试了解PROLOG编译器；掌握PROLOG语言中常量、变量的表示方法和PROLOG进行事实库、规则库的编写方法。
加深对逻辑程序运行机理的理解，掌握PROLOG语言的特点，熟悉其编程环境。
针对实际应用问题，分析题目背景，利用编程实现图搜索技术的问题求解方法，以牢固掌握图搜索技术的基本原理和常用算法，加深对图搜索技术的理解。
实验要求采用PROLOG编程求解8*8骑士周游问题以及农夫、狼、羊、菜问题。
采用熟悉的高级语言编程实现“过河问题”、“九宫格”等问题的求解。
二、所用仪器、设备
计算机、TRINC－PROLOG及高级语言程序设计环境。
三、实验原理
1.8*8骑士周游问题求解，以squre（x，y）表示骑士的位置，然后寻找一条是否存在的路径判断是否存在此路径的周游方法。
通过x与y的值的范围，判断是否可以向左右方向移动，达到求解周游的问题。
2.农夫、狼、羊、菜问题求解，采用宽度优先搜索算法，寻找一条安全的路径，农夫把三物品从河的一岸送到对岸，设计状态state（x，y，z，w）表示当前四物所处在的状态，按照算法寻找出最后的路径。
3.四皇后问题解决，封装Queen类，包括皇后个数，以及皇后位置是否正确而的判断方法，然后再主方法中调用方法即可。
4.极大极小方法求解井字棋问题，对状态空间采用最大最小值搜索，计算机在生成的子节点中选择评估函数值最大的节点，而计算机在选择着数时使人选择评估函数值最小的节点，也就是对计算机一方最不利的节点。
四、实验方法与步骤
（一）八骑士周游问题
8*8骑士周游问题求解，以squre（x，y）表示骑士的位置，然后寻找一条是否存在的路径判断是否存在此路径的周游方法。
通过x与y的值的范围，判断是否可以向左右方向移动，达到求解周游的问题。
8*8骑士周游问题，通过当前点的坐标范围判断是否可以向“加一”，“加二”方向移动，而实现8*8周游问题的解决。
通过对横纵坐标的范围，确定是否可以对其进行移动而得到判断，只需要写好对应的坐标变化，然后与当前要移动的坐标是否合一，而确定是否存在这样的路径。
Path（）则是对于在两坐标判断是否存在其中的路径然后对其蕴含式的解析。
当path（x，y）的x与y参数相同是则退出。
实现算法：
move（squre（Row,Column）,squre（New_Row,New_Column））:
-
Row=<6,New_RowisRow+2,Column=<7,New_ColumnisColumn+1.
move（squre（Row,Column）,squre（New_Row,New_Column））:
-
Row=<6,New_RowisRow+2,Column>=2,New_ColumnisColumn-1.
move（squre（Row,Column）,squre（New_Row,New_Column））:
-
Row>=3,New_RowisRow-2,Column=<7,New_ColumnisColumn+1.
move（squre（Row,Column）,squre（New_Row,New_Column））:
-
Row>=3,New_RowisRow-2,Column>=2,New_ColumnisColumn-1.
move（squre（Row,Column）,squre（New_Row,New_Column））:
-
Row=<7,New_RowisRow+1,Column=<6,New_ColumnisColumn+2.
move（squre（Row,Column）,squre（New_Row,New_Column））:
-
Row=<7,New_RowisRow+1,Column>=3,New_ColumnisColumn-2.
move（squre（Row,Column）,squre（New_Row,New_Column））:
-
Row>=2,New_RowisRow-1,Column=<6,New_ColumnisColumn+2.
move（squre（Row,Column）,squre（New_Row,New_Column））:
-
Row>=2,New_RowisRow-1,Column>=3,New_ColumnisColumn-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）.
运行结果
（二）农夫、狼、羊、菜问题
农夫、狼、羊、菜问题求解，采用宽度优先搜索算法，寻找一条安全的路径，农夫把三物品从河的一岸送到对岸，设计状态state（x，y，z，w）表示当前四物所处在的状态，按照算法寻找出最后的路径。
此问题涉及到了四个对象：
农夫，狼，羊，白菜。
各个成员的位置，如果用字母n和s分别表示北岸和南岸，则location（n,s,n,s）可以表示规定农夫和羊在北岸，狼和白菜在南岸。
动作描述了农夫的摆渡操作，只可能有四种动作：
农夫单独过河，农夫带着狼过河，农夫带着羊过河，农夫带着白菜过河。
解决此问题便是一个求动作序列的问题，但是动作序列直接求解比较困难，可以将求解动作的问题化为求解状态变化序列的问题，因为状态的变化可以反应动作。
即通过求解一个从初状态location（n,n,n,n）到末状态location（s,s,s,s）的中间序列，进而解和其动作。
下面将实现过程描述如下：
在南岸与在北岸是不同的状态：
reverse（n,s）.reverse（s,n）.
可能发生危险的只有羊与白菜，要确保它们的安全。
关于羊，如果农夫与羊在河岸的同一侧，则羊一定安全：
safe_sheep（D,_,D,_）.
如果农夫与羊不在河岸的同一侧，在确保羊与狼也不在河的同一侧：
safe_sheep（F,W,S,_）:
-reverse（F,S）,reverse（W,S）.同理可以写出白菜安全的情况：
safe_cabbage（D,_,_,D）.
safe_cabbage（F,_,S,C）:
-reverse（F,C）,reverse（S,C）.安全状态由羊和白菜的安全状态共同组成：
safe（F,W,S,C）:
-safe_sheep（F,W,S,C）,safe_cabbage（F,W,S,C）.
过河的方案，共有四种过河的情况：
情况一：
农夫单独过河。
boat（location（D1,W,S,C）,location（D2,W,S,C））:
-reverse（D1,D2）.
情况二：
农夫带着狼过河。
boat（location（D1,D1,S,C）,location（D2,D2,S,C））:
-reverse（D1,D2）.
情况三：
农夫带着羊过河。
boat（location（D1,W,D1,C）,location（D2,W,D2,C））:
-reverse（D1,D2）.
情况四：
农夫带着白菜过河。
boat（location（D1,W,S,D1）,location（D2,W,S,D2））:
-reverse（D1,D2）.对应过河的四种情况，有四种输出语句描述过河：
情况一：
农夫单独过河。
write_move（location（D1,W,S,C）,location（D2,W,S,C））:
-write（"Thefarmercrossestheriverhimself!
"）,nl.
情况二：
农夫带着狼过河。
write_move（location（D1,D1,S,C）,location（D2,D2,S,C））:
-write（"Thefarmercrossestheriverwiththewolf!
"）,nl.
情况三：
农夫带着羊过河。
write_move（location（D1,W,D1,C）,location（D2,W,D2,C））:
-write（"Thefarmercrossestheriverwiththesheep!
"）,nl.
情况四：
农夫带着白菜过河。
write_move（location（D1,W,S,D1）,location（D2,W,S,D2））:
-write（"Thefarmercrossestheriverwiththecabbage!
"）,nl.
因为是通过状态的变化来体现动作，农夫，狼，羊，白菜要是想顺利到达对岸，他们在河的两岸的分布状态就不应该重复出现。
因此可用一个表L来记录过河的每一个状态。
要用到下面判断是否为表成员的表处理：
member（X,[X|_]）.
member（X,[_|L]）:
-member（X,L）.
最后将状态的变化对应过河的每一种动作，进行输出，即要输出L：
write_List（[]）.
write_List（[H1,H2|T]）:
-write_move（H1,H2）,write_List（[H2|T]）.
过河的过程，先找到一种过河的情况，后判断末状态是否安全，并且末状态是以前没有出现过的状态。
move（location（F0,W0,S0,C0）,location（F,W,S,C）,Temp_L,List）:
-boat（location（F0,W0,S0,C0）,location（F1,W1,S1,C1））,
safe（F1,W1,S1,C1）,
not（member（location（F1,W1,S1,C1）,Temp_L））,
move（location（F1,W1,S1,C1）,location（F,W,S,C）,[location（F1,W1,S1,C1）|Temp_L],List）.move（location（F,W,S,C）,location（F,W,S,C）,L,L）.
简化问题的输入，将过河问题拆成两部分，前部分求解状态，后部分作输出：
fun（location（F0,W0,S0,C0）,location（F,W,S,C））:
-
move（location（F0,W0,S0,C0）,location（F,W,S,C）,[location（F0,W0,S0,C0）],L）,write_List（L）.
输入如下数据：
运行结果如下图所示：
（三）四皇后问题
四皇后问题解决，封装Queen类，包括皇后个数，以及皇后位置是否正确而的判断方法，然后再主方法中调用方法即可。
四皇后问题，在类中封装方法，boolbCanPlace（intk），oidBackTrack（intk），voidPrintX（void），实现实现对皇后位置的检测，最后打印出结果为每行皇后的位置的列即就是为一个有效的序列。
主要方法：
classQueen{
friendintnQueen（int）;
private:
boolbCanPlace（intk）;
voidBackTrack（intk）;
voidPrintX（void）;
intn,*x,sum;
};
boolQueen:
:
bCanPlace（intk）//判断是否合法
{
boolbOk=true;
for（inti=1;i{
if（（abs（k-i）==abs（x[k]-x[i]））||（x[k]==x[i]））
{
bOk=false;
break;
}
}
returnbOk;
}
运行结果
（四）极大极小方法求解井字棋
极大极小方法求解井字棋问题，对状态空间采用最大最小值搜索，计算机在生成的子节点中选择评估函数值最大的节点，而计算机在选择着数时使人选择评估函数值最小的节点，也就是对计算机一方最不利的节点。
本程序采用的核心算法是极大极小值算法，这种算法的思想是“考虑双方对弈若干步之后，从可能的走法中选一步相对较好的走法来走”，并且“在有限的搜索深度范围内进行求解”。
整个算法在AutoDone函数中实现，其实现过程分为以下几步：
（1）为了获得最优的落子位置，在算法中首先要生成搜索树。
其中，我把States[0]作为树根节点，根节点所在的层是极大层（MAX层），然后通过向棋盘中没有落子的空格添一个对方的棋子生成下一层（极小层，MIN层）的树节点，如果当前树的高度大于等于TREE_DEPTH（>=1）全局变量，则停止生成节点，否则则继续生成下一层节点（如果当前节点层为MIN层，则下一层为MAX层，否则，则下一层为MIN层）。
生成每一层时可为每一层的属性（MAX或MIN）做标记，生成每个节点时，应计算这个节点的评估函数值，并将其保存在状态节点的e_fun域中。
（2）因为层次遍历会修改非叶节点的极大极小值，而且非叶节点原来的极大极小值会对其来自其子女节点的极大极小值产生影响（比如，如果一个非叶节点的极大极小值大于或小于其子女节点中的最大者或小于其中的最小者，则导致其评估函数值无法更新）。
所以非叶节点没有必要也不能保存。
这一步的源代码如下所示：
tag=States[s_count].parent;//设置最底层标志，以区分叶节点和非叶节点。
for（i=0;i<=s_count;i++）{
if（i>tag）//保留叶节点的评估函数值{States[i].e_fun=e_fun（States[i]）;
}else//抹去非叶节点的评估函数值States[i].e_fun=NIL;}
（3）然后，通过层次遍历获得每个非叶节点的评估函数值，同时将非叶节点的
bestChild域指向最佳子女，从而形成一条从根节点到叶节点的最佳解路径。
这一步的
源代码如下所示：
while（!
IsOK）//寻找最佳落子的循环
{
for（inti=s_count;i>tag;i--）{
if（max_min）//取子女节点的最大值{
if（States[States[i].parent].e_fun{States[States[i].parent].e_fun=States[i].e_fun;//设置父母节点的最大最小值
States[States[i].parent].bestChild=i;//设置父母节点的最佳子女的下标
}}else//取子女节点的最小值{
if（States[States[i].parent].e_fun>States[i].e_fun||States[States[i].parent].e_fun==NIL）
{States[States[i].parent].e_fun=States[i].e_fun;//设置父母节点的最大最小值
States[States[i].parent].bestChild=i;//设置父母节点的最佳子女的下标}}}
s_count=tag;//将遍历的节点上移一层
max_min=!
max_min;//如果该层都是MAX节点，则它的上一层都是MIN节点，反之亦然。
if（States[s_count].parent!
=NIL）//如果当前遍历的层中不包含根节点，//则tag标志设为上一层的最后一个节点的下标
tag=States[s_count].parent;else
IsOK=true;//否则结束搜索}
（4）最后，将当前的棋局更新为其最优子女节点的棋局，并获得落子的位置。
这一步的源代码如下所示：
//取落子的位置，将x,y坐标保存在变量pos_x和pos_y中，//并将根（当前）节点中的棋局设为最佳子女节点的棋局for（intx=0;x<3;x++）{
for（inty=0;y<3;y++）{if（States[States[0].bestChild].QP[x][y]!
=States[0].QP[x][y]）{pos_x=x;pos_y=y;}
States[0].QP[x][y]=States[States[0].bestChild].QP[x][y];}}
运行结果
五、讨论与结论
同时通过这几次的实验，我对人工智能的一些思想以及应用有了更进一步的了解。
在实验期间，也遇到了很多困难，我通过在书本上查找答案以及询问周边的同学，希望能得到合理的答案，在大家的帮助下，解决了不少实验中的问题以及很多难以理解的理论和思想，不过还有很多地方自己和同学们都不是很了解，希望在今后的学习中能慢慢解决问题。
升级会员 