人工智能实验

1、人工智能导论实验河南理工大学人工智能实验指导实验内容实验一状态空间搜索实验实验二A*算法实验 实验三子句消解实验实验四化为子句集的九步法实验实验五梵塔问题实验实验六BP网络实验温馨提示：上述实验可以采用任何自己熟悉的语言来实现人工智能导论实验河南理工大学实验一状态空间搜索实验八数码问题（必修，2学时）一、实验目的及内容 实验目的：理解和掌握状态空间搜索的策略实验内容要求：在一个3X3的九宫中有1 8,这八个数及一个空格，随机的摆放在其中的格子 里，现要求实现这个问题：将该九宫格调整为某种有序的形式，调整的原则为每次只能将空格（上、下、 左、右）相邻的一个数字平移到空格中，试编程实现这一问题的求

2、解实验原理:二、实验原理及基本技术路线图（方框原理图或程序流程图） 算法分析： 实验流程图：硬件:三、所用仪器、材料（设备名称、型号、规格等或使用软件） 软件：四、实验方法、步骤（或：程序代码或操作过程）1. 实验步骤2. 实验源程序五、实验过程原始记录（测试数据、图表、计算等）六、实验结果、分析和结论人工智能导论实验河南理工大学1实验二A*算法实验（2学时）一、实验目的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。二、实验原理：A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序 搜索，总是选择f值最小的节点作为扩

3、展节点。因此，f是根据需要找到一条最小 代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。三、实验条件：1N数码难题演示程序。2 IE6.0 以上，可以上 Internet。号#*"flmtRrwt ritatB ««疥师卫亘Htl肄139114b72311 1214 8*106 15OTBFSB/ r 111； U，4 EI ? fhII I B"越LJU7：_m '阳&曲苗任L.書曲S尋0 -liM）肝时嘩旅JP T的节戶 DIOK 苗肚U5圧 ”雷工忖换

4、阳F1拆辛* * tgMfliF也脣币倒leu苗星,聊韋盘*皈声点員密啊'IH三、实验内容：1分别以8数码和15数码为例实际求解A*算法。2画出A*算法求解框图。3分析估价函数对搜索算法的影响。4分析A*算法的特点。四、实验步骤：1开始演示。进入N数码难题演示程序，可选8数码或者15数码，点击 选择数 码”按钮确定。第一次启动后，点击两次 缺省”或者 随机”按钮，才会出现图片。22点击缺省棋局”会产生一个固定的初始节点。点击 随机生成”会产生任意 排列的初始节点。3算法执行。点击 连续执行”则程序自动搜索求解，并演示每一步结果；点击 单 步运行”则每次执行一步求解流程。运行速度”可自由

5、调节。“154观察运行过程和搜索顺序，理解启发式搜索的原理。在下拉框中选择演示 数码难题”，点击 选择数码”确定选择；运行15数码难题演示实例。节点静5算法流程的任一时刻的相关状态，以算法流程高亮、open表、close表、 态图、A*算当前扩展节点移动图等5种形式在按钮上方同步显示，便于深入学习理解法。6根据程序运行过程画出A*算法框图。其它可参考帮助文件。五、实验报告要求：1 A*算法流程图和算法框图。2试分析估价函数的值对搜索算法速度的影响。根据A*算法分析启发式搜索的特点。3人工智能导论实验河南理工大学实验三子句消解实验（2学时）一、实验目的：理解含有变量的子句如何使用消解规则，掌握子

6、句消解的原理和规则，能熟练进 行任意两个子句的消解，了解消解推理的某些常用规则。二、实验原理：对子句集进行消解推理，得到相应的结论。为了对含有变量的子句使用消解规 则，我们必须找到一个置换，作用于父辈子句使其含有互补文字。消解两个子句 时，可能有一个以上的消解式，不过，在任何情况下最多有有限个消解式。三、实验条件1子句消解推理演示程序。2 IE6.0 以上，可以上 Internet。9 - MurwMfl I At rJ-rWl <n二出聖例灌示E 冥例a云31系绽重1电曹QfCd, vlVR(fCyl>四、实验内容：1运行并观察演示实例。2输入新的子句，检查消解结果。3根据消解过

7、程理解消解原理和常用规则。五、实验步骤：演示实例1”，然后点击 开始消解”，得1. 默认示例演示。进入演示实例，点击 到消解结果。2. 分别运行演示实例2”和演示实例3”，观察消解结果，理解常用消解规则的应4 用。Q”与 V，3. 自定义消解子句。点击 系统重置”按钮，再通过键盘与两个按钮 输入合法的子句，点击 加入子句集”加入子句集，点击开始消解”，观察消解结 果。4. 重复步骤3,多次输入不同子句进行消解，熟悉消解过程。六、实验结论：1熟悉消解过程，理解子句消解规则。2给出自己输入的待消解子句、消解结果和详细过程。5人工智能导论实验河南理工大学 实验四化为子句集的九步法实验（2学时）一、实

8、验目的：理解和掌握消解原理，熟悉谓词公式化为子句集的九个步骤，理解消解推理规 则，能把任意谓词公式转换成子句集。二、实验原理'消解是可用于一定的子句公式的重要推理规则，任一谓词演算公式可以化成一个 子句集。通过九步法消解可以从这两个父辈子句推导出一个新子句。九步法消解包括消去蕴涵符号、减否定符辖域、对变量标准化、消去存在量词、 化为前束型、化为合取范式、消去全程量词、消去合取符、更换变量名，依次变 换即可得到子句集。三、实验条件：1子句集转换演示程序。2 IE6.0 以上，可以上 Internet。aawffiwwftim 啪n未荷Hii曲片ntfr *： 古古 4ir:电近WMUi:

9、聆:二匚:J 旳迂Y处珂约哥二乂 Mf旷门三汀5 4代 疗: 帕于邨1节十:；L囲+：民门一卜7：甸憲E需应*古二*亡 己+ *心* *m j也:血"円川I州用代门Pu训用IWf r ； . Y :':甌* m；r 再刊:： : -I乂W：F 门般號西匚;；LdI3心;迟宀啲乂呼代叫）时尹化）1门Igy；Vr：XuhA 心，口）陶=：口C；川 rIf 二；沁：汽;忙E;.冷 5;: F口吐M冷Mi件賊;'匚巳J-一L - 心冶工LJ«耐4 I 20 'JI11 叵“二K 二JfeXf四、实验内容:理解消解原理，熟悉谓词公式转换成子句集的步骤。 五、实

10、验步骤：61对默认谓词公式进行转换。进入演示程序，点击 过语法检查” ”再依次点击消解程的九个步骤按钮，得到消解结果。2自定义消解目标。点击 清除”删除默认公式，利用界面键盘输入新的消解目 标，用大写字母”小写字母”按键进行输入中的字母变换。3语法检查。点击 语法检查”检查输入谓词公式的语法错误。如无错误，则依次 占八、击步骤按钮进行消解。4重复运行2、3步，熟悉消解原理和消解过程。六、实验报告要求：1了解每一步消解的规则和原则。2给出一个谓词公式消解的详细过程和结果。3分析消解原理的特点和原理。7人工智能导论实验河南理工大学实验五BP网络实验（4学时）一、实验目的：理解反向传播网络的结构和原

11、理，掌握反向传播算法对神经元的训练过程，了解 反向传播公式。通过构建BP网络实例，熟悉前馈网络的原理及结构。二、实验原理反向传播（BP）算法是一种计算单个权值变化引起网络性能变化值的较为简单的方 法。BP算法过程从输出节点开始，反向地向第一隐含层 （即最接近输入层的隐含 层）传播由总误差引起的权值修正。BP网络不仅含有输入节点和输出节点，而且 含有一层或多层隐（层）节点。输入信号先向前传递到隐节点，经过作用后，再把 隐节点的输出信息传递到输出节点，最后给出输出结果。三、实验条件：1 BP网络演示程序。2 IE5.0以上版本，能连通Internet。四、实验内容：1通过BP网络各项参数的不同设置

12、，观察 BP算法的学习效果。2观察比较BP网络各项参数变化对于训练结果的影响。五、实验步骤：1设置各层神经元个数设置。用户点击下拉列表框选择输入、隐含、输出各层神 经元个数，其中隐含层神经元个数自动设为输入层神经元个数（n）的2n+1个，然后再点击 确定”按钮，就可以看到所设置 BP神经网络示意图以及系统随机生成默认 的各层权值。2学习参数设置，用户点击或拖动各滚动条分别设置样本误差、系统误差、学习速率、动量因子、迭代次数参数值。3各层权值设置，如果用户使用系统随机生成默认的各层权值，则进行第机 l$«nE IhhOLU JIEI h II II I|儿-iJLiiJLILIIJIJ

13、iJUiLiaLII QCl I II 云吵广- If1 p TjIiItw« vyLlIU,叫 IDE咽口畤齐丁丿wJ-LiO. 1=0 耳总愛白THQTT怪Q宝N匚 w】cL W一I】 T; whii 1 . 口=a.口TT&33仝；31" I -LTL勺艺HHKT占I ?=Qi步。用户ILIULILIUIJMTE IT -1-3 seWlpTTr-II 卜肯h" V fDjr Lti 1.18或选中自定义权”单选框自定义权各层权，在权值设置文本域设置权值后，单击其后确定”按钮。或双击下方列表框选项，相应权值会在权值设置文本域出现,则进行该权值修改后，

14、单击其后 确定”按钮，修改后的权值会成功地列表框的原位修改。后两种方式均会成功地激活确定”按钮。4学习样本设置，单文本域中出现 入层”字样表示在单文本域中设置输入层神经信号向量。单文本域中出现 出层”字样表示在单文本域中设置输出层神经元信号向量。当输入已完成一个或一个以上模式对,已设置完”单选框会成功地激活,3的双击修改如选中，则 校正网络”按钮会成功地激活。样本列表框也具有如步 功能。5校正网络”按钮成功地激活后，单击 校正网络”按钮，进行网络学习。当学习 完成后，较正结果如下：”列表框显示校正学习后的结果，用户可通过察看习”是否满意。如满意，贝U设置测试样本，进行测试学习”效果。如不满意，

15、则可（重新设置初始权值、或学习样本等方式）让网络重新学习”六、实验结论：1 BP网络的基本结构及BP算法的训练过程。2试述阈值函数和权值变化对 BP网络推理结果的影响。9人工智能导论实验河南理工大学实验一状态空间搜索实验样例八数码问题一、实验目的及内容实验目的：理解和掌握状态空间搜索的策略实验内容要求：在一个3X3的九宫中有1 8,这八个数及一个空格，随机的摆放在其中的格子 里，现要求实现这个问题：将该九宫格调整为某种有序的形式，调整的原则为每次只能将空格(上、下、 左、右)相邻的一个数字平移到空格中，试编程实现这一问题的求解二、实验原理及基本技术路线图(方框原理图或程序流程图)实验原理：八数

16、码问题中，程序产生的随机排列转换成目标共有两种可能，而且这两种不可 能同时成立，也就是奇数排列和偶数排列。我们可以把一个随机排列的数组从左 到右从上到下用一个数组表示，例如8，7，1，5，2，6，3，4，0 其中0代表空格。它在奇序列位置上。在这个数组中我们首先计算它能够重排列 出来的结果，公式就是：X(F(X)=Y，其中F (X)，就是一个数他前 面比这个数小的数的个数，Y为奇数和偶数个有一种解法。那么上面的数组我们就可以解出它的结果。算法分析：九宫问题的求解方法就是交换空格(0)位置，直至到达目标位置为 止。图形表示就是：81151g34Hi1523CR=e7152£3A8115

17、234G因此可知：九宫的所以排列有9!种，也就是3 6 2 8 8 0种排法，数据量是非 常大的，我使用广度搜索，需要记住每一个结点的排列形式，要是用数组记录的 话会占用很多的内存，我们把数据进行适当的压缩。使用DWORD形式保存， 压缩形式是每个数字用3位表示，这样就是3 X9 = 2 7个字节，由于8的二进 制表示形式1 0 0 0,不能用3位表示，我使用了一个小技巧就是将8表示位0 0 0,然后用多出来的5个字表示8所在的位置，就可以用DWORD表示了。 用移位和或操作将数据逐个移入，比乘法速度要快点。定义了几个结10果来存储遍历到了结果和搜索完成后保存最优路径。实验流程图：台,软件：M

18、icrosoft Visual C+ 6.0四、实验方法、步骤（或：程序代码或操作过程）111. 实验步骤(1) 运行Microsoft Visual C+ 6.0软件，新建工作空间，得文档。(2) 输入源程序代码，进行编译，调试运行。(3) 运行结果，按提示要求输入1 8这八个数，进行程序测验。2. 实验源程序 #i nclude <stdio.h>#i nclude <stdlib.h>#i nclude vwin dows.h>#in clude <queue>#in clude <stack>using n ames pace st

19、d;#defi ne HashTableSize 362881#defi ne NOT !#defi ne UP 0#defi ne DOWN 1#defi ne LEFT 2#defi ne RIGHT 3#defi ne Bit chartyp edef struct mapsBit detail9;int myindex; /记录自己节点在hash表中的位置Bit position; /记录 空格（0）在序列中的位置Ma p,*P Ma p;Map org; II初始状态int EndIndex;目标上移，下移，左移，右移 int const derection4 = -3,3 , -1

20、 , 1 ;II可移动的四个方向in t co nst Factorial9 = 40320,5040,720 , 120,24,6,2 , 1 , 1 ;int HashTableHashTableSize=0;*/Ilhash表，其中记录的是上一个父节点对应的位置I*八数码的输入（在这里不做任何输入检查，均认为输入数据是正确的）void inp ut（）12int i,j;int sum , coun t ,i ndex ;for(i = 0 ; i < 9 ; i + )sca nf("%1d", & org.detail i );org.detail

21、i | (org. positi on = i);for(i = 0 ; i < 9 ; i + ) / 计算逆序if( 0 = org.detail i )con ti nue;for(j = 0 ; j < i; j + )sum += ( 0 != org.detail j && org.detail j < org.detail i ); for( i = 0 , index = 0 ; i < 9 ; i + ) / 计算初始状态的 hash值for(j = 0 , count = 0 ; j < i ; j +)count += org

22、.detail j > org.detail i ;in dex += Factorial org.detail i * count;org.m yin dex = in dex + 1 ;EndIndex = sum%2 ? 161328:322561; 目标状态的 hash值 return;/*hash值的计算*Parent:父状态的hash值*direct:移动的方向*/in li ne int HashValue(Ma p& Paren t , i nt& direct )int i = Paren t. po siti on ;int newin dex = P

23、aren t.myi ndex ;Bit *p = Paren t.detail;switch(direct)case UP :n ewi ndex -= 3*40320 ;n ewi ndex += ( p i - 2 > p i - 3 ) ? ( Factorial p i - 3 ) : ( - Factorial p i - 2 ); n ewi ndex += ( p i - 1 > p i - 3 ) ? ( Factorial p i - 3 ) : ( - Factorial p i - 1 ); 13break;case DOWN :n ewi ndex +=

24、3*40320 ;n ewi ndex -= ( p i + 2 > p i + 3 ) ? ( Factorial p i + 3 ) : (- Factorial p i + 2 ); n ewi ndex -= ( p i + 1 > p i + 3 ) ? ( Factorial p i + 3 ) : ( - Factorial p i + 1 ); break;case LEFT : retur n newin dex - 40320; break;case RIGHT : return newi ndex + 40320; break;retur n newin de

25、x;/* * *宽度优先搜索*/ void Bfs()queuevMa p> Queue;Queue .pu sh(org);HashTable org.m yin dex = -1;while( NOT Queue.e mp ty()Map node = Queue.fro nt();Queue .pop();for(i nt k =0 ; k < 4; k + )Map tmp = no de;tmp.po siti on = node.p ositi on + derecti on k;if(tmp.p ositi on < 0 | tmp.p ositi on >

26、; 8 | ( k > 1 && tmp.po siti on / 3 != node.p ositi on /3 )con ti nue;tmp.myin dex = HashValue( node , k );if(0 != HashTablet mp.myin dex ) continue;tmp .detail node.p ositi on = tmp .detail tmp.po siti on ; / 移动空格tmp .detail tmp.p ositi on = 0 ;HashTabletmp.myindex = node.myindex; / 状态记录

27、至U hashtable中if( no de.m yin dex = EndIn dex ) retur n ;Queue .pu sh( tmp );14return ;/*通过hash表中记录的进行查找路径*/ void FindP ath()int nowin dex;int count =0 ;int nixu9, result9;int i, j , k ;stack< int> Stack;Stack .p ush(E ndln dex);nowin dex = EndIn dex;while( -1 != HashTable nowin dex )Stack .p u

28、sh(HashTable nowin dex ); nowin dex = HashTable nowin dex ;printf("共需：%d 步 n",Stack.size()-1); getchar();while( NOT Stack.e mp ty()nowin dex = Stack.t op() - 1 ;Stack .pop();for( i = 0 ; i < 9; i + ) / 计算出逆序ni xui = nowin dex / Factorial i ;nowin dex %= Factorial i ;memset( result , -1 , 9 *sizeof(i nt);for( i =0 ; i < 9 ; i + ) /根据逆序计算排列 for( j = 0 , k = n ixui ; j < 9 ; j + )if(resultj = -1 ) k -;if( k < 0 ) break; result = i ;for( i =0 ; i < 9 ; i + )15prin tf("%3d",resulti);i