A星算法求解迷宫问题实验资源-CSDN文库

版权申诉

5星 · 超过95%的资源 108 浏览量 2023-04-29 18:57:17 上传评论收藏 107KB DOC 举报

资源推荐

资源详情

资源评论

实验四：A*算法求解迷宫问题实验

一、实验目的

熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用 A*

算法求解迷宫问题，理解求解流程和搜索顺序。

二、实验内容

迷宫问题可以表述为：一个二维的网格，0 表示点可走，1 表示点

不可以走，点用（x，y）表示，寻找从某一个给定的起始单元格出发，

经由行相邻或列相邻的单元格(可以通过的)，最终可以到达目标单元

格的、所走过的单元格序列。在任一个单元格中，都只能看到与它邻

近的 4 个单元格(如果位于底边，则只有 3 个；位于 4 个角上，则只

有 2 个是否能通过)。

A*算法是人工智能中的一种搜索算法，是一种启发式搜索算法，

它不需遍历所有节点，只是利用包含问题启发式信息的评价函数对节

点进行排序，使搜索方向朝着最有可能找到目标并产生最优解的方向。

它的独特之处是检查最短路径中每个可能的节点时引入了全局信息，

对当前节点距终点的距离做出估计，并作为评价节点处于最短路线上

的可能性的度量。

A*算法中引入了评估函数，评估函数为：f（n）=g（n）+h（n）

其中：n 是搜索中遇到的任意状态。g(n)是从起始状态到 n 的代价。

h(n)是对 n 到目标状态代价的启发式估计。即评估函数 f ( n) 是从初

始节点到达节点 n 处已经付出的代价与节点 n 到达目标节点的接近

程度估价值的总和。

剩余12页未读，继续阅读

内容反馈

版权申诉

m0_74812742

2023-06-17

实在是宝藏资源、宝藏分享者！感谢大佬~

文档优选

粉丝: 88
资源: 1万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip