篇一 :八数码实验报告

利用人工智能技术解决八数码游戏问题

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中的节点,确定是否需要修改通向他们后继节点的指针。

…… …… 余下全文

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

实验一  启发式搜索算法

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

一、实验目的:

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

二、实验内容:

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

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

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

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

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

三、实验原理:

1.   问题描述

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

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

…… …… 余下全文

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

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

——八数码问题求解

(一)实验软件

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)

《人工智能》实验一题目

实验一  启发式搜索算法

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;  父节点:指向父亲节点。

…… …… 余下全文

篇五 :八数码实验报告53

华 中 师 范 大 学 计 算 机 学 院

实 验 报 告 书

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

课程名称 : 人工智能

主讲教师 : **

班 级 :

试验时间 :

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) 估价函数

…… …… 余下全文

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

八数码问题

(一)问题描述

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

(二)问题分析

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

1、启发式搜索

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

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

…… …… 余下全文

篇七 :人工智能实验报告八数码难题

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

201   201  学年     学期

 课程名称:             开课实验室:            年 月  日

一、实验内容

       八数码难题,问题描述:在3×3方格棋盘上,分别放置了标有数字1,2,3,4,5,6,7,8的

八张牌,初始状态S0,目标状态S1如图所示,可以使用的操作有:空格上移,空格左移,

空格右移,空格下移。只允许位于空格左,上,右,下方的牌移入空格。用广度优先搜索

策略寻找从初始状态到目标状态的解路径。

                 

…… …… 余下全文

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

                                                  

                                                         

…… …… 余下全文