这把年纪,依然不清楚A*算法,有点可耻了
看了结构之法的博客,google相关内容,总结A*算法如下
问题可以简单描述为 找到从指定起点到指定终点的最短路径
一般的搜索如BFS、DFS、Dijkstra算法往往是一种盲目的四周方向的搜索,搜索空间大,效率低
而A*算法引入估价函数的概念
公式表示为: f(n)=g(n)+h(n),
其中f(n) 是从初始点经由节点n到目标点的估价函数,
g(n) 是在状态空间中从初始节点到n节点的实际代价,
h(n)是从n到目标节点最佳路径的估计代价。
在当前节点的候选节点中,选取估价函数值f(n)最小的节点
以上时A*算法的主要的内容
使得具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是:
1、搜索树上存在着从起始点到终了点的最优路径。
2、问题域是有限的。
3、所有结点的子结点的搜索代价值>0。
4、h(n)=<h*(n) (h*(n)为实际问题的代价值)
一般情况下,前三个条件容易满足,关键在于第4个,估计代价h(n)的设计
因为实际情况下,h*(n)并不知道,h(n)的好坏与A*算法的表现优劣关系很大。
h(n)与h*(n)越接近,算法的效果越好。
如何设计一个合理的f(n),是后续关注的重点。
以上是本人对A*算法的简单理解,不足之处,请指正。
分享到:
相关推荐
对传统的A*算法进行matlab仿真实验,位做改进,只为给读者提供最原始简介的实验环境,避免因为过度的改进造成不必要的理解误区。该实验程序可自由定义栅格地图大小,自由定义障碍物的摆放位置与数量,同时也可以生成...
【无人机路径规划】基于A算法求解无人机三维路径规划问题matlab源码.zip
本文档旨在介绍常见搜索算法(如:广度优先搜索,深度优先搜索,爬山算法,束搜索,最佳优先算法,分支界限,A*)。 本文档主要针对搜索算法执行步骤,示例执行过程与搜索树的构造进行简介。 适用于 初学计算机算法...
关于A*寻路算法的代码在网上有很多,但用DELPHI的比较...A*寻路算法简介 A*与最好优先算法的原理类似,只是最好优先算法在路经上给出了节点的代价,而A*算法需要F(NODE) = G(NODE)+H(NODE)的估价函数来估计当前点的代价
【路径规划】基于A星算法实现栅格地图全路径规划matlab源码.zip
AS3游戏常用寻路算法 astar(a星)算法 - A*算法 原理简介 A*(A-Star)算法是一种静态路网中求解最短路最有 A star 算法在静态路网中的应用 效的方法。
里面有两篇关于A星算法的详细介绍,源代码也包括在里面!讲的很详细,对初学者很好!
2.2算法描述2.2.1 A*算法简介A*(A-Star)算法是求解最短路最有效的直接搜索方法,也是许多其他问题的常用启发式算法 2.2.3 选择启发式函数A*
在这个项目中,我研究并使用了 A* 算法。 我使用了“城市街区”又名。 曼哈顿启发式计算与目标的距离。 作者:我叫帕特里克·奥斯古德。 我正在学习编程,希望尽快成为一名专业的程序员。 您可以通过与我联系
a星算法,用于规划的,求最短路径,可以看看
算法简介A*算法结合了贪心算法(深度优先)和Dijkstra算法(广度优先),是一种启发式搜索算法。路径优劣评价公式为: f(n)=g(n)+h(n)。f(n)
a) SIFT特征是图像的局部特征,其对旋转、尺度缩放、亮度变化保持不变性,对视角变化、仿射变换、噪声也保持一定程度的稳定性。 b) 独特性(Distinctiveness)好,信息量丰富,适用于在海量特征数据库中进行快速、...
【路径规划】基于A星算法求解栅格地图路径规划matlab源码.zip
【路径规划】基于动态衡量式A星算法及拐角优化算法实现栅格地图路径规划matlab源码.zip
人工智能结课作业(A星八数码/广度优先/深度优先/粒子群寻优算法/遗传算法/蚁群算法/BP神经网络/卷积神经网络) 简介 本项目包含我当时人工智能与专家系统的结课作业。总共分为三大部分,每部分由几个相关算法组成...
The bag-of-words model is a simplifying assumption used in natural language processing and information retrieval. In this model, a text (such as a sentence or a document) is represented as an ...
内容简介: 用Netbeans基于Java开发的遗传算法和交互式遗传算法平台,内含源代码,jar包等. 包含了: (1)传统遗传算法在函数优化中的应用,你可以仿照其中的代码加入自己的函数进行优化; (2)交互式遗传算法在...
他的论文 A New Road Map of Algorithm Design Techniques:Picking Up Where the Traditional Classification Leaves Off(《算法设计技术新途径:弥补传统分类法的缺憾》)受到业内人士极高的评价。在SIGCSE会议上...
【算法】02 SCE-UA简介及源代码 https://blog.csdn.net/weixin_43012724/article/details/121401083 【算法】03 SCE-UA算法C++实现 https://blog.csdn.net/weixin_43012724/article/details/121862991 作者: 卢家波...