没有合适的资源?快使用搜索试试~ 我知道了~
人工智能报告.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 165 浏览量
2023-02-03
17:33:12
上传
评论
收藏 611KB DOCX 举报
温馨提示
试读
27页
人工智能报告.docx
资源推荐
资源详情
资源评论
人工智能课程报告
——推箱子小游戏的人工智能寻路
学院:
姓名:
学号:
班级:
指导教师:
人工智能课程报告
一.简介
推箱子游戏简介
经典的推箱子是一个来自日本的古老游戏,目的是在训练你的逻辑思考能力。在一个狭
小的仓库中,要求把木箱放到指定的位置,稍不小心就会出现箱子无法移动或者通道被堵住
的情况,所以需要巧妙的利用有限的空间和通道,合理安排移动的次序和位置,才能顺利的
完成任务。胜利条件就是把所有的箱子都推到目的地。本程序的目标就是利用启发式搜索实
现电脑自动推箱子。
推箱子游戏地图
程序采用手机中的推箱子小游戏的程序,地图总共 75 张,难度由易到难,搜寻路径的
计算复杂度也会越来越高。每一张地图都以文本文件的形式存储起来。
地图展示:
(第 1 关) (第 35 关)
(第 56 关) (第 75
关)
保存到文本文件中的地图代码:
推箱子中人的行为
人只可以推箱子, 不可以拉, 而且一次只能推动一个。即使是处于目的位置的箱子也可
以推走。
二.基本概念
启发式搜索
考虑一个普通的图搜索问题:给出初始状态(节点 s)和目标状态(节点 t,可以不止一
个)以及 状态的产生规则,求从 s 到 t 的一条路经。搜索过程可描述如下:
1 待展开的节点集合(OPEN 表)为 {s},已展开的节点集合(CLOSED 表)为 {},节点 s 的层
深为 g(s) = 0。
2 每次从 OPEN 表中取出一个节点 n,根据规则扩展产生一组节点 m
i
,然后把 n 放入 CLOSED
表中。节点 m
i
可能属于下列三种情况之一:
(1)新的节点,则把 m
i
的源标记为 n,层深 g(m
i
) = g(n) + 1,并放入 OPEN 表中。
(2)已在 OPEN 表中存在的节点,并且层深 g(m
i
) > g(n) + 1,说明从 s 到 m
i
并且经
由 n 的路径要比先前搜索得到的路径要短。因此,把 m
i
的源改记为 n,层深 g(m
i
) = g(n)
+ 1,仍放入 OPEN 表中。
(3)已在 CLOSED 表中存在的节点,并且层深 g(m
i
) > g(n) + 1。同理,把 m
i
的源改记为
n,层深 g(m
i
) = g(n) + 1,并从 CLOSED 表中取出重新放入 OPEN 表中,留待以后重新搜
索计算 m
i
的子节点的层深。
3 不断重复上一步操作,直到满足下列条件之一:
(1)n == t,搜索成功。
(2)OPEN 表为空,搜索失败。
在以上过程中,如何从 OPEN 表中选取待扩展的节点是关键。如果每次均选取层深 g(n)
最小的节点,以上过程就是宽度优先搜索;如果每次均选取层深 g(n) 最大的节点,以上过
程 就是深度优先搜索。启发式搜索算法 A*的思想是,给节点定义一个评价函数
f(n) = g(n) + h(n) (1)
其中,g(n) 是节点的层深,即从 s 到 n 目前搜索已知的最短路径长度,h(n) 是节点
n 到目标节点 t 的最短路径长度的估计值,称为启发函数。拥有最小 f(n) 值的节点有希望
成为从 s 到 t 的最短路径上的一个节点,因而被取出并扩展。
启发函数 h(n) 具有下列一些性质(证明略,我也不完全懂):
如果 h(n) 处在从 n 到 t 的最短路径长度的真实值 h
*
(n) 的下界,即恒有 h(n) <=
h
*
(n),则算法 A*找到的一定是从 s 到 t 的最短路径。此时算法 A*称为算法 A*。
可以想象,h(n) 越接近真实值 h
*
(n),它所包含的启发信息就越多,搜索所需扩展的节点数
就越少。
如果对所有节点 n
i
和 n
j
(其中 n
j
是 n
i
的子节点)都有 h(n
i
) - h(n
j
) <= 1,则称启发
函数 h(n) 满足单调限制条件。此时,算法 A*在选取节点 n 进行扩展时,必有 g(n) ==
g
*
(n),在搜索过程中不会出现把 m
i
从 CLOSED 表中取出重新放入 OPEN 表的情况。
三.算法的设计与实施
推箱子游戏模块
程序中定义的四个函数:
int orderDown(NodeInfo *infos, int *opens, const int
&open_used, int root);
堆的向下(从根到叶)调
整,内部使用
int orderUp(NodeInfo *infos, int *opens, const int
&open_used, int leaf);
堆的向上(从叶到根)调
整,内部使用
template <class Node> int key(Node *nodes, const int
&hash_size, const Node &n);
在散列数组中查找节点
template <class Node> int solve(Node *nodes, int hash_size,
Node s);
搜索函数,程序的入口
基于可重用性的考虑,搜索函数 solve 被定义为模板函数,它操作的对象是一个表示
节点的 模板类。节点类要求具有被搜索函数使用的一些基本接口,这些接口描述了节点的
推箱子游戏
初
始
化
模
块
画
图
模
块
移
动
箱
子
模
块
移
动
小
人
模
块
功
能
控
制
模
块
基本行为和属性,而节点的 具体意义(比如表示推箱子的某个状态)则隐藏在类的实现细节
中。节点类的基本接口如下:
int from;
节点的源,返回目标路径时
使用
Node();
空节点的构造函数
int possibleMoves() const;
可能的扩展节点数
int move(int sw);
按第 sw 种扩展方式改变节点
int h() const;
启发函数
int isTarget() const;
判断节点是否目标节点
int isNull() const;
判断节点是否空节点
int hash() const;
散列函数
friend int operator == (const Node &left, const Node
&right);
判断两个节点是否同一
void output() const;
输出
为了提高速度,节点的存储和查找使用开地址散列,使用简单的线性探测解决冲突。
程序中的 Node nodes[] 和 NodeInfo infos[] 是并列的两个散列数组,分别存储所有已展
开的节点 和节点的附加信息(f 值和在 OPEN 表中的位置)。key 根据节点的散列函数 hash()
在散列数组中查找或分配节点。
OPEN 表实际上是一个优先队列,因而采用堆的方式实现。程序中的 int opens[] 是以
数组(完全二叉树)存储的堆,数组元素表示节点在散列数组中的位置,最小 f 值的节点可以
在 堆的根即 opens[0] 处中给出。orderDown 和 orderUp 是调整堆的需要。
推箱子
应用通用程序求解推箱子问题,关键是节点类的实现。
状态的划分
推箱子的状态由人和箱子的位置决定。考虑到人可以在墙壁和箱子围成的连通区域内任
意行走 而不会对局面产生实质性的影响,规定人必须位于他所处的连通区域的左上角。考
虑到箱子的全同性,箱子的 坐标应从小到大排序。这些都在构造函数 Box() 或者节点扩展
函数 move(sw) 中完成。这时,判断 两个状态是否相等只需分别比较每个箱子和人的坐标是
否相等即可。
节点的扩展
每个箱子可以推向四个方向,因此总的可能的扩展节点数是箱子数的四倍。考虑到人的
可到达范围(way[])的限制,某些箱子的某些方向(push_directions[])是不可到达的。另外,
地图中 还存在一些“死位置”(dead_positions[]),比如墙角、两个箱子并列在墙边等等。
还有,箱子的背后 可能是墙壁或者另一个箱子。这些不可能的情况都可以在节点扩展函数
move(sw) 中予以拒绝。
启发函数
可以计算所有箱子离最近的目标的距离之和作为启发函数 h() 的返回值。不难看出,此
定义的 启发函数满足算法 A*的下界条件,因而找到的目标路径一定是最优解。
A*算法的伪代码如下:
创建两个表,OPEN 表保存所有已生成而未考察的节点,CLOSED 表中记录已访问过的节点。
剩余26页未读,继续阅读
资源评论
猫一样的女子245
- 粉丝: 95
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功