最近对A*算法和IDA*算法有点理解~
以上是久久对所学的知识进行理解和总结的原创~讲得不好还请多多指教~
在求迷宫最优解的时候一般会用dfs和bfs~dfs比较容易实现~但当搜索深度太大的时候有可能爆栈~并且其算法效率是不稳定的~得出来的解不一定是最优解~在用bfs算法如果堆空间足够的时候总是能得出最优解的~是稳定算法~但如果是在一个开放空间内~它所占用的堆空间资源是很多的~通常在做简单处理的时候用dfs就够了~
但用dfs就像上面所说一样~缺点就是搜索深度太大会爆栈~所以在dfs的基础上衍生出了一种IDA*算法~就是在dfs的基础上加了个深度评估函数~可以设定搜索深度阈值为Hmax如果搜索深度大于Hmax就退出搜索~然后搜索其它分支~当所有分支都搜索完毕还没有找到目标地点时就加大Hmax的阈值继续搜索~这样能在找出最短路径的范围与最优解总是在Hmax每次增加的阈值内~改进一下在找到其中一条路径后通过不断缩阈值重新搜索就可以得出最优解~用IDA*算法不像A*算法那样要记录节点并且判断其是否重复~一些中小型迷宫用IDA*是比较理想的~
不过我却自己想到了一种求迷宫最短路径解的A*算法的大概~思路其实很简单~在一个方格迷宫内就是如果已知终点坐标就可以把从起点到终点距离当作一个目标函数~这个目标函数可以有三个优先级~如果移动目标方向与终点方向一致则这个优先级为1~如果目标移动方向与目标方向垂直~则这个优先级为-1~如果移动方向与目标方向相反~则这个优先级为-2，可以先搜索所有优先级为1的所有节点~将其存入队列~如果当开放堆目标函数返回值没有1时就可以搜索-1的最后再搜索-2的~以此类推~直到找到最短路径~
个人感觉A*算法的难点之一就是要定期对堆进行维护~
先简单说说什么叫开放堆和关闭堆~
所谓开放堆就是指即将要对其进行开放搜索的对象~而不对其进行开放搜索的对象就可以理解为关闭堆~其实关闭堆可以理解成假出队~因为用A*算法可能要对其维护而保留~
如果开放堆和关闭堆相差深度过大则要考虑开启关闭堆~这里先说一条公式f(x)=h(x)+g(x)##其中f(x)就是目标价值量~h(x)就是当前遍历深度g(x)就是当前开放堆的搜索代价~
在这里每次遍历对f(x)的最小值进行优先搜索~
举个具体点的例子~在求四方格迷宫最短路径解里h(x)就是表示搜索深度~每层遍历搜索深度会增加~而g(x)可以理解为对出口距离的评估函数~当前移动距离与目标距离的偏移量叫做曼哈顿距离~如果曼哈顿距离为正数则意味着该移动更接近目标距离~反之则意味着该移动远离目标~由于h(x)和g(x)都是确定的~每个格对应的f(x)也是确定的~可以从f(x)的最小值开始将对应节点设为开放堆进行搜索~这样得出的一个解会是一个相当不错的解~如果h(x)为0则意味着不考虑搜索深度~这样就意味着对关闭堆进行维护~这样的搜索只能得出当前开放堆的最优解而不是当前所有堆的局部最优解更不可能是全局最优解~这样可能即使得出一个解也会是路径很长的一个解~如果g(x)为0~则不考虑搜索代价这样就A*算法就会退化成bfs了~如果目标估计函数g(x)合理(如何取值合理这里先不深究~具体还要代码验证)则可以得出其最优解~
当然~求方格迷宫还可以进一步优化~可以考虑沿边界遍历~这里g(x)除了可以用对目标距离进行评估外还可以对开放堆衍生的节点数目进行评估~衍生节点越少的g(x)的值越少~这样可以避免对空间开放度较大的迷宫搜索资源过大~这样搜索就可以起到沿墙遍历而避免开放空间过大的效果~
感觉A*算法可以算得上是最好的算法~虽然对于现在我这个水平实现起上来还是相当有难度的~
以上只是我个人的理解~如果讲得有什么问题还请大神指教
2017-03-19 02:24
，不过平时写代码时这些算法还真用到过。