文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > A星算法实验报告
侵权投诉

A星算法实验报告

A*算法

A*算法实验报告

一、 实验原理

A*算法,作为启发式算法中很重要的一种,被广泛应用在最优路径求解和一些策略设计的问题中。而A*算法最为核心的部分,就在于它的一个估值函数的设计上:

f(n)=g(n)+h(n)

其中f(n)是每个可能试探点的估值,它有两部分组成:一部分为g(n),它表示从起始搜索点到当前点的代价(通常用某结点在搜索树中的深度来表示)。另一部分,即h(n),它表示启发式搜索中最为重要的一部分,即当前结点到目标结点的估值,h(n)设计的好坏,直接影响着具有此种启发式函数的启发式算法的是否能称为A*算法。

一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是:

1) 搜索树上存在着从起始点到终了点的最优路径。

2) 问题域是有限的。

3)所有结点的子结点的搜索代价值>0。

4)h(n)=<h*(n) (h*(n)为实际问题的代价值)。

当此四个条件都满足时,一个具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法,并一定能找到最优解。

对于一个搜索问题,显然,条件1,2,3都是很容易满足的,而

条件4): h(n)<=h*(n)是需要精心设计的,由于h*(n)显然是无法知道的。

所以,一个满足条件4)的启发策略h(n)就来的难能可贵了。不过h(n)距离h*(n)的程度不能过大,否则h(n)就没有过强的区分能力,算法效率并不会很高。对一个好的h(n)的评价是:h(n)在h*(n)的下界之下,并且尽量接近h*(n).

二、 实验过程

运行未修改的程序会得到最优路径为:

A星算法实验报告

第1页

你可能喜欢

  • 八数码问题
  • 人工智能实验报告
  • 进程调度算法实验报告
  • 银行家算法实验报告
  • 页面置换算法实验报告
  • 排序算法实验报告
  • 计算机算法实验报告
  • 动态规划算法实验报告

热门文档

相关文档

  • A星算法实验报告11

    A星算法实验报告11_计算机软件及应用_IT/计算机_专业资料。人工智能人工智能 学院:信息学院 班级: 学号: 姓名: 一、 实验原理 A*算法,作为启发式算法中很重要...

  • 实验二 A星算法实验

    3) 分析估价函数对搜索算法的影响。 4 )分析 A*算法的特点。 5、提交要求 1、本次实验为个人任务,需独立完成,以纸质和电子档的形式把实验报告提交给学习 委员...

  • 实验报告A

    D-A转换仿真实现 实验报告 13页 5财富值 A星算法实验报告 4页 2财富值 A-实验报告模版 暂无评价 3页 免费 电子商务安全实验报告A 12页 2财富值...

  • A星算法求解八数码技术报告

    A星算法求解八数码技术报告_计算机软件及应用_IT/计算机_专业资料。人工智能。...实验结果: 实验结果: 附录: 源代码及其注释 #include "iostream.h" #include ...

  • A星算法详解

    A星算法详解_计算机软件及应用_IT/计算机_专业资料。A星算法详解A*路径寻找算法入门 来源于: GameDev.net 作者: Patrick Lester 原文 URL: http://www.game...

  • 人工智能(A星算法)

    人工智能 A*算法实验报告实验目的 1.熟悉和掌握启发式搜索的定义、估价函数和算法过程 2. 学会利用 A*算法求解 N 数码难题 3. 理解求解流程和搜索顺序 实验原理...

  • A星算法

    算法所用内存较少. 二.广度优先搜索(BFS) 1.先在开始位置测试周围一格所能走...2014年度细分行业报告汇集 2014年移动互联网O2O分析报告 休闲农庄项目可行性研究...

  • A星算法求解八数码问题

    实验结果,如图 3 所示 3 图 3 A*算法求解八数码问题实验结果 7、源代码 ... 休闲农庄项目可行性研究报告 2014年建筑幕墙建筑装饰行业分析报告...

  • A星算法中文详解

    A星算法中文详解_IT/计算机_专业资料。UNITY3D中的A星算法中文详解虽然A*(读作A星)算法对初学者来说是比较深奥难懂,但是一旦你找到门路了, 它又会变得非常简单...

  • A星算法

    A星算法_专业资料。A星算法A*算法目录 原理简介 估价值与实际值越接近,估价函数取得就越好 详细内容 启发式搜索其实有很多的算法 其实 A*算法也是一种最好优先...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email