人工智能 A算法

【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《人工智能 A算法》，欢迎阅读！

自己收藏的

觉得很有用

故上传到百度

与大家一起分享！

人工智能课程设计

题目:用A*算法解决8数码问题

学院:信息科学与技术学院

专业:计算机科学与技术

2005年12月

摘 要

本课题以人工智能两大支柱之一的搜索技术中的启发式搜索策略（即通过对向最终结果的逼近作评估来发现问题的解）为出发点

结合人工智能应用及其最新进展

阐述了人工智能搜索原理、启发式搜索算法和启发式函数等内容

本文讨论了各种状态空间搜索策略、启发式推理技术

并且以八数码问题为例着重讨论了各种启发式函数及其特点

分析它们在问题求解时所起的作用

关键词：人工智能

搜索策略

启发式函数

目 录

1. 概述

1.1 八数码问题

1.2 A*算法

1.3 A*算法的一般描述

1.3.1约定

1.3.2算法过程

2. A*算法在VC6.0开发环境下的实现

2.1类

2.1.1 CDisplay类

2.1.2 CMain类

2.1.3 其它类

2. 2数据结构

2.2.1 生成搜索树

3．主要程序代码及注释

4．其它

5. 结束语

参考文献

附件一

附件二

1. 概述

1.1 八数码问题

8数码问题是指在3X3的九宫棋盘上有标号为1～8的8个棋牌,和一个空白位,通过棋牌向空白位移动来改变棋盘布局,如何移动棋牌才能从初使布局到达目标布局.显然解答路径实际上就是一个合法的走步序列

1.2 A*算法

A*算法属于一种启发式搜索,它扩展结点的次序类似于广度优先搜索,但不同的是每生成一个子结点需要计算估价函数F,以估算起始结点的约束经过该结点至达目标结点的最佳路径代价;每当扩展结点时,意是在所有待扩展结点中选择具有最小F值的结点做为扩展对象,以便使搜索尽量沿最有希望的方向进行.A*算法只要求产生问题的全部状态空间的部分结点及关系,就可以求解问题了,搜索效率较高

2.3 A*算法的一般描述

1.3.1约定

S：指示初使状态节点（Note）；G：指示搜索图

OPEN：作为存放待扩展节点的表；SNS：子节点集合

CLOSE：作为存放已被扩展节点的表

Move_First(Open)：指示取Open表首节点作为当前要被扩展的节点n

同时将节点n移到CLOSE表；

F(n) = G(n) + H(n)：评价函数

用于排列节点在OPEN表中的位置

1.3.2算法过程

○1 G:=S; ○2 OPEN := (S), CLOSE := ();

○3 如果OPEN为空则算法失败

○4 n := Move_First(OPEN);

○5 如果n是目标结点

搜索完成

○6 扩展节点n

将非节点n祖先的子节点置于子点子集合SNS中

并插入G

对SNS每个子节点计算F(n,ni)=G(n,ni)+H(ni)

○7 标记与修改指针：

1.把SNS中的

本文来源：https://www.dywdw.cn/db72f83f084e767f5acfa1c7aa00b52acfc79c38.html