本篇將會(huì)結(jié)合實(shí)例解析啟發(fā)式搜索，幫助大家更好理解。

啟發(fā)式搜索（英文：heuristic search）是一種改進(jìn)的搜索算法。它在普通搜索算法的基礎(chǔ)上引入了啟發(fā)式函數(shù)，該函數(shù)的作用是基于已有的信息對(duì)搜索的每一個(gè)分支選擇都做估價(jià)，進(jìn)而選擇分支。簡(jiǎn)單來說，啟發(fā)式搜索就是對(duì)取和不取都做分析，從中選取更優(yōu)解或刪去無效解。

（1）貪婪最佳優(yōu)先

在Dijkstra算法中，我已經(jīng)發(fā)現(xiàn)了其最終要的缺陷，搜索存在盲目性。在這里，我們只針對(duì)這個(gè)痛點(diǎn)，采用貪婪最佳優(yōu)先搜索來解決。如何解決？我們只需稍微改變下觀念即可，在Dijkstra算法中，優(yōu)先隊(duì)列采用的是，每個(gè)頂點(diǎn)到起始頂點(diǎn)的預(yù)估值來進(jìn)行排序。在貪婪最佳優(yōu)先搜索采用的是，每個(gè)頂點(diǎn)到目標(biāo)頂點(diǎn)的預(yù)估值來進(jìn)行排序。

兩者的搜索過程對(duì)比如下動(dòng)圖所示：

明顯看到右邊的算法（貪婪最佳優(yōu)先搜索 ）尋找速度要快于左側(cè)，雖然它的路徑不是最優(yōu)和最短的，但障礙物最少的時(shí)候，他的速度卻足夠的快。這就是貪心算法的優(yōu)勢(shì)，基于目標(biāo)去搜索，而不是完全搜索。

（2）A star算法

我們找到了最短路徑和搜索頂點(diǎn)最少數(shù)量的兩種方案，Dijkstra 算法和貪婪最佳優(yōu)先搜索。接下來能否汲取兩者的有點(diǎn)選擇既速度快又能得到最優(yōu)解的算法？

A star算法正是這么做了，它吸取了Dijkstra 算法中的當(dāng)前代價(jià)，為每個(gè)邊長(zhǎng)設(shè)置權(quán)值，不停的計(jì)算每個(gè)頂點(diǎn)到起始頂點(diǎn)的距離，以獲得最短路線，同時(shí)也汲取貪婪最佳優(yōu)先搜索算法中不斷向目標(biāo)前進(jìn)優(yōu)勢(shì)，并持續(xù)計(jì)算每個(gè)頂點(diǎn)到目標(biāo)頂點(diǎn)的距離，以引導(dǎo)搜索隊(duì)列不斷想目標(biāo)逼近，從而搜索更少的頂點(diǎn)，保持尋路的最優(yōu)解。A star算法在運(yùn)算過程中，每次從優(yōu)先隊(duì)列中選取f(n)值最?。▋?yōu)先級(jí)最高）的節(jié)點(diǎn)作為下一個(gè)待遍歷的節(jié)點(diǎn)。A star算法使用兩個(gè)集合來表示待遍歷的節(jié)點(diǎn)，與已經(jīng)遍歷過的節(jié)點(diǎn)，這通常稱之為open_set和close_set。

A star算法優(yōu)先隊(duì)列排序方式基于估價(jià)值，估價(jià)值由頂點(diǎn)到起始頂點(diǎn)的距離（代價(jià)）加上頂點(diǎn)到目標(biāo)頂點(diǎn)的距離(啟發(fā)函數(shù)）之和構(gòu)成。

A star算法、貪婪最佳優(yōu)先、Dijkstra算法三者的靜態(tài)效果圖如下：

由于概念過于抽象，這里使用例題講解。

題目描述：辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大?！?/p>

如果你是辰辰，你能完成這個(gè)任務(wù)嗎？

輸入格式：

第一行有 22 個(gè)整數(shù) TT（1 \le T \le 10001≤T≤1000）和 MM（1 \le M \le 1001≤M≤100），用一個(gè)空格隔開，TT 代表總共能夠用來采藥的時(shí)間，MM 代表山洞里的草藥的數(shù)目。

接下來的 MM 行每行包括兩個(gè)在 11 到 100100 之間（包括 11 和 100100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。

輸出格式：

輸出在規(guī)定的時(shí)間內(nèi)可以采到的草藥的最大總價(jià)值。

代碼實(shí)現(xiàn)：

很明顯的背包吧。這里我們寫一個(gè)啟發(fā)式搜索，所謂的啟發(fā)式搜索，就是我們?cè)谒阉鞯臅r(shí)候用一個(gè)估價(jià)函數(shù)去幫助和優(yōu)化我們的決策。當(dāng)我們選擇一樣草藥的時(shí)候沒什么好說的，直接往下搜，當(dāng)我們不選的時(shí)間，我們有估價(jià)函數(shù)來幫助我們判斷，接下來的價(jià)值是否大于我們目前的最優(yōu)值，如果不大于那么顯然我們沒有必要進(jìn)行下一輪的搜索。你可以理解為這個(gè)估價(jià)函數(shù)是幫助我們剪枝的一個(gè)工具。

#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;
}