转载请注明作者：phylips@bmy

出处：http://duanple.blog.163.com/blog/static/70971767200811344425606/

引言：
现实中的很多问题都可以看成搜索问题
众里寻她千百度，蓦然回首那人却在灯火阑珊中。
就算是人类的思维，很多时刻也是在进行着搜索，搜索存储在脑中的记忆元素
就算身在社会中，我们也还是在不同的时间搜索着不同的东西。

这些只是普遍意义上的搜索，在算法中，很多问题时间上是在进行着状态空间搜索，希望找到一条从初始状态到目标状态的排序，比如排序，8数码，8皇后，最短路

而进行搜索的方法有很多，最简单的如盲目搜索，与之相反的一种就是启发式搜索，就是有效的利用当前的信息，根据一个评估函数，选择一个比较有前途的待扩展节点进行扩展。启发式搜索也叫做A算法，而A*算法则是一种特殊形式的A算法。这也算是人工智能的一个分支内容，网上的一些资料，比如lrj的那本黑书，还有一些介绍A*算法的文章，基本上都是A*算法的应用，所以很多概念，并不准确，而对于理解A*算法需要的一些关键性的证明也是没有提供的。

本文，就从人工智能的角度来介绍这个算法，主要内容参考自NJ 尼尔森的<<人工智能>>，这本书对启发式算法进行了比较深入的解释，关键是其中的一些关键性的证明都是存在的，比如证明A*算法的可接纳性，一致性条件及定理。

关键概念：

介绍一些关键的概念：
首先，对于状态空间搜索，是可以提出一个通用的搜索算法框架的，而这个框架中则主要使用了open,和closed两个表。open表，保存了当前待扩展节点，closed表则保存已扩展节点，而BFS DFS也可以纳入这个框架，比如DFS中使用的white black gray染色，实际于 open closed便是对应的。

对于启发式搜索一般具有如下评估函数f*(n) = g*(n)+h*(n)，f*(n)表示从起始点经过n到达目标的估计函数
g*(n)表示从起始点到达节点n的花费函数，比如对于最短路问题，可能就是已经发现的从出发点，到当前节点的最小cost， h*(n)表示从当前状态n到目标状态的估计花费。

对于h*(n)施加如下约束，g*(n) >= g(n)  ,h*(n) <= h(n),即估计花费从是小于等于实际最小花费，则启发式搜索就是A*算法。而A*算法是可接纳的，也就是说如果存在一条到达目标的最优路径，A*算法可以保证找到这条路径。

继续对A*算法的h函数施加约束，可以保证满足一致性，或者叫单调性，约束是：对于任意的状态ni,nj
h*(ni) - h*(nj) <= c(ni,nj)
一致性可以保证，当 A*扩展节点n时，它已经找到了到达节点n的最优路径。

通用搜索框架：
1）生成一个包含初始点n0的搜索树Tr,并把n0放入open表
2）初始化一个为空的closed表
3）如果open表为空，则失败退出
4）取出open表第一个元素，将该元素放入closed表，设该元素为n
5）如果n为目标，则可以从n沿着Tr的弧进行回溯，找到解决方案，成功退出
6）扩展节点n，生成n的后继节点集M，可以利用一个parent指针，将这些节点指向n，从而维护Tr树，将这些节点放入open表
7）按任意模式或者启发式方式对open表进行排序
8）返回步骤3

该算法可以用来执行 DFS BFS 以及A*，如果是BFS则只需要把待扩展 节点放到open表的尾部即可
如果是DFS 则只需要把待扩展 节点放到open表的头部即可，均不需要执行7）
而对于启发式搜索来说，要根据启发函数进行步骤7）。


A*算法中可能需要解决的问题：
观察以上步骤，实际上在加入两个表的操作中，可能遇到一些特殊情况，就是原表中已经包含了当前要插入的这个点。这时候该如何处理。对应的在搜索树，或者搜索图中，行进的过程中又到达了原来曾经扩展或者已经在待扩展open表的那个点。

比如在8数码中，实际上每两个状态如果可达，则肯定上可以相互到达的，也就是说对于节点n的每个后继都可以吧节点n作为它的后继。这样我们就需要解决这类问题，对于这种情况只要，保证在扩展节点的后继M中不要包含它的双亲就行了，考虑到更长的循环，我们还要把双亲修改成祖先，即后继M中不要包含它的祖先。这样我们可能就需要一个数据结构用来保存节点的祖先。

但是仍有可能通过不同的路径到达相同的节点，解决这个问题的一个简单方法就是忽略它，不去检查。也就是说不去检查是否一个节点已经存在于open 或者closed中。这样实际上就允许通过不同的路径到达相同的节点，这个相同节点在Tr中重复多次出现，而这个重复的次数就是算法发现到达该点的不同路径的数目。

当然，如果对A*算法，加入一致性约束，这样就可以保证当A*首次扩展节点n时，它已经找到了到达该节点的最佳路径。

为了防止不满足一致性约束的A*算法进行重复搜索，需要对A*算法进行修改，由于可以沿着不同路径到达同一点，导致A*算法实际上产生的是一个搜索图G，而不是树，而树Tr刚好包含在这个图里。之所以要保留这个图，是因为可能后面的那个路径要比现在这个更优，在发现这样的路径时我们要更新那个搜索树。

A*算法框架：
1）生成一个包含初始点n0的搜索树Tr,并把n0放入open表
2）初始化一个为空的closed表
3）如果open表为空，则失败退出
4）取出open表第一个元素，将该元素放入closed表，设该元素为n
5）如果n为目标，则可以从n沿着Tr的弧进行回溯，找到解决方案，成功退出
6）扩展节点n，生成n的后继节点集M，在G中n的祖先不能出现在m中，在G中放置M，使他成为n的后继
7）
从M中每一个不在G中的节点放置一个指向n的指针，并且加入open中(即不在open也不在closed中的节点)
对于在open的那些，则判断是否需要更新，如果更小则更新
对于在closed中的那些，则判断是否需要更新，如果更小则更新
8）按照启发式方式对open表进行递增排序
9）返回步骤3

A*算法的一些证明和性质：

对图和h函数施加一些条件，可以保证A*算法得到最优解：
1）图中每个节点的后继是有限的
2）图中所有弧的代价都大于某个正数
3）对于图中所有节点，h函数<= 实际代价

证明略。
主要依赖于如下引理：


h函数取值越小，所具有的启发性越小，而查看的节点就越多，dikstra算法实际上就是h函数=0，的特殊的A*算法。

一致性约束。。。

IDA*算法。
迭代加深的A*算法，初始设置截断值为h*(n0),以后逐步增大