启发式搜索

【这一章在某些地方笔者自己也没完全弄清楚，比如在递归最优搜索处没有找到一个很好的例子来理解，比如如何选择启发式函数等等一系列的问题，希望有大神能指明讲解。所以本章重要的只是介绍A*算法流程和简单优化并介绍引出一些改进的A*算法】

使用评估函数

除了搜索过程不是从开始节点统一向外扩展外，本章描述的搜索过程有点像广度优先搜索，不同的是，它会优先顺着有启发性和具有特定信息的节点搜索下去，这些节点可能是到达目标的最好路径。我们称这个过程为最优（best-first）或启发式搜索。下面是其基本思想。

我们常常可以为最优搜索制定好评估函数。如在8数码问题中，可以用不正确位置的数字个数作为状态描述好坏的一个度量，将这个标准应用于8数码问题中。如下图所示。

下，可以看到搜索相当直接的朝着目标进行。

这个例子提出了两个重要的问题。

• 我们如何为最优搜索决定评估函数？
• 最优搜索的特性是什么？他能找到到达目标节点的好路径么？

一个通用的图搜索算法

为了更准确地解释本章的启发式搜索过程，这里提出一个通用的图搜索算法，它允许各种用户，进行定制。我们把这个算法叫做图搜索。下面是它的定义：

这个算法可以用开执行最优搜索、广度优先搜索或深度优先搜索。在广度优先搜索中，新节点只要放在OPEN的尾部即可（先进先出，FIFO），节点不用重排。在深度优先搜索中，新节点放在OPEN的开始（后进后处，LIFO）。在最优（启发式）搜索中，按节点的启发式方法来重排OPEN。

1. 算法A*

因为动作是可逆的，即任何节点n的每一个后继都可以使n作为它的一个后继。在建立8数码搜索树中忽略了这些循环。因此我们将算法的第六步改为：

则最后完整的A*算法如下：

2. 迭代加深的A*

在上一章，讲过广度优先搜索的存储需求会随着搜索空间中目标深度的增加呈指数递增。尽管好的启发式搜索减少了分支因子，但启发式搜索还是有如一样的缺点。在上一章中介绍的迭代加深搜索，不但允许我们找到最小代价路径，而且存储需求随着深度增加呈线性增长。由此提出的迭代加深A*（IDA*）方法能获得同启发式搜索相似的好处。通过使用IDA*算法并行实现能获得更高的效率。

3. 递归最优搜索

【此处笔者也没看懂，希望大牛能给出一些实例进行讲解，这里直接将网上找到的资料原文po出来，希望有大神指点！】

启发式函数和搜索效率

搜索效率的一个度量是有效分支因子B，他描述了一个搜索过程朝着目标前进的激烈程度。假设搜索找到了一个长为d的路径，生成了N个节点，那么B就是有以下属性的树上每个节点的后继个数。

• 数中每个非树叶节点都有B个后继
• 数中的树叶节点的深度均为d
• 数中的节点总数是N

因此，B和路径长度d以及生成的总结点数N之间有下列关系：

归纳一下，有三个重要因素影响算法A*的效率：

• 被发现的路径的代价（长度）
• 在发现路径中被扩展的节点数
• 计算h估计的计算量

选择适当的启发式函数可以让我们平衡这些因素以最大化搜索效率。

搜索算法
Ø 利用计算机的高性能来有目的的穷举一个问题解空间的部分或者所有的
可能情况，从而求出问题的解的一种计算机算法

启发式搜索算法

Ø 利用启发式信息引导算法搜索，达到减少搜索范围，降低问题复杂度的
目的
Ø 将人类求解问题的经验固化到求解算法

估价函数

基于一般图搜索算法，定义一个评价函数$f$，对当前的搜索状态进行评估，从Open表中找出一个最有希望的节点来扩展。
f的一般定义
$$f(x)=g(x)+h(x)$$
$g(x)$:从根节点（起始节点）到当前节点的估计路径长，$g^{\ast }(x)的估计$
$h(x)$:从当前节点到目标节点的估计路径长，$h^{\ast }(x)的估计$

$g^{\ast }(x)$:从根节点（起始节点）到当前节点的最短路径长
$h^{\ast }(x)$:从当前节点到目标节点的最短路径长

爬山法
Ø只考虑与目标之间的差距，即$g(n)=0$

分支界限法
Ø 总是扩展具有最小耗散值的路径
Ø 使用g(n)，h(n)=0

** 动态规划法**
Ø 总是扩展具有最小耗散值的路径
Ø 总是删除明显不可能的路径
Ø 使用g(n)，h(n)=0

A算法伪代码

1 G=G0 (G0=s), Open := (s), 计算f(s) := g(s) + h(s), Closed=();
2 Loop: If Open = ( ) Then Exit(Fail);
3 n := First(open), Remove(n, Open), Add(n, Closed);
4 If Goal(n) Then Exit(Success);
6 Expand(n) →{mi}, 计算f(n, mi) := g(n, mi) + h(mi), G:=Add(mi, G);
7 标记和修改指针：
	Add(mj, Open), 标记mj到n的指针； //新节点
	If f(n, mk) < f(mk) Then f(mk) := f(n, mk), //Open表中未扩展节点
		标记mk到n的指针；
	If f(n, ml)<f(ml,) Then f(ml):=f(n, ml), //Closed表中已扩展节点
		标记ml到n的指针, Add(ml, Open);
8 Open中的节点按f值从

A*算法

在A算法中，如果满足条件：$h(n)\le h^{\ast }(n)$
则A算法称为A*算法。

$f\ast (start)=f\ast (aim)=h\ast (start)=g\ast (aim)=f\ast (n)$
start为起始点 aim为终点，n为最佳路径start到aim的任意节点

A*定理和推论
定理1：对于有限图，A*算法一定终止。
算法每次循环从OPEN表里去掉一个节点，而有限图的OPEN表内只有有限个节点加入。所以无论算法是否找到解都会正常停止。

定理2：若算法不终止，则OPEN表上的点的f值将越来越大。

定理3：A*结束前，Open表中必存在$f(n)\le f^{\ast }(s)$

定理4：若问题有解，算法终止时一定找到最优解，即可达。

定理5：OPEN表上任一具有$f(n)\le f^{\ast }(s)$ 的节点n，最终都将被算法选作扩展的节点。

定理6：A*选作扩展的任一节点n，有$f(n)\le f^{\ast }(s)$

定理7：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有$h_2(n)>h_1(n)$，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。

算法改进

因A算法第6步对$m_1$ 类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。

解决的途径:
对h加以限制：对h增加适当的限制，使得第一次扩展一个节点时，就找到了从S到该节点的最短路径。
对算法加以改进：对算法加以改进，避免或减少节点的多次扩展。

改进的条件:
可采纳性不变
不多扩展节点
不增加算法的复杂性

实践

模板代码

#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 1000


int n,m,s,t;
double x[maxn],y[maxn];     //点的坐标 
bool edge[maxn][maxn];          //二维数组存边 
int pos[maxn];              //每个节点的前驱结点，记录路径 
double length;              //最短路径长度 
vector<int> path;           //最短路径 

double gi[maxn],f[maxn];    //gi 耗散值  f评价值

double distance(int A,int B){   //点A与点B的距离 
    return sqrt((x[A]-x[B])*(x[A]-x[B])+(y[A]-y[B])*(y[A]-y[B]));
}

double A_star(int s,int t); //A_star算法主体过程，pos数组记录每个节点的前驱结点

int main(){
    cin>>n>>m>>s>>t;
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];        //保存点的坐标 
    }
    for(int i=0;i<m;i++){
        int A,B;
        cin>>A>>B;              //保存边 
        edge[A][B]=edge[B][A]=true;
    }

    memset(f,-1,sizeof(f));
    length=A_star(s,t);         //算法主体 
    int tmp=t;
    while(tmp!=s){
        path.push_back(tmp);
        tmp=pos[tmp];
    }path.push_back(tmp);       //路径记录 


    cout<<length<<endl;         //输出答案 
    for(int i=path.size()-1;i>0;i--) cout<<path[i]<<" ";
    cout<<path[0]<<endl;

    return 0;
}
/* 你的代码将会被嵌入在这个部分 */

思路：
先写出评估函数f(n)
在本题中不难发现理想的g(x)就是从起点到x点的最佳路径（这时候就需要图算法来进行g(x)的迭代），而h(x)根据下界的定义，就是两点之间的直线距离


利用priority_queue作为储存的容器，这样我们可以对储存的点以f[s]进行上升排序，从而减少排序时间的损耗

后续将起始点s的f(s)和s存入pq中，进行后续的

while循环
	//需要改变的量
	从open中pop f(p)最小的点
	判断是不是目标点t
		是返回 路径(t)
	遍历临界点 v
		得到从起始点到p再到v的g(x)
		若小于现有的g(x)
		进行g(x)更新，并得到f(x)存放进入open表中
			//此时p相当于已经从open表中放到close表中了

需要注意的是，close表直接使用gi[x]来进行判断，因为我们所需要的最小g(x)是会根据不同路径产生不同的情况，我们需要抽出来最小的g(x)进行迭代。

double h(int point)//离终点的预计最小状态
{
    return distance(t, point);
}
// double g(int point)//离起点的确切距离
// {
//     return gi[point];
// }
#include<climits>
priority_queue<pair<double,int>, vector<pair<double, int>>, greater_equal<pair<double, int>> > pq;
double A_star(int s,int t)
{
    //初始化部分
    for(int i = 0; i < n; i++)
        gi[i] = INT_MAX;
    gi[s] = 0;
    f[s] = gi[s] + h(s);
    pq.push(make_pair(f[s], s));


    while(!pq.empty())
    {
        int point = pq.top().second;
        pq.pop();
        if(point == t)//找到对应的点
            return f[t];
        for(int i = 0; i < n; i++)//遍历相邻点
        {
            if(edge[point][i])
            {
                double g_new = gi[point] + distance(point, i);
                if(g_new < gi[i])
                {
                    gi[i] = g_new;
                    f[i] = gi[i] + h(i);
                    pos[i] = point; //i的前一个点为point
                    pq.push(make_pair(f[i], i));
                }
            }
        }
    }
    return f[t];

}

A* 算法是启发式搜索算法中的经典，经常应用于图搜索、路径搜索和规划中。这里以八数码问题状态空间图的搜索为例，初步介绍以A*算法为代表的启发式搜索。

搜索算法可分为两大类：无信息的搜索算法和有信息的搜索算法。无信息的搜索又称盲目搜索，其特点是只要问题状态可以形式化表示，原则上就可用使用无信息的搜索，无信息搜索有如下常见的几种搜索策略：广度优先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入优先搜索、双向搜索。我们说DFS和BFS都是蛮力搜索，因为它们在搜索到一个结点时，在展开它的后续结点时，是对它们没有任何‘认识’的，它认为它的孩子们都是一样的‘优秀’，但事实并非如此，后续结点是有好有坏的。好，就是说它离目标结点‘近’，如果优先处理它，就会更快的找到目标结点，从而整体上提高搜索性能。
为了改善上面的算法，我们需要对展开后续结点时对子结点有所了解，这里需要一个估值函数，估值函数就是评价函数，它用来评价子结点的好坏，因为准确评价是不可能的，所以称为估值。这就是我们所谓的有信息搜索。如果估值函数只考虑结点的某种性能上的价值，而不考虑深度，比较有名的就是有序搜索（Ordered-Search），它着重看好能否找出解，而不看解离起始结点的距离（深度）。如果估值函数考虑了深度，或者是带权距离（从起始结点到目标结点的距离加权和），那就是A* 如果不考虑深度，就是说不要求最少步数，移动一步就相当于向后多展开一层结点，深度多算一层，如果要求最少步数，那就需要用A*。简单的来说A*就是将估值函数分成两个部分，一个部分是路径价值，另一个部分是一般性启发价值，合在一起算估整个结点的价值。

一、启发性信息和估价函数

1.启发性信息：

启发式搜索是利用知识来引导搜索过程的，达到减少搜索范围的目标，使得尽量先走“最有希望的方向”，从而降低问题复杂度。这里就是要根据知识，设计启发性信息（启发函数），启发性信息可以：
1）帮助确定扩展节点的信息
2）有效地帮助决定哪些后继节点应被生成
3）能决定在扩展一个节点时哪些节点应从搜索树上被删除
启发性信息的设计至关重要，太弱可能就起不到效果，甚至退化为盲目搜索，太强就会可能导致找不到最优的解。

2.估价函数：

Evaluation Function：是一种对于节点“希望”的度量，表示这个节点在通向目标节点最佳路径上的“希望”或者概率，以此为指导选择优先扩展的节点。
估价函数的选取有很多方式：节点处于最佳路径上的概率；节点与目标节点集之间距离的度量或者差异的距离；根据状态优劣的打分等等。
注意：估价函数和之前提到的代价函数不一样，代价函数是预先知道的，而估价函数是根据知识预测得到的

二、启发式搜索过程（A和A*算法）

1.A算法

对于求解过程中，启发式搜索与盲目搜索的区别就在于对于OPEN表的重排，优先选择最优希望的节点扩展。
重排的依据就是：从起始节点到达该节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价，即

2.A*算法

对于A算法中，g(n)和h(n)，尤其是h(n)该如何选择呢，选择如果超过实际代价太多，也就是太强，可能会找不到解；太弱就会在搜索过程中，扩展一些多余的节点，对于具体问题要根据具体知识进行设计。这里定义如果对于所有的n都有h(n)≤h* (n)，也称h(n)为h* (n)的下界，则是一种相对保守的搜索，但是这样是可纳的。
采用h*(n)的下界h(n)为启发函数的A算法，称为A* 算法。当h=0时，A* 算法就变为有序搜索算法。
上图中，f*(n)=g*(n)+h*(n)是从s经过n到g的最优路径的实际代价，而g(n)和h(n)就分别是对实际代价的估计！
所以在设计估价函数时，要尽可能的使得和h(n)逼近h*(n)，但又不超过h*(n)，这样得到的时完备可纳的，有时复杂度最小的，但是如何知道有没有超过h*(n)呢？感觉还是需要具体问题具体分析。

3.求解过程描述

搜索过程大致和盲目搜索一样，只是在OPEN表排序不同，其中涉及到的排序算法，去重算法等都会影响算法的效率。

对于上面图中“调整亲子关系和指针”：
1）如果j既不在OPEN表中，也不在CLOSED表中，则用估价函数f把它添入OPEN表，从j加一指向父辈节点i的指针。
2）如果j已在OPEN表或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值.。如果新的f值较小，则作以下几种操作：
a. 以此新值取代旧值
b.从j指向i, 而不是指向它的父辈节点
c.如果节点j在CLOSED表中, 则把它移回OPEN表

4.八数码问题设计估价函数

这里以之前提到的八数码问题为例：
1）估价函数1：f(n)=d(n)+w(n)
d(n)为n的深度
w(n)为不在位的棋子数
这样w(n)≤h*(n)，是满足A* 算法的限制条件，所有一定能找到最优解，但是这样设计估价函数并不是最优的。
2）估价函数2：f(n)=d(n)+p(n)
p(n)为不在位的棋子与其目标位置的距离之和
这样p(n)≤h*(n)，也是满足A* 算法的限制条件。
w(n)是不在位的棋子数，不够贴切，错误选用节点加以扩展，而p(n)是更接近于h*(n)的h(n)，其值是节点n与目标状态节点相比较，每个错位棋子在假设不受阻拦的情况下，移动到目标状态相应位置所需走步的总和。p(n)不仅考虑了错位因素，还考虑了错位的距离（移动次数），也就是启发性信息更多了。

5.启发式搜索特点和实际工程应用

1）对于启发性信息：设对同一个问题定义了两个A* 算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n) > h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。
2）在实际应用中理论上是设计接近、又总是≤h*(n)的h(n)，但是这种设计往往也要消耗大量的时间，如果h(n)本身设计的复杂，每次计算时消耗在h(n)上的复制度也就会增加，使得求解变慢。
3）对于搜索深度和启发性信息的权衡：

搜索图的浅层时，让w取较大值，突出启发式函数的作用，加速向纵深方向搜索。
搜索到较深的层次时，让w取较小值，以使g(n)所占权重大，并确保wh(n)≤h* (n)，引导搜索向横广方向发展，寻找到较短的解答路径。