2.1.10 A星算法在线视频

为什么最佳优先搜索算法仍然不能得到最优解

它能找到可行解

但不一定能找到最优解

其实我们发现问题关键在于

就是因为忽略了

从初始节点到当前节点这样的代价造成的

所以结合前面那种算法的优点

我们重新定义一个代价估计函数

把它定义为从起始节点到当前节点的实际路径

代价值GN

再加上从当前节点到目标节点的路径代价的估计值

也就是曼哈顿距离

让它俩之和作为评价函数

那么能满足它们之和

也就是说这个代价函数的估计值

是实际的最优值的下界函数

也就是估计值小于实际的自由值

这一条件的搜索算法

我们称为A*算法

那么这是A*算法的算法六它的步骤

第一步

将初始节点ni和它的代价放入OPEN表中

第二步

将OPEN表中的最前面的节点提出来

并设为n如果OPEN表为空

那么求解告终失败

显然这里面如果这个节点就是目标节点

那么就求解成功了

下一步扩展当前节点n得到子节点的集合

把n放入CLOSED表中

第四步对于子节点的集合中

不包含在CLOSED表中的节点配置

指向n′的指针

也就是指向目标节点的指针

计算出从起始节点到当前节点

以及当前节点到目标节点的

前面是实际值后面是估计值

作为它们的代价函数之和

同样进行排序

从小到大进行排序

放到OPEN表中

那这里面如果发现当前节点出现了它的估计值

同样的到达了一个节点

它的代价的总和更小的时候我就要注意更新

通过配置指针解决这个问题

替换一下

后面结合实际例子来解释一下

第五步就返回到第二步

进行一个循环

下面我们还是以这个状态空间图为例

介绍一下A*算法的搜索过程

初始节点是F

目标节点是B

在F节点它有一个子节点就是G

那么这时候G的对应的代价多少呢

我们就要考虑从起始节点到当前节点的实际代价是E

那么从当前节点G到目标节点B的曼哈顿距离

也就是他的估计代价是多少

3加2等于5

所以两个代价加起来是六

这是节点G的代价是六

那么下一步搜索G的时候

产生了两个子节点E和H

E从起始节点F经过G到达E的实际代价是二

另外一方面

从当前节点E到达目标节点B的代价估计值

也就是曼哈顿距离2加2等于4

所以它的代价是六

E是六

H呢

从起始节点F经过G到达当前节点H的代价是三

而H到达目标节点曼哈顿距离估计值也是三

加起来是六

这样的话就得到了OPEN表里面是C6

H也是6

下一个搜索谁呢

我们可以先搜索E

对于E节点来说

它有两个子节点

一个是C一个是A

那么对于C节点来说

F经过G E到C的代价

实际代价是三

然后C到目标节点B的代价估计值

曼哈顿距离也是三

加起来就是六

C 6

A呢F经过GE到A实际代价是六

加上A到目标节点B的代价估计值是二

所以A代价是八

这样的话就得到了

在节点E位置

OPEN表里面就是（H,6）（C,6）（A,8）

下一个搜索谁呢

搜索代价总代价最小的H

我们发现H没有子节点

所以在H节点位置处

OPEN表里面只剩下（C,6）（A,8）

那么下一个搜索谁呢

显然搜索C

搜索C的时候

我们发现它有两个子节点A和D

那么F经过GEC到A

它的实际代价是四

加上A到B的估计值代价二

这就是出现了（A,6）

这样的话原来已经有（A,8）现在出现了（A,6）

所以我们要把咱的（A,8）要替换掉

F经过GEC到A就是（A,6）

不需要F经过G到E到A了

这样找到一个代价更小的值

路径把它替换掉了

而D的代价多少

F经过GEC到D实际代价是五

再加上D到目标节点B的代价是三

所以是D代价是八

这样的话在C这个位置

（A,6）（D,8）

那么下一个搜索A

到A这个位置的时候

我们发现他只有一个子节点B

对B来说

F经过GECA到B它的实际代价是六

而B到目标节点

B的曼哈顿距离是零

所以B仍然是六

D是八仍然保留

下一半就是B了

到B这个位置时候只剩下DE了

OPEN表里面只剩下（D,1）和（D,8）了

其实我们就找到目标节点

然后我们按照蓝色箭头回溯一下

也就是FGECAB就是我们这个问题的答案

找到这个问题的解了

其实我们已经发现了什么

A※算法

由于考虑了从起始节点到当前节点的实际路径代价

以及当前节点到目标节点的曼哈顿距离

也就是它的代价的估计值

也就是说既考虑了过去到现在的实际代价

又考虑了现在的到将来的代价估计值

以这两个之和减小的方向进行搜索

就形成了A※算法

其实他刚好找到了最优解

总结一下

把这三种算法进行比较一下

均一代价搜索算法

它扩展了八次

能找到最优解

而最佳优先搜索算法扩展了六次

并没有找到最优解

找到了一条可行解

因为它只考虑了当前节点到目标节点的曼哈顿距离

也就是估计值

并没有考虑从起始节点到当前节点的实际代价

而A※算法扩展了七次

最终找到了最优解

那么A※算法既考虑到从过去到现在的实际代价

也考虑了从现在到将来的估计代价

这样的话他就找到了最优解

下面我们看一下这张状态空间图

我们研究一下如何采用A※算法进行搜索

对于起始节点F来说

那么它有一个子节点G

那么对于G节点来说

F到G的实际代价是二

G到目标节点B的代价估计值

曼哈顿距离是3加2等于5

所以得到了

这个时候G所对应的代价是2加5等于七

那么下一步搜索结点G它有两个子节点

一个是E和H

F经过G到E的实际代价是三

E到目标节点的曼哈顿距离是四

所以它代价是3加4

而H

F经过G到H的实际代价是四

而H到目标节点的B的代价是三

就是4加3

那么这时候E和H的代价都是七

我们先搜索谁呢

这时候这两个都可以

先搜索

假定先搜索的是E

那么对于节点E来说

它有两个子节点

一个是C一个是A那么H保持不动OPEN表里头

对于C来说

F经过G到E

它的实际代价加上E

到目标节点B的代价估计值

那就是七了

AF经过GE到A

它的实际代价加上A到目标节点B的代价估计值

加起来A就是九

下一步节点E搜索完之后

我们发现（H,7）（C,7）（A,9）

我们可以先考虑搜索H

这时候我们发现H节点没有子节点的

所以剩下（C,7）(A,9)

下一步先搜索C

到C这个位置

我们发现有两个子节点

一个是A一个是D

A我们发现F经过GEAC它的实际代价是五

再加上A到目标节点B的代价是二

所以A这时候总代价是七

而D的代价经过他的F经过GEC到D的实际代价

加上D到目标节点B的代价估计值是九

这样的话在结点C处

OPEN表里面就是（A,7）(D,9)

由于(A,7)比原来的(A,9)小

所以把它替换掉

这样的话下一步搜索谁

显然搜索是A

在A这个位置

它到子节点只有一个就是B

对B来说

起始节点F经过GECA到B实际代价

加上它的曼哈顿距离是零

这样的话B的总代价是七

这样的话OPEN表里面就是（B,7）(D,9)

下一步显示搜索B

其实B就是目标节点已经找到我们的答案了

按照蓝色箭头进行回溯

我们发现FGECAB刚好就是这个问题的解

其实它也是两条可行解中的最优解