实验一  启发式搜索算法

姓名：徐维坚学号：2220103484 日期：20##/6/29

一、实验目的：

熟练掌握启发式搜索算法及其可采纳性。

二、实验内容：

使用启发式搜索算法求解8数码问题。

1)        编制程序实现求解8数码问题算法，采用估价函数

，

其中：是搜索树中结点的深度；为结点的数据库中错放的棋子个数；为结点的数据库中每个棋子与其目标位置之间的距离总和。

2)        分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是的上界

的的定义，并测试使用该估价函数是否使算法失去可采纳性。

三、实验原理：

1.   问题描述：

八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。

要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。

2.        原理描述：

2.1 有序搜索算法：

（1）原理：

在搜索过程中，OPEN表中节点按照其估价函数值以递增顺序排列，选择OPEN表中具有最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为有序搜索。

在本例中，估价函数中的取节点深度，为节点n的状态与目标状态之间错放的个数，即函数。

（2）算法描述：

…… …… 余下全文

华 中 师 范 大 学 计 算 机 学 院

实 验 报 告 书

实验题目 ： 八数码问题求解

课程名称 ： 人工智能

主讲教师 ： **

班 级 ：

试验时间 ：

1.问题描述：

八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。

要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

2.初始状态

1 0 3

7 2 4

6 8 5

3.目标状态

1 2 3,

8 0 4,

7 6 5

4.搜索策略

启发式搜索技术

（1） 原理：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

（2） 估价函数

计算一个节点的估价函数，可以分成两个部分：

1、 已经付出的代价（起始节点到当前节点）；

2、 将要付出的代价（当前节点到目标节点）。

节点n的估价函数定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值，即= +。

是从初始节点到达当前节点n的实际代价；

是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。

所占的比重越大，越趋向于宽度优先或等代价搜索；反之，的比重越大，表示启发性能就越强。

本实验中我们使用函数，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然比更接近于，因为不仅考虑了错位因素，还考虑了错位的距离。

…… …… 余下全文

《人工智能》上机实验

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

——八数码问题求解

（一）实验软件

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

（二）实验目的

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

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

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

（三）需要的预备知识

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

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

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

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

（四）实验数据及步骤

1. 实验内容

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

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

图1 八数码问题示意图

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

2. 实验步骤

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

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

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

（3）编写算符运算、目标比较等函数；

（4）编写输入、输出接口；

（5）全部模块联调；

（6）撰写实验报告。

（五）实验报告要求

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

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

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

…… …… 余下全文

《人工智能》实验一题目

实验一  启发式搜索算法

1. 实验内容：

使用启发式搜索算法求解8数码问题。

⑴ 编制程序实现求解8数码问题算法，采用估价函数

，

其中：是搜索树中结点的深度；为结点的数据库中错放的棋子个数；为结点的数据库中每个棋子与其目标位置之间的距离总和。

⑵ 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是的上界的的定义，并测试使用该估价函数是否使算法失去可采纳性。

2. 实验目的

熟练掌握启发式搜索算法及其可采纳性。

3.数据结构与算法设计

该搜索为一个搜索树。为了简化问题，搜索树节点设计如下：

typedef struct Node//棋盘

{//节点结构体

    int data[9];

    double f,g;

    struct Node * parent; //父节点

}Node,*Lnode;

int data[9];    数码数组：记录棋局数码摆放状态。

struct Chess * Parent;  父节点：指向父亲节点。

下一步可以通过启发搜索算法构造搜索树。

1、局部搜索树样例：

2、搜索过程

  搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。搜索过程如下：

  （1）、把原棋盘压入队列；

  （2）、从棋盘取出一个节点；

  （3）、判断棋盘估价值，为零则表示搜索完成，退出搜索；

  （4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；

（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃；

…… …… 余下全文

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

——八数码问题求解

（一）实验软件

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

（二）实验目的

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

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

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

（三）需要的预备知识

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

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

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

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

（四）实验数据及步骤

1. 实验内容

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

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

图1 八数码问题示意图

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

2. 实验步骤

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

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

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

（3）编写算符运算、目标比较等函数；

（4）编写输入、输出接口；

（5）全部模块联调；

（6）撰写实验报告。

…… …… 余下全文

八数码问题

（一）问题描述

在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。

（二）问题分析

八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。

1、启发式搜索

由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。

由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。

  启发函数设定。对于八数码问题，可以利用棋局差距作为一个度量。搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。

（三）数据结构与算法设计

该搜索为一个搜索树。为了简化问题，搜索树节点设计如下：

struct Chess//棋盘

{

       int cell[N][N];//数码数组

…… …… 余下全文

昆明理工大学信息工程与自动化学院学生实验报告

（ 20## — 20## 学年 第  1  学期 ）

课程名称：人工智能及其应用   开课实验室：信自楼504  2014年11月 26日

一、上机目的及内容

1.上机内容：

求解八数码问题。

问题描述：八数码难题，问题描述：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0，目标状态S1如图所示，可以使用的操作有：空格上移，空格左移，空格右移，空格下移。只允许位于空格左，上，右，下方的牌移入空格。用广度优先搜索策略寻找从初始状态到目标状态的解路径。

2.上机目的:

（1）复习程序设计和数据结构课程的相关知识；

（2）熟悉人工智能系统中的问题求解过程；

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

二、实验原理及基本技术路线图（方框原理图或程序流程图）

（1）建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点的表中；

（2）建立一个叫做CLOSED的已扩展节点表，其初始为空表；

（3）LOOP:若OPEN表是空表，则失败退出；

（4）选择OPEN表上的第一个节点，把它从OPEN表移除并放进CLOSED表中，称此节点为节点n；

（5）若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的；

（6）扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点舔到图中；

（7）对那些未曾在G中出现过的M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN表或CLOSED表上的成员，确定是否需要更改通到n的指针方向；

（8）按某一任意方式或按某个探视值，重排OPEN表。

宽度优先算法实现过程

…… …… 余下全文