人工智能实验内容

上传者：陈兆琪
|
上传时间：2015-05-07
|
密次下载

人工智能实验内容

实验1 梵塔问题实验

一、实验目的：

熟悉和掌握问题规约法的原理、实质和规约过程；理解规约图的表示方法。

二、实验原理

从目标(要解决的问题)出发逆向推理，先把问题分解为子问题和子-子问题，直至最后把初始问题归约为一个平凡的本原问题集合，然后解决较小的问题。对所有本原问题的解答就意味着原始问题的解决。

三、实验软件：

VC6.0 编程语言或其它编程语言

四、实验内容：

1. 分析归约机理，熟悉问题规约的详细过程。

2. 自己建造一个梵塔问题归约系统，然后根据归约原理进行逆向推理，得到本原问题集合。通过解决这些本原问题，最终求解问题。

五、实验结论：

1. 圆盘数目与移动步骤之间的数学关系。

2. 根据自己所建梵塔问题，画出问题规约图，得到子问题集，列出求解过程。 3. 分析问题规约的实质。

实验2 八数码问题求解

一、实验要求

采用A*算法求解八数码问题。

二、实验软件

VC6.0 编程语言或其它编程语言

三、实验目的

1. 熟悉人工智能系统中的问题求解过程；

2. 熟悉启发式搜索算法的应用；

3. 熟悉对八数码问题的建模、求解及编程语言的应用。

四、实验内容

八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

2 8 3 1 2 3

1 4 8 4

7 6 5 7 6 5

(a) 初始状态 (b) 目标状态

图 1 八数码问题示意图

采用A*算法编程实现。

实验3 利用遗传算法解决TSP问题

1. 实验目的

利用遗传算法获得TSP问题的近似解。

2. 实验要求

要求学生了解遗传算法解决问题的基本流程。对TSP问题有所了解,知道TSP问题的难点在什么地方,如何使用遗传算法来获得一个较好的近似解。

3. 实验内容

已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij) 是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。

实验4 化为子句集的九步法实验

一、实验目的

理解和掌握消解原理，熟悉谓词公式化为子句集的九个步骤，理解消解推理规则，能把任意谓词公式转换成子句集。

二、实验原理

消解是可用于一定的子句公式的重要推理规则，任一谓词演算公式可以化成一个子句集。通过九步法消解可以从这两个父辈子句推导出一个新子句。九步法消解包括消去蕴涵符号、减否定符辖域、对变量标准化、消去存在量词、化为前束型、化为合取范式、消去全程量词、消去合取符、更换变量名，依次变换即可得到子句集。

具体为：

（1）消去连接词“→”和“?” P→Q?﹁P∨QP?Q?(P∧Q)∨(﹁P∧﹁Q)

（2）将否定符号“﹁”移到仅靠谓词的位置﹁(﹁P)?P ﹁(P∧Q)?﹁P∨﹁Q ﹁(P∨Q)?﹁P∧﹁Q ﹁(?x)P(x)?(?x)﹁P(x) ﹁(?x)P(x)?(?x)﹁P(x) (?x)(﹁(?y)P(x,y)∨﹁(?y)(﹁Q(x,y)∨R(x,y)))?(?x)((?y)﹁P(x,y)∨(?y)(Q(x,y)∧﹁R(x,y)))

（3）对变元标准化 (?x)((?y)﹁P(x,y)∨(?z)(Q(x,z)∧﹁R(x,z)))

（4）化为前束范式 (?x)(?y)(?z)(﹁P(x,y)∨(Q(x,z)∧﹁R(x,z)))

（5）消去存在量词 (?x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))

（6）化为Skolem标准形P∨(Q∧R)?(P∨Q)∧(P∨R) (?x)((﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x))))

（7）消去全称量词 (?x)((﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x))))

（8）消去合取词﹁P(x,f(x))∨Q(x,g(x)) ﹁P(x,f(x))∨﹁R(x,g(x))

（9）更换变量名称﹁P(x,f(x))∨Q(x,g(x)) ﹁P(y,f(y))∨﹁R(y,g(y))

三、实验内容

（1）可以采用自己熟悉的C#、C++、JAVA等任一种语言编写出Windows应

用程序，演示子句消解推理演示程序。

（2）界面中可以通过实例按钮，由程序指定具体的实例，给出原始谓词公式；

（3）设计九个步骤的按钮，每按一步按钮，给出这一步消解的结果；