A*搜索，類似于剪枝

擴(kuò)展節(jié)點(diǎn)的評價(jià)函數(shù)，包括當(dāng)前節(jié)點(diǎn)到該節(jié)點(diǎn)的代價(jià)，加上該節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的代價(jià)，之和。

優(yōu)先擴(kuò)展這兩個(gè)代價(jià)之和最低的節(jié)點(diǎn)。

（a）初始節(jié)點(diǎn)：arad，

（b）優(yōu)先擴(kuò)展sibiu，因?yàn)閟ibiu的兩個(gè)代價(jià)之和最低

以此類推，

A*搜索，本質(zhì)上也是一種迭代加深深度優(yōu)先搜索。

先擴(kuò)展深度，然后選擇綜合路徑代價(jià)最低的節(jié)點(diǎn)進(jìn)行下一級擴(kuò)展

本質(zhì)上還是一種深度優(yōu)先搜索，但是這種搜索是基于估算最低代價(jià)的搜索，比起單純的深度優(yōu)先搜索，內(nèi)存使用較低

有了評價(jià)函數(shù)的參與，A*搜索更有目的性，且內(nèi)存占用較小，搜索效率較高。