（以“==A*算法== ===问题简化=== 我们把一切类似问题抽象成一个最短路问题：记<m>D_AB</m>为在一个图中A、B两点间的最短路，求两点S...”为内容创建页面） |
|||
| 第1行： | 第1行： | ||
==A*算法== | ==A*算法== | ||
| − | === | + | ===A*能解决的问题简化=== |
| − | 我们把一切类似问题抽象成一个最短路问题：记<m> | + | 我们把一切类似问题抽象成一个最短路问题：记<m>D_{AB}</m>为在一个图中A、B两点间的最短路，求两点S、T的<m>D_{ST}</m>。 |
| − | ===A* | + | ===A*算法=== |
| − | + | 类似于搜索，我们把已经搜索过的点集合记作P。接下来我们要搜一点A（A与P中一点有连边），将它加入P中，那么我们当然希望A一定在ST的最短路上，于是： | |
::::<m>D_{ST}=D_{SA}+D_{AT}</m> | ::::<m>D_{ST}=D_{SA}+D_{AT}</m> | ||
::::记作：<m>F(A)=G(A)+H(A)</m> | ::::记作：<m>F(A)=G(A)+H(A)</m> | ||
其中，如果G，H都是已知量，那么直接找满足F(A)最小的A即可。然而实际情况是G已知，那么我们通过估计出一个H*(A)得到： | 其中，如果G，H都是已知量，那么直接找满足F(A)最小的A即可。然而实际情况是G已知，那么我们通过估计出一个H*(A)得到： | ||
::::<m>F^*(A)=G(A)+H^*(A)</m> | ::::<m>F^*(A)=G(A)+H^*(A)</m> | ||
| − | 那么F*(A) | + | 那么F*(A)越小，A属于最短路的可能性越大。就满足条件的最小F*(A)把它加入P中（可以用堆处理），继续扩展点，直到T点也在集合P中，就得到答案了。这就是A*算法。 |
===关于H*(A)的分析=== | ===关于H*(A)的分析=== | ||
假设我们找到一种神奇的H*(A)=H(A)，那么无疑F*(A)就是最优解。 | 假设我们找到一种神奇的H*(A)=H(A)，那么无疑F*(A)就是最优解。 | ||
| 第16行： | 第16行： | ||
当<m>H^*(A)>H(A)</m>时，我们可能会在没有搜索到最优解的时候就错误的结束，A*算法保证能找到可行解，但不一定是最优解。 | 当<m>H^*(A)>H(A)</m>时，我们可能会在没有搜索到最优解的时候就错误的结束，A*算法保证能找到可行解，但不一定是最优解。 | ||
| − | 当<m>H^*A=0</m>时，我们会搜索所有解，退化成bfs。 | + | 当<m>H^*(A)=0</m>时，我们会搜索所有解，退化成bfs。 |
| − | 当<m>F^*(A)=XA(X\ | + | 当<m>F^*(A)=Len_{XA}</m>(点<m>X{\in}P</m>，XA有连边，<m>Len_{XA}</m>指的XA之间的边长)时，这是Dijkstra算法。 |
===时间复杂度=== | ===时间复杂度=== | ||
| − | <m>|H(x) - H^*(x)| = O(\log H^*(x))</m> | + | <m>|H(x)-H^*(x)|=O({\log}H^*(x))</m> |
| − | ===关于IDA*===通过控制G(A)进行迭代加深搜索，与迭代加深的深度优先搜索类似。可以避免判重等的时间、空间复杂度（代码也好写），但是在大数据量的时候不如普通的A*。==参考资料和扩展阅读==https://en.wikipedia.org/wiki/A* | + | ===关于IDA*=== |
| + | 通过控制G(A)进行迭代加深搜索，与迭代加深的深度优先搜索类似。可以避免判重等的时间、空间复杂度（代码也好写），但是在大数据量的时候不如普通的A*。 | ||
| + | ==参考资料和扩展阅读== | ||
| + | https://en.wikipedia.org/wiki/A*_search_algorithm | ||
| + | http://m.blog.csdn.net/blog/CreationAugust/41929843 | ||
| + | |||
| + | [[分类:启发式搜索]] | ||
我们把一切类似问题抽象成一个最短路问题：记为在一个图中A、B两点间的最短路，求两点S、T的
。
类似于搜索，我们把已经搜索过的点集合记作P。接下来我们要搜一点A（A与P中一点有连边），将它加入P中，那么我们当然希望A一定在ST的最短路上，于是：
其中，如果G，H都是已知量，那么直接找满足F(A)最小的A即可。然而实际情况是G已知，那么我们通过估计出一个H*(A)得到：
那么F*(A)越小，A属于最短路的可能性越大。就满足条件的最小F*(A)把它加入P中（可以用堆处理），继续扩展点，直到T点也在集合P中，就得到答案了。这就是A*算法。
假设我们找到一种神奇的H*(A)=H(A)，那么无疑F*(A)就是最优解。
当时，我们就会搜索到更多的无效解，然而最后的P集合一定包含最优路径，A*算法一定有最优解。
当时，我们可能会在没有搜索到最优解的时候就错误的结束，A*算法保证能找到可行解，但不一定是最优解。
当时，我们会搜索所有解，退化成bfs。
当(点
，XA有连边，
指的XA之间的边长)时，这是Dijkstra算法。
通过控制G(A)进行迭代加深搜索，与迭代加深的深度优先搜索类似。可以避免判重等的时间、空间复杂度（代码也好写），但是在大数据量的时候不如普通的A*。
https://en.wikipedia.org/wiki/A*_search_algorithm http://m.blog.csdn.net/blog/CreationAugust/41929843
CloudLunar