什么是启发式搜索？

本篇将会结合实例解析启发式搜索，帮助大家更好理解。

启发式搜索（英文：heuristic search）是一种改进的搜索算法。它在普通搜索算法的基础上引入了启发式函数，该函数的作用是基于已有的信息对搜索的每一个分支选择都做估价，进而选择分支。简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解。

（1）贪婪最佳优先

在Dijkstra算法中，我已经发现了其最终要的缺陷，搜索存在盲目性。在这里，我们只针对这个痛点，采用贪婪最佳优先搜索来解决。如何解决？我们只需稍微改变下观念即可，在Dijkstra算法中，优先队列采用的是，每个顶点到起始顶点的预估值来进行排序。在贪婪最佳优先搜索采用的是，每个顶点到目标顶点的预估值来进行排序。

两者的搜索过程对比如下动图所示：

明显看到右边的算法（贪婪最佳优先搜索 ）寻找速度要快于左侧，虽然它的路径不是最优和最短的，但障碍物最少的时候，他的速度却足够的快。这就是贪心算法的优势，基于目标去搜索，而不是完全搜索。

（2）A star算法

我们找到了最短路径和搜索顶点最少数量的两种方案，Dijkstra 算法和贪婪最佳优先搜索。接下来能否汲取两者的有点选择既速度快又能得到最优解的算法？

A star算法正是这么做了，它吸取了Dijkstra 算法中的当前代价，为每个边长设置权值，不停的计算每个顶点到起始顶点的距离，以获得最短路线，同时也汲取贪婪最佳优先搜索算法中不断向目标前进优势，并持续计算每个顶点到目标顶点的距离，以引导搜索队列不断想目标逼近，从而搜索更少的顶点，保持寻路的最优解。A star算法在运算过程中，每次从优先队列中选取f(n)值最小（优先级最高）的节点作为下一个待遍历的节点。A star算法使用两个集合来表示待遍历的节点，与已经遍历过的节点，这通常称之为open_set和close_set。

A star算法优先队列排序方式基于估价值，估价值由顶点到起始顶点的距离（代价）加上顶点到目标顶点的距离(启发函数）之和构成。

A star算法、贪婪最佳优先、Dijkstra算法三者的静态效果图如下：

由于概念过于抽象，这里使用例题讲解。

题目描述：辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式：

第一行有 22 个整数 TT（1 \le T \le 10001≤T≤1000）和 MM（1 \le M \le 1001≤M≤100），用一个空格隔开，TT 代表总共能够用来采药的时间，MM 代表山洞里的草药的数目。

接下来的 MM 行每行包括两个在 11 到 100100 之间（包括 11 和 100100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式：

输出在规定的时间内可以采到的草药的最大总价值。

代码实现：

很明显的背包吧。这里我们写一个启发式搜索，所谓的启发式搜索，就是我们在搜索的时候用一个估价函数去帮助和优化我们的决策。当我们选择一样草药的时候没什么好说的，直接往下搜，当我们不选的时间，我们有估价函数来帮助我们判断，接下来的价值是否大于我们目前的最优值，如果不大于那么显然我们没有必要进行下一轮的搜索。你可以理解为这个估价函数是帮助我们剪枝的一个工具。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
int n,m,ans;
const int maxn=105;
struct node {
    int a,b;
    double val;
}e[maxn];

bool cmp (node a,node b) {
    return a.val>b.val;
}

int f(int t,int v) {
   int tot=0;
   for (int i=0;i+t<=n;i++) {
       if (v>=e[t+i].a) {
           v-=e[i+t].a;
           tot+=e[i+t].b;
       }
       else return (int ) (tot+v*e[i+t].val);
   }
   return tot;
}

void dfs (int t,int pass,int v) {

   ans=max (ans,v);
   if (t>n) return ;
   if (f(t,pass)+v>=ans) dfs (t+1,pass,v);
   if (e[t].b<pass) dfs (t+1,pass-e[t].a,v+e[t].b);

}

int main () {
    cin>>m>>n;
    for (int i=1;i<=n;i++) {
        cin>>e[i].a>>e[i].b;
        e[i].val=1.0*e[i].b/e[i].a;
    }   
    sort (e+1,e+1+n,cmp);
    dfs (1,m,0);
    cout<<ans<<endl;
    
    return 0;
}