八数码问题人工智能实验报告

基于人工智能的状态空间搜索策略研究

――八数码问题求解

（一）实验软件

或编程语言或其它编程语言

（二）实验目的

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

2.熟悉状态空间的盲目搜索和启发式搜索算法的应用；

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

（三）需要的预备知识

1.熟悉或编程语言或者其它编程语言；

2.熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法；

3.熟悉计算机语言对常用数据结构如链表、队列等的描述应用；

4.熟悉计算机常用人机接口设计。

（四）实验数据及步骤

1.实验内容

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

图八数码问题示意图

请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或任选一种启发式搜索方法（A算法或A*算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。

2. 实验步骤

（1）分析算法基本原理和基本流程；

程序采用宽度优先搜索算法，基本流程如下：

(2)确定对问题描述的基本数据结构，如Open表和Closed表等;

(3)编写算符运算、目标比较等函数；

(4)编写输入、输出接口；

(5)全部模块联调；

(6)撰写实验报告。

(五)实验报告要求

所撰写的实验报告必须包含以下内容：

1.算法基本原理和流程框图；

2.基本数据结构分析和实现；

3.编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功能、输入输出参数意义和与其它模块联系等；

4.程序运行结果，含使用的搜索算法及搜索路径等；

5.实验结果分析；

6.结论；

7. 提供全部源程序及软件的可执行程序。

附：实验报告格式

一、实验问题

二、实验目的

三、实验原理

四、程序框图

五、实验结果及分析

六、结论

八数码问题求解--实验报告讲解

实验报告 一、实验问题 八数码问题求解 二、实验软件 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 八数码问题示意图 （二、）基本数据结构分析和实现 1.结点状态 我采用了struct Node数据类型 typedef struct _Node{

int digit[ROW][COL]; int dist; // distance between one state and the destination一 个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置 } Node; 2.发生器函数 定义的发生器函数由以下的四种操作组成： (1)将当前状态的空格上移 Node node_up; Assign(node_up, index);//向上扩展的节点 int dist_up = MAXDISTANCE; (2)将当前状态的空格下移 Node node_down; Assign(node_down, index);//向下扩展的节点 int dist_down = MAXDISTANCE; (3)将当前状态的空格左移 Node node_left; Assign(node_left, index);//向左扩展的节点 int dist_left = MAXDISTANCE; (4)将当前状态的空格右移 Node node_right; Assign(node_right, index);//向右扩展的节点 int dist_right = MAXDISTANCE; 通过定义结点状态和发生器函数，就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。 3.图的搜索策略 经过分析，8数码问题中可采用的搜速策略共有：1.广度优先搜索、2.深度优先搜索、2.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。 实验时,采用了广度(宽度)优先搜索来实现。 （三、）广度(宽度)优先搜索原理 1. 状态空间盲目搜索——宽度优先搜索 其基本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。其搜索过程如图（1）所示。

八数码问题人工智能实验报告

基于人工智能的状态空间搜索策略研究 ——八数码问题求解 （一）实验软件 TC2.0 或VC6.0编程语言或其它编程语言 （二）实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 （三）需要的预备知识 1. 熟悉TC 2.0或VC6.0 编程语言或者其它编程语言； 2. 熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法； 3. 熟悉计算机语言对常用数据结构如链表、队列等的描述应用； 4. 熟悉计算机常用人机接口设计。 （四）实验数据及步骤 1. 实验内容 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 图1 八数码问题示意图 请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或任选一种启发式搜索方法（A 算法或A* 算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。 2. 实验步骤 （1）分析算法基本原理和基本流程； 程序采用宽度优先搜索算法，基本流程如下：

（2）确定对问题描述的基本数据结构，如Open表和Closed表等；

（3）编写算符运算、目标比较等函数； （4）编写输入、输出接口； （5）全部模块联调； （6）撰写实验报告。 （五）实验报告要求 所撰写的实验报告必须包含以下内容： 1. 算法基本原理和流程框图； 2. 基本数据结构分析和实现； 3. 编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功能、输入输出参数意义和与其它模块联系等； 4. 程序运行结果，含使用的搜索算法及搜索路径等； 5. 实验结果分析； 6. 结论； 7. 提供全部源程序及软件的可执行程序。 附：实验报告格式 一、实验问题 二、实验目的 三、实验原理 四、程序框图 五、实验结果及分析 六、结论

A星算法求八数码问题试验报告

人工智能实验报告实验名称：八数码问题 姓名：xx 学号：2012210xx xx计算机学院

2014年1月14日 一．实验目的． 的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一掌握A* 个状态转为另状态的路径。 二．实验内容且要求在有限步的操作内，使其转化为目标状态，给定九宫 格的初始状态，并打印出求解路径。例如(即移动的步数最少)所得到的解是代 价最小解 3 8 2 4 6 1 5 0 7 3 2 8 4 6 1 5 0 7 A*三、算法思想：1、思想：估价值与实际A*算法是一种静态路网中求 解最短路最有效的直接搜索方法。值越接近，估价函数取得就越好、原理：2 f(n)=g(n)+h(n), 估价函数公式表示为：是在状态空g(n) 是从初始点经由节点n到目标点的估价函数，其中 f(n) 到目标节点最佳路径的估计nh(n) 是从间中从初始节点到n节点的实际代价，h(n)的选取：代价。保证找到最短路径（最优解的）条件，关键在于估价函数到目标节点的距离实际值，这种情况下，搜索的点数多，搜索估价值h(n)<= n等于h(n)范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计如

果估那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。最短距离， ,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。价值>实际值 四、算法流程：

1、使用了CreateChild（）函数，求得了任意未拓展九宫格的扩展结点，便于拓展子空间，搜索所有情况。 关键代码： bool CreateChild(NOExtend ns[],NOExtend ne){

人工智能原理及其应用(王万森)第3版 课后习题答案

第1章人工智能概述课后题答案 1.1什么是智能?智能包含哪几种能力？ 解：智能主要是指人类的自然智能。一般认为，智能是是一种认识客观事物和运用知识解决问题的综合能力。 智能包含感知能力，记忆与思维能力，学习和自适应能力，行为能力 1.2人类有哪几种思维方式?各有什么特点？ 解：人类思维方式有形象思维、抽象思维和灵感思维 形象思维也称直感思维，是一种基于形象概念，根据感性形象认识材料，对客观对象进行处理的一种思维方式。 抽象思维也称逻辑思维，是一种基于抽象概念，根据逻辑规则对信息或知识进行处理的理性思维形式。 灵感思维也称顿悟思维，是一种显意识与潜意识相互作用的思维方式。 1.3什么是人工智能?它的研究目标是什么？ 解：从能力的角度讲，人工智能是指用人工的方法在机器（计算机）上实现智能；从学科的角度看，人工智能是一门研究如何构造智能机器或智能系统，使它能模拟、延伸和扩展人类智能的学科。 研究目标： 对智能行为有效解释的理论分析； 解释人类智能； 构造具有智能的人工产品； 1.4什么是图灵实验？图灵实验说明了什么？ 解：图灵实验可描述如下，该实验的参加者由一位测试主持人和两个被测试对象组成。其中，两个被测试对象中一个是人，另一个是机器。测试规则为：测试主持人和每个被测试对象分别位于彼此不能看见的房间中，相互之间只能通过计算机终端进行会话。测试开始后，由测试主持人向被测试对象提出各种具有智能性的问题，但不能询问测试者的物理特征。被测试对象在回答问题时,都应尽量使测试者相信自己是“人”，而另一位是”机器”。在这个前提下，要求测试主持人区分这两个被测试对象中哪个是人，哪个是机器。如果无论如何更换测试主持人和被测试对象的人，测试主持人总能分辨出人和机器的概率都小于50%，则认为该机器具有了智能。 1.5人工智能的发展经历了哪几个阶段？ 解：孕育期，形成期，知识应用期，从学派分立走向综合，智能科学技术学科的兴起

八数码问题C语言A星算法详细实验报告含代码

一、实验内容和要求 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如： [ (a) 初始状态 (b) 目标状态 图1 八数码问题示意图 请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A 算法或 A* 算法）编程求解八数码问题（初始状态任选）。选择一个初始状态，画出搜索树，填写相应的OPEN 表和CLOSED表，给出解路径，对实验结果进行分析总结，得出结论。 二、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； % 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 三、实验算法 A*算法是一种常用的启发式搜索算法。 在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为： f'(n) = g'(n) + h'(n) 这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数： f(n) = g(n) + h(n) 其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已

知的。用f(n)作为f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。这样必须满足两个条件：（1）g(n)>=g'(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。 *算法的步骤 A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。 A*算法的步骤如下： & 1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。 2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。 3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。 4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。 5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。 四、程序框图

八数码实验报告人工智能课设报告

学生实验报告 实验课名称：人工智能 实验名称: 八数码 专业名称：计算机科学与技术 班级： 学号： 学生姓名： 教师姓名： 2010 年10 月20日 一．实验内容 用OPEN表和CLOSED表解决搜索问题。 二．实验题目 采用启发式算法（如A*算法）求解八数码问题。 三．实验要求 1.必须使用OPEN表和CLOSED表。 2.明确给出问题描述。系统初始状态。目标状态和启发式函数。 3.除了初始状态以外，至少搜索四层。 4.给出解路径（解图）。 四．实验过程 ①问题：初始状态到目标状态是否可解如何判断？ 答：实验过程自己给出的初始状态使用A*算法求解，并不是所有的初始状态都可解到达目标状态。因为八数码问题其实是0~9的一个排列，而排列有奇排列和偶排列，从奇排列不能转化为偶排列或者相反。例如：函数f(s)表示s前比s 小的数字的数目（s 则当f(a8)+f(a7)+……+f(a1)为偶数时才能重排成，所以嘛,上面那个有解的. ②问题描述： 在3X3的九宫格棋盘上，摆有8个将牌，每一个将牌都刻有1~8数码中的某一个数码。棋盘中留有一个空格，允许周围的某一个将牌向空格移动，这样通过移动将牌就可以不断地改变将牌的布局。这种游戏的求解的问题是：给定一种处

世的将牌布局或结构和一个目标的布局，问如何移动将牌，实现从从初始状态到目标状态的转变。 下面给出初始状态和目标状态： 初始状态：Array 目标状态： 评价函数f(n)形式为：f(n)=g(n)+h(n),其中g(n)是节点所处的深度， h(n)是启发式函数，这里启发式函数h(n)表示“不在位”的将牌个数，这时f(n) 注意：移动规则为左-→上→右→下。 ③搜索过程： 因此可得解路径：S(4)→B(4)→D(5)→E(5)→I(5)→K(5)→L(5). ④得到OPEN表和CLOSED表 OPEN表

八数码问题C语言A星算法详细实验报告含代码

八数码问题C语言A星算法详细实验报告含代 码 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】

一、实验内容和要求 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如： (a) 初始状态 (b) 目标状态 图1 八数码问题示意图 请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A 算法或 A* 算法）编程求解八数码问题（初始状态任选）。选择一个初始状态，画出搜索树，填写相应的OPEN表和CLOSED表，给出解路径，对实验结果进行分析总结，得出结论。 二、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 三、实验算法 A*算法是一种常用的启发式搜索算法。 在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为： f'(n) = g'(n) + h'(n)

这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数： f(n) = g(n) + h(n) 其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。用f(n)作为f'(n)的近似，也就是用g(n)代替 g'(n)，h(n)代替h'(n)。这样必须满足两个条件：（1）g(n)>=g'(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费 h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。 *算法的步骤 A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。 A*算法的步骤如下： 1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。

人工智能 八数码实验

人工智能作业八数码问题

一、题目 八数码问题： 初始状态图：目标状态图： 二、算符与状态空间 算符：左、上、右、下 状态空间： 状态：A=(X0,X1,X2,X3,X4,X5,X6,X7,X8) 初始状态：S0=(0,4,1,5,2,8,3,6,7); 目标状态：Sg=(0,1,7,5,2,8,3,6,4)。

三、搜索树 22 求解: 四、Open 表，Closed 表 Open 表： Closed 表：

五、程序代码 /* 3_13.pro eight puzzle */ trace DOMAINS state=st(in,in,in,in,in,in,in,in,in) in=integer DATABASE-mydatabase open(state,integer) closed(integer,state,integer) res(state) mark(state) fail_ PREDICATES solve search(state,state) result searching step4(integer,state) step56(integer,state) equal(state,state) repeat resulting(integer) rule(state,state) GOAL solve. CLAUSES solve:-search(st(0,4,1,5,2,8,3,6,7),st(0,1,7,5,2,8,3,6,4)),result. search(Begin,End):-retractall(_,mydatabase), assert(closed(0,Begin,0)),assert(open(Begin,0)),

A星算法求八数码问题实验报告

人工智能实验报告 实验名称：八数码问题 姓名：xx 学号：2012210xx xx计算机学院 2014年1月14日

一．实验目的 掌握A*的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一个状态转为另状态的路径。 二．实验内容 给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)并打印出求解路径。例如 2 8 3 1 6 4 7 0 5 2 8 3 1 6 4 7 0 5 三、A*算法思想： 1、思想： A*算法是一种静态路网中求解最短路最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好 2、原理： 估价函数公式表示为： f(n)=g(n)+h(n), 其中 f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。如果估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

四、算法流程： 是 是，输出路径 否，生成n 的所有子状态 Heuristic_Search(启发式搜索) While （未拓展表不为空？） 从未拓展表中删除第一个状态n N 为目标状态？ Case:此子状态 不在拓展表和 未拓展表中 Case:此子状态在未拓展表中 Case:此子状态在拓展表 计算该子状态的估价函数值； 记录比已有的路径更短 的路径 记录比已有的路径更短的路径 返回

人工智能原理与应用_(张仰森_著)_高等教育出版社_课后答案

2.7解：根据谓词知识表示的步骤求解问题如下： 解法一： (1)本问题涉及的常量定义为： 猴子：Monkey，箱子：Box，香蕉：Banana，位置：a，b，c (2)定义谓词如下： SITE(x，y)：表示x在y处； HANG(x，y)：表示x悬挂在y处； ON(x，y)：表示x站在y上； HOLDS(y，w)：表示y手里拿着w。 (3)根据问题的描述将问题的初始状态和目标状态分别用谓词公式表示如下： 问题的初始状态表示： SITE(Monkey，a)∧HANG(Banana，b)∧SITE(Box，c)∧~ON(Monkey，Box)∧~HOLDS(Monkey，Banana) 问题的目标状态表示： SITE(Monkey，b)∧~HANG(Banana，b)∧SITE(Box，b) ∧ON(Monkey，Box)∧HOLDS(Monkey，Banana) 解法二： (1)本问题涉及的常量定义为： 猴子：Monkey，箱子：Box，香蕉：Banana，位置：a，b，c (2)定义谓词如下： SITE(x，y)：表示x在y处； ONBOX(x)：表示x站在箱子顶上； HOLDS(x)：表示x摘到了香蕉。 (3)根据问题的描述将问题的初始状态和目标状态分别用谓词公式表示如下： 问题的初始状态表示： SITE(Monkey，a)∧SITE(Box，c)∧~ONBOX(Monkey)∧~HOLDS(Monkey) 问题的目标状态表示： SITE(Box，b)∧SITE(Monkey，b)∧ONBOX(Monkey)∧HOLDS(Monkey) 从上述两种解法可以看出，只要谓词定义不同，问题的初始状态和目标状态就不同。所以，对于同样的知识，不同的人的表示结果可能不同。 2.8解：本问题的关键就是制定一组操作，将初始状态转换为目标状态。为了用谓词公式表示操作，可将操作分为条件(为完成相应操作所必须具备的条件)和动作两部分。条件易于用谓词公式表示，而动作则可通过执行该动作前后的状态变化表示出来，即由于动作的执行，当前状态中删去了某些谓词公式而又增加一些谓词公式从而得到了新的状态，通过这种不同状态中谓词公式的增、减来描述动作。 定义四个操作的谓词如下，操作的条件和动作可用谓词公式的增、删表示： (1)goto

八数码问题实验报告讲解

《八数码问题》实验报告 一、实验目的： 熟练掌握启发式搜索A *算法。 二、实验内容： 使用启发式搜索算法求解8数码问题。编制程序实现求解8数码问题A *算法，采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 三、实验原理： 1. 问题描述： 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 原理描述： 启发式搜索 （1）原理 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 （2）估价函数

计算一个节点的估价函数，可以分成两个部分： 1、 已经付出的代价（起始节点到当前节点）； 2、 将要付出的代价（当前节点到目标节点）。 节点n 的估价函数)(n f 定义为从初始节点、经过n 、到达目标节点的路径的最小代价 的估计值，即)(* n f = )(* n g + )(* n h 。 )(*n g 是从初始节点到达当前节点n 的实际代价； )(*n h 是从节点n 到目标节点的最佳路径的估计代价。 )(*n g 所占的比重越大，越趋向于宽度优先或等代价搜索；反之，)(*n h 的比重越大， 表示启发性能就越强。 （3）算法描述： ① 把起始节点S 放到OPEN 表中，并计算节点S 的)(S f ； ② 如果OPEN 是空表，则失败退出，无解； ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同，当其中有一个 为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ； ④ 把节点i 从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中； ⑤ 如果i 是个目标节点，则成功退出，求得一个解； ⑥ 扩展节点i ，生成其全部后继节点。对于i 的每一个后继节点j ： 计算)(j f ；如果j 既不在OPEN 表中，又不在CLOCED 表中，则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针，以便一旦找到目标节点时记住一个解答路径；如果j 已在OPEN 表或CLOSED 表中，则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小，则 (I)以此新值取代旧值。 (II)从j 指向i ，而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中，则把它移回OPEN 表中。 ⑦ 转向②，即GOTO ②。 （3）算法流程图：

人工智能试验-八数码难题

昆明理工大学信息工程与自动化学院学生实验报告 （2012 —2013 学年第 1 学期） 课程名称：人工智能开课实验室：信自楼442 2012 年10月 24日 一、上机目的及内容 1.上机内容 用确定性推理算法求解教材65-66页介绍的八数码难题。 2.上机目的 （1）复习程序设计和数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并实现在小规模状态空间中进行图搜索的方法； （3）理解并掌握图搜索的技术要点。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）设计并实现程序，求解出正确的解答路径； （2）对所设计的算法采用大O符号进行时间复杂性和空间复杂性分析； （3）对一般图搜索的技术要点和技术难点进行评述性分析。 问题描述： 在3×3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以 不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状 态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。 初始状态：8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中，状态空间中的任一种状态都可以作为初始状态。 后继函数： 通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。 目标测试： 比较当前状态和目标状态的格局是否一致。 路径消耗： 每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。

三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 数据结构 static int target[9]={1,2,3,8,0,4,7,6,5}; 全局静态变量，表示目标状态class eight_num { private: int num[9]; 定义八数码的初始状态 int not_in_position_num; 定义不在正确位置八数码的个数 int deapth; 定义了搜索的深度 int eva_function; 评价函数的值，每次选取最小的进行扩展public:

人工智能实验八数码问题的求解策略

人工智能上机实验二八数码问题的求解策略1、广度优先算法程序截图： 2、最佳优先算法程序截图：

（接上图） 3、程序代码： ①广度优先算法： (defun init-search (start goal) (declare (special *open*)) (declare (special *closed*)) (declare (special *moves*)) (declare (special *start*)) (declare (special *goal*)) (let (tuple) (setq tuple (cons start '(nil)) ) (setq *open* (list tuple) ) (setq *closed* nil ) (setq *start* start) (setq *goal* goal) (setq *moves* '(blank-left blank-up blank-right blank-down)) (breadth-first-search))) (defun breadth-first-search () (declare (special *open*)) (declare (special *closed*)) (declare (special *goal*)) (declare (special *moves*)) (let (state tuple children path) (cond ((null *open*) 'FAIL!) (t (setq tuple (car *open*) ) (setq state (car tuple) ) (setq *open* (cdr *open*) ) (setq *closed* (cons tuple *closed*)) (cond ((equal state *goal*) (setq path (get-path-from *goal*)) (setq path (reverse path)) (print-path path)

人工智能八数码游戏

实验一：八数码游戏问题 一、八数码游戏问题简介 九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。问题是在3×3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。 问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。 （a）初始状态（b）目标状态 图八数码游戏 二、实验目的 1.熟悉人工智能系统中的问题求解过程； 2.熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3.熟悉对八数码问题的建模、求解及编程语言的应用。 三、实验的思路 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如：

图1 八数码问题示意图 1.启发函数设定 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索范围，提高搜索速度。 2.搜索过程：（搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）） a、把初始数码组压入队列； b、从队列中取出一个数码组节点； c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点： d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其父节点加一，是则将其压入队，否则抛弃。 e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成，

人工智能实验报告,包括八数码问题八皇后问题和tsp问题

八数码问题 （一）问题描述 在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。 （二）问题分析 八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。 1、启发式搜索 由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。 启发函数设定。对于八数码问题，可以利用棋局差距作为一个度量。搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。 （三）数据结构与算法设计 该搜索为一个搜索树。为了简化问题，搜索树节点设计如下： struct Chess//棋盘 {

int cell[N][N];//数码数组 int Value;//评估值 Direction BelockDirec;//所屏蔽方向 struct Chess * Parent;//父节点 }; int cell[N][N]; 数码数组：记录棋局数码摆放状态。 int Value; 评估值：记录与目标棋局差距的度量值。 Direction BelockDirec; 所屏蔽方向：一个屏蔽方向，防止回推。 Direction ：enum Direction{None,Up,Down,Left,Right};//方向枚举 struct Chess * Parent; 父节点：指向父亲节点。 下一步可以通过启发搜索算法构造搜索树。 1、局部搜索树样例：

八数码实验报告

利用人工智能技术解决八数码游戏问题 1．八数码游戏问题简介 九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。问题是在 3×3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。 2．八数码游戏问题的状态空间法表示 ①建立一个只含有初始节点s0的搜索图g，把s0放入open表中 ②建立closed表，且置为空表 ③判断open表是否为空表，若为空，则问题无解，退出 ④选择open表中的第一个节点，把它从open表移出，并放入closed表中，将此节点记为节点n ⑤考察节点n是否为目标节点，若是，则问题有解，成功退出。问题的解就是沿着n到s0的路径得到。若不是转⑥ ⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合m，将m中的这些节点作为n的后继节点加入图g中 ⑦对未在g中出现过的（open和closed表中未出现过的）集合m中的节点, 设置一个指向父节点n的指针，并把这些节点放入open表中；对于已在g中出现过的m中的节点，确定是否需要修改指向父节点的指针；对于已在g中出现过并已在closed表中的m中的节点，确定是否需要修改通向他们后继节点的指针。 ⑧按某一任意方式或某种策略重排open表中节点的顺序 ⑨转③ 3．八数码游戏问题的盲目搜索技术 宽度优先搜索： 1、定义 如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-first search)。 2、特点 这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。 3、宽度优先搜索算法 (1) 把起始节点放到open表中(如果该起始节点为一目标节点，则求得一个解答)。 (2) 如果open是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从open表移出，并把它放入closed的扩展节点表中。 (4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。 (5) 把n的所有后继节点放到open表末端，并提供从这些后继节点回到n的指针。 (6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。 流程图： 性质： 当问题有解时，一定能找到解。 当问题为单位消耗值，且问题有解时，一定能找到最优解。 算法与问题无关，具有通用性。 时间效率和空间效率都比较低。 深度优先搜索：

人工智能十五数码实验报告

目录 1 实验概述 (2) 2 十五数码问题分析 (2) 2.1十五数码问题简介 (2) 2.2可行性分析 (3) 3问题的求解策略 (3) 3.1算法分析 (3) 3.2 A*算法设计 (4) 4 实验总结 (5) 4.1 实验可视化界面 (5) 4.2个人体会 (6) 4.3 详细代码： (7)

1 实验概述 十五数码问题来源于美国的科学魔术大师萨姆.洛伊德（Sam I.oyd）在1978年推出的著名的“14-15”智力玩具。这个游戏曾经风靡欧美大陆" 。洛伊德的发明其实只是将重排九宫（即八数码问题）中的3阶方阵扩大到4 阶方阵罢了。由于这个细微的变化，十五数码问题的规模远远大于八数码问题，八数码问题的规模较小，总的状态数为9！（=362880）个，而十五数码问题的状态,数为16！（）个。故十五数码问题更能评价一个算法的“智能”水平。 2 十五数码问题分析 2.1十五数码问题简介 15数码问题又叫移棋盘问题，是人工智能中的一个经典问题。所谓的15数码问题：就是在一个4×4的16宫格棋盘上，摆放有15个将牌，每一个将牌都刻有1～15中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种求解的问题是：给定一种初始的将牌布局或结构(称初始状态)和一个目标布局(称目标状态)，问如何移动数码，实现从初始状态到目标状态的转变，如下图所示。问题的实质就是寻找一个合法的动作序列

2.2可行性分析 十五数码问题存在无解的情况,当遍历完所有可扩展的状态也没有搜索到目标状态就判断为无解。可以根据状态的逆序数来先验的判断是否有解,当初始状态的逆序数和目标状态的逆序数的奇偶性相同时,问题有解；否则问题无解。状态的逆序数是定义如下：把四行数展开排成一行,并且丢弃数字0 不计入其中,ηi是第i 个数之前比该数小的数字的个数,则η=Σηi 是该状态的逆序数,例如：对于初始状态：5、1、2、4、9、6、3、8、13、15、10、11、14、7、12.其η=0+0+1+2+4+4+2+6+8+9+8+9+11+6+11=81；对于目标状态：1、2、3、4、5、6、7、8、9、10、11、12、13、14、15，其η=0+1+2+3+4+5+6+7+8+9+10+11+12+13+14=105。初始状态和目标状态的奇偶性相同，故存在解路径。 3问题的求解策略 3.1算法分析 十五数码问题的解空间树属排列树，用于排列树搜索的方法主要有两大类：一类是盲目搜索，如深度优先搜索DFS 和广度优先搜索BFS；另一类是启发式搜索，如A* 算法。 对于十五数码问题，深度优先搜索的状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。应用此策略很可能得不到解。宽度优先搜索的优势在于当问题有解时，一定能找到解，且能找到最优解。但其搜索时需要保存所有的待扩展结点，这样很容易扩展那些没有用的结点，造成状态的指数增长，甚至“组合爆炸”。这对宽度优先搜索很不利。这两种搜索方法的共同缺点是结点排序杂乱无章，往往在搜索了大量无关结点后才能得到目的结点，只适合于复杂度较低的问题的求解。 启发式搜索利用特定问题自身所携带的启发信息在一定程度上避免了盲目搜索的不足，适合于解决十五数码问题。其核心思想是引入一个启发式函数（或称为评估函数）利用评估函数为生成的结点估值%并按估值的大小对结点进行排

关于人工智能实验报告

****大学 人工智能基础课程实验报告 （2011-2012学年第一学期） 启发式搜索王浩算法 班级： *********** 学号： ********** 姓名： ****** 指导教师： ****** 成绩： 2012年 1 月 10 日

实验一 启发式搜索算法 1. 实验内容： 使用启发式搜索算法求解8数码问题。 ⑴ 编制程序实现求解8数码问题A *算法，采用估价函数 ()()()() w n f n d n p n ??=+???， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 ⑵ 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()p n 的上界的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。 2. 实验目的 熟练掌握启发式搜索A *算法及其可采纳性。 3. 实验原理 使用启发式信息知道搜索过程，可以在较大的程度上提高搜索算法的时间效率和空间效率； 启发式搜索的效率在于启发式函数的优劣，在启发式函数构造不好的情况下，甚至在存在解的情形下也可能导致解丢失的现象或者找不到最优解，所以构造一个优秀的启发式函数是前提条件。 4.实验内容 1.问题描述 在一个3*3的九宫格 里有1至8 八个数以及一个空格随机摆放在格子中，如下图： 初始状态 目标状态 现需将图一转化为图二的目标状态，调整的规则为：每次只能将空格与其相邻的一个数字进行交换。实质是要求给出一个合法的移动步骤，实现从初始状态到目标状态的转变。 2.算法分析 (1)解存在性的讨论 对于任意的一个初始状态，是否有解可通过线性代数的有关理论证明。按数组存储后，算出初始状态的逆序数和目标状态的逆序数，若两者的奇偶性一致，则表明有解。 （2）估价函数的确定