八数码实验报告资源-CSDN文库

需积分: 9 187 浏览量 2016-06-02 18:27:07 上传评论收藏 662KB DOC 举报

资源详情

资源评论

同济大学人工智能原理课程实验报告

实验题目:___八数码问题_____________________

姓名:___________ 学号: 专业:



一．实验概述

【实验目的】

通过实验加深对搜索策略的理解，尤其是对启发式搜索的基本原理的理解，使学生能够通过

编程实现图搜索的基本方法和启发式搜索算法，并能够解决一些应用问题。

【实验问题描述】

八数码问题是人工智能当中有名的难题之一。问题是在 3×3 方格盘上，放有八个数码，剩

下第九个为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，

要求通过一系列的数码移动，将初始位置转化为目标位置。问题的一个状态就是棋子在棋

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

中间过渡状态。本实验采用启发式搜索，综合所学知识以及其他方面知识实现八

数码问题，并加以可视化演示。

初始状态过渡状态目标状态

【实验原理】

本实验采用 A*算法，故在此以 A*算法为介绍对象。

A*算法: A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方

法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接

近，最终搜索速度越快。f(n)=g(n)+h(n)为其估价函数，其中 f(n) 是从开始节点

经由节点 n 到目标节点的代价估计，g(n)是从开始节点到节点 n 的路径代价，

而 h(n)则表示从节点 n 到目标结点的最小代价路径的估计值。保证找到最短路

径（最优解的）条件，关键在于估价函数 f(n)的选取，在搜索过程中以使 f(n)最

小为拓展方向，并根据 f(n)的值即时更新 open 和 close 表中的节点，

【实验环境】

操作系统：Windows 10 操作平台

开发工具：eclipse 开发软件

开发环境：java 开发环境

硬件环境： 内存、 频率 、硬盘 

二．实验过程及结果

5 1 4

6 8

7 3 2

5 4

6 1 8

7 3 2

5 4

6 1 8

7 3 2

【实验方案设计】

在设计八数码实验时，首先我们根据 A*算法特点进行了数据结构设计，然后结

合 A*算法设计解决问题的方法，最后设计界面，将解决问题的方法与界面的

触发函数结合，做出美观实用的八数码问题模型。下面将具体解释每一步的

思路、步骤及方法。

1. 数据结构定义：

◎public class Node

用来定义节点的存储结构及节点包含的变量、数据、函数：

a. 变量：

Node prev;//表示该节点的父节点

private int g;//从开始节点到当前结点的路径代价

private int h;//从当前结点到目标节点的估计代价

private int current;//得到当前状态所要移动的数码

private int state[][];//节点的状态

private Direct direction;//得到当前状态所要移动的方向

Node next;//链表中下一个节点

b. 函数：

public Node(Node prev,int[][]a,int[][]b)//构造初始状态

public Node(Node prev,int[][]a,int hChange,int current,Direct direction)//构

造拓展节点

public void changeNode(Node prev,int hChange,int current,Direct

direction)//用来更新链表中已有节点

public boolean equalState(int[][] a)//用来判断当前状态是否与目标状态相同

public void getState(int[][] currentState)//获取当前状态数据

public int getf()//当到当前状态的 f(n)

public int getc()//得到当前状态的 current

public Direct getDirect()//获取当前状态要移动的方向

◎public class Linklist

用来定义链表的存储结构及链表包含的变量、数据、函数

a. 变量：

Node head;//指向头节点

int num;//记录链表中节点的个数

b. 函数：

public Linklist()//构造函数，起到初始化作用

public Node checkSame(int [][]extendState)//检查是否有相同节点

public void AddHead(Node addhead)//增加节点

public void AddNode(Node addnode)//增加节点，有顺序

public boolean DelNode(Node delnode)//删除节点

◎public enum Direct

用来定义移动方向 UP、DOWN、LEFT、RIGHT

UP 表示向上

DOWN 表示向下

LEFT 表示向左

RIGHT 表示向右

public class Path

用来存储路径的数据结构

int current;//表示当前是哪个数字

Direct direction;//表示当前数字移动方向

Path next;//指向下一个节点

在问题实现过程中，open 表中节点按照其估价函数值以递增顺序排列，选

择 open 表中具有最小估价函数值的节点作为下一个待扩展的节点，将已

拓展的节点放入 close 表中，表中设置指向头节点的指针，以及记录当前节

点个数的变量，表中节点用 node 表示，node 中 parent 所指向的节点表示

该节点是由其拓展而来的，next 用来指向表中下一个节点。

2. 解题策略：

本实验采用最佳优先搜索：A*算法，f(n)=g(n)+h(n)为其估价函数，g(n)是

从开始节点到节点 n 的路径代价，而 h(n)则表示从节点 n 到目标结点的最

小代价路径的估计值。

总体思路：

<1>首先根据输入建立初始状态和目标状态节点，计算初始状态的估价函数

<2>计算初始状态节点和目标状态节点的逆序数，如果逆序数奇偶性不同，

说明此问题无解，失败退出；如果不同则把初始状态放入 open 表中（open

表中节点是按顺序存放的）

<3>判断 open 表头节点是否为空，若为空，则无解，反之进行下面的步骤

<4>把 open 表中头节点放入 close 表中，判断进入 close 表的节点是否是目

标节点，如果是目标节点，则成功退出；反之拓展当前节点，重复进行<3>

直至找到目标节点，或失败退出。

设计技巧

<1>open 表中对节点进行从小到大的排列，每次拓展后，只要把头节点取

出放入 close 中即可，因为 open 表中最小代价节点就是头节点。

<2>用 path 记录 close 表中状态节点加入的顺序，并在 path 中记录每个状

态所要移动的数码及移动的方向，以便于后续过程的演示。

<3>根据空白所在的位置来分情况考虑数码要移动的方向，在中间有四种移

动方式，在边上有三种移动方式，在四角有两种移动方式，然后根据这几

种情况来进行节点拓展

<4>同时要设置一个状态查重函数，在拓展状态的时候，如果发现在 open

表或者 close 表中已有相同节点，那么则要根据他们的估价函数来进行取舍

替换。

<5>为避免无用搜索，可以在搜索前计算一下初始状态和目标状态的逆序

数，如果他们的逆序数奇偶性不同，则这种情况无解就不必进行搜索了。

<6>在输入模块建立输入检测功能，检查不合法或超出范围的数据。

开始

剩余34页未读，继续阅读

评论收藏

内容反馈

八数码实验报告

评论0

最新资源

八数码实验报告

评论0

最新资源

相关推荐

八数码问题实验报告

人工智能 八数码实验报告

人工智能八数码实验报告

西工大人工智能八数码实验报告

八数码实验报告（附源代码·）

八数码问题实验报告1

八数码

八数码结题报告

昆明理工大学八数码实验报告.docx

宽度优先算法解决八数码问题实验报告.zip

武汉理工大学人功智能概论八数码实验报告.docx

数码转换实验报告

八数码_八数码_

数码鱼

-9-数码枪

武汉理工大学人功智能概论八数码实验报告.pdf

最新武汉理工大学人功智能概论八数码实验报告.docx

利用启发式搜索解决八数码难题程序及实验报告

bashuma.zip_八数码实验_数码实验报告

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

数码数码

数码展

八数码问题_八数码_八数码问题_

八数码 A* A星

数码

人工智能八数码实验报告