A*算法
是一种启发式的搜索算法。
了解BFS、DFS或者Dijkstra算法的人应该知道。这些算法都是一种向四周盲目式搜索的方法。
启发式搜索:
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径,提到了效率。在启发式搜索中,对位置的估价是十分重要的。不同的估价可以有不同的效果。因此,A*算法的关键就在于如何建立这个启发函数。
公式表示为:f(n)=g(n)+h(n),
f(n)是从初始点经由节点n到目标点的估价函数,
g(n)是在状态空间中从初始节点到n节点的实际代价,
h(n)是从n到目标节点最佳路径的估计代价。
A* 算法与广度、深度优先和 Dijkstra 算法的联系:
1、g(n) = 0 时:该算法类似于DFS。
2、h(n) = 0 时:该算法类似于BFS。
3、如果h(0) = 0,只需求出g(n)(即起点到任意点n的最短路径)时,则转化成单源最短路径问题。
A*算法浅析:
A*算法与其他搜索路径的算法的最大区别在于其估计函数的设计,也就是公式:f(n)=g(n)+h(n)中h(n)的设计。
一般计算h(n)的方法有下面几种:
1、曼哈顿距离:|x1-x2| + |y1-y2|。
2、欧式距离:两点之间的直线距离。
3、切比雪夫距离:max(|x2-x1|,|y2-y1|)。
这幅图中绿色的线代表欧式距离,其他均为曼哈顿距离。
该图中,F6到E2的切比雪夫距离为:4
接下来的分析中,我们的h(n)为曼哈顿距离,g(n)为欧式路径。
假设我们需要搜索的情况如下:
绿色为起始点,红色为目标,蓝色为障碍物,黑色为可通行路径。
F的值是G和H的和。第一步搜索的结果可以在下面的图表中看到。F,G和H的评分被写在每个方格里。正如在紧挨起始格右侧的方格所表示的,F被打印在左上角,G在左下角,H则在右下角。
接下来我们来讲讲A*算法的流程:
1,把起始格添加到开启列表。
2,重复如下的工作:
a) 寻找开启列表中F值最低(最佳估值)的格子,把它切换到关闭列表。
b)对相邻的格中的每一个格子进行判断
* 如果它不可通过或者已经在关闭列表中,略过它。反之如下。
* 如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
* 如果它已经在开启列表中,用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序,改变之后你可能需要重新对开启列表排序。
c)停止,当你
* 把目标格添加进了关闭列表(注解),这时候路径被找到,或者
* 没有找到目标格,开启列表已经空了。这时候,路径不存在。
3.保存路径。从目标格开始,沿着每一格的父节点移动直到回到起始格。这就是你的路径。
下篇文章,我将使用A*算法解决一个经典的八数码问题。
---------------------by----zerocool--------2012年9月29日22:58:34
分享到:
相关推荐
五子棋人工智能算法,电脑算的上比较聪明了!可以人机对弈。
【有C语言基础即可,自己去搜索下如何用Java写出Hello World就没有问题】 大二,推荐这本书从头到尾好好读一遍,做下上千道的课后习题 【后面的有点小难度,但是难度不大值得一做,听起来很多的样子,用心去做,...
这是我认为的JADE平衡好在提高了收敛性能的同时保持了人口多样性的关键。当然,聪明的读者发现了可以在两个差分向量之间施以不同的权重来改进算法,这也是我第一次想创新时想出的最简单的改进了。
秃鹰搜索(BES)算法,这是一种新颖的,受自然启发的元启发式优化算法,它模仿秃鹰在寻找鱼类时的狩猎策略或聪明的社交行为。 这是该文件的源代码:Alsattar,HA,Zaidan,AA&Zaidan,BB(2020)。 新颖的元启发式...
[⼈⼯智能]alpha-beta剪枝算法及实践 alpha-beta剪枝算法及实践 算法原理 算法伪码 中国象棋AI实践 算法原理 alpha-beta剪枝算法是基于极⼤极⼩搜索算法的。极⼤极⼩搜索策略是考虑双⽅对弈若⼲步之后,从可能的步...
倒不是害怕电脑程序真的能比我聪明从而使我失去了对程序的控制。我倒是想这样...... 6,当然还采用了其他一些“无效区”分析的方法。包括几个箱子挤在一起的情况、凹形区域底边箱子数量分析、用回溯法分析无效区、...
楼天城 -《匹配算法在搜索问题中的应用》 贝小辉 -《浅析树的划分问题》 林 涛 -《线段树的应用》 杨思雨 -《伸展树的基本操作与应用》 许智磊 -《后缀数组》 朱泽园 -《多串匹配算法及其启示》 韩文弢 -《论...
下面是实验内容描述,具体详情可以下下来看 实验一:聪明的打字员 实验二:马周游问题-启发式搜索 实验三:alphabeta剪枝-三子棋 实验四:遗传算法 实验五:蚁群算法-TSP旅行商问题
运用本书中介绍的先进算法,你可以编写聪明的程序,以访问其他网站那些有趣的数据集,从自有应用程序的用户中收集数据,或者分析和理解你所发现的数据。 《集体智慧编程》将你带入机器学习和统计的世界,并且阐释了...
merge-sort-static-list.cpp-在静态列表上合并排序(不是那么聪明的实现) 堆 堆栈-包含堆栈的静态,固定大小和链接的实现。 StackTest-使用自定义单元测试框架演示单元测试的使用。 带STL的组合和数据结构 Combines...
【一点资讯】聪明地了解你的兴趣,智能汇聚你最关心的内容。 50000 基于兴趣的主题频道,让你轻松发现对味的内容 微博绑定,快速猜出你的兴趣 专属你的信息流聚合精华资讯,只为你服务 先进算法不断学习了解你的兴趣...
一种深度优先的搜索方法,可以解决数独问题。 用C ++编写,编译为WebAssembly并。 编译并运行 在项目的根目录下运行make run ,以在上编译并运行求解器(这使用和 Docker映像)。 算法 我们使用对每个像元应用所有...
张宁:《猜数问题的研究——《聪明的学生》一题的推广》 伍昱:《由对称性解2-SAT问题》 周源:《浅析“最小表示法”思想在字符串循环同构问题中的应用》 姜尚仆:《模线性方程的应用——用数论方法解决整数问题》 ...
最聪明的算法 我要的排名位置没有了! 客户 销售人员 您花2000¥可以买5个关键词服务,5个关键词服务带来的流量肯定和排在您要的那个热门关键词11名的流量相差不大! 您花5000¥可以买15个关键词服务,15个关键词...
JavaScript 图形库。 以及它的算法朋友。...路线图 图形 有向图 无向###迭代器 特别勋章 广度优先搜索 深度优先搜索###算法 和弦检查器 顶点着色 字典广度优先搜索####寻找路径 A*(未加权图) 普里姆 迪杰斯特拉
何时使用蛮力,何时使用聪明; 斑马拼图; 生成器表达式; 排列组合。 密码学; 递归和一厢情愿的想法; 最长回文子串算法。 第 3 课:正则表达式、其他语言和解释器 定义正则表达式的语言; 口译语言; 定义正则...
张宁:《猜数问题的研究——《聪明的学生》一题的推广》 伍昱:《由对称性解2-SAT问题》 周源:《浅析“最小表示法”思想在字符串循环同构问题中的应用》 姜尚仆:《模线性方程的应用——用数论方法解决整数问题》 ...
张宁:《猜数问题的研究——《聪明的学生》一题的推广》 伍昱:《由对称性解2-SAT问题》 周源:《浅析“最小表示法”思想在字符串循环同构问题中的应用》 姜尚仆:《模线性方程的应用——用数论方法解决整数问题》 ...
如果与搜索相关,请考虑二分搜索。 “二分搜索告诉我们,当一个列表被排序或大部分排序时: 给定索引处的值告诉我们很多关于左侧和右侧的信息。 我们不必查看列表中的每个项目。 通过检查中间项目,我们可以“排除”...
用回溯算法搜索这n+1层的完全二叉树。 1)若当前工程和之前已选的工程集合不相容,则剪去该分支,不进行该分支之下的搜索,返回到上层结点。 2)将所有满足相容性的可行的叶节点,计算获得的最大工钱数。