一致代價搜索，實(shí)質(zhì)上是選擇路徑代價最低的節(jié)點(diǎn)來優(yōu)先擴(kuò)展

一致代價搜索算法解釋：

首先和寬度優(yōu)先搜索相同，先定義四個變量，四個變量的定義與寬度優(yōu)先搜索也相同。

變量 node 定義是當(dāng)前狀態(tài)的節(jié)點(diǎn)，初始化，該變量為問題的初始狀態(tài) problem INITIAL-STATE

PATH-TEST 定義為路徑的代價，也即步驟代價。初始化為零 （初始狀態(tài)的當(dāng)前節(jié)點(diǎn)，即為初始狀態(tài)節(jié)點(diǎn)）

frontier 參數(shù)是按照路徑的代價進(jìn)行排序，（含義就是代價最低的路徑優(yōu)先探索）

explored （已探索過的節(jié)點(diǎn)之集合），初始化為一個空集?

loop do 主循環(huán)

第一個步驟，首先口判斷frontier表是否為空，如果為空，則返回失敗

如果frontier不為空，則從frontier中彈出一個路徑成本最低的值，計入node節(jié)點(diǎn)表中，

? ? 如果該節(jié)點(diǎn)能夠通過目標(biāo)測試，則將該節(jié)點(diǎn)作為解solution返回。

? ? 否則將該節(jié)點(diǎn)放入explored表中，代表該節(jié)點(diǎn)已探索過。

? ? 對于該節(jié)點(diǎn)的每一個動作（該節(jié)點(diǎn)本身已經(jīng)處于路徑代價最低的路徑上），執(zhí)行下列子循環(huán)語句：

? ? ? ? 將該節(jié)點(diǎn)的下一級節(jié)點(diǎn)，計入child 子節(jié)點(diǎn)表中

? ? ? ? ? ? ? ?判斷：如果該子節(jié)點(diǎn)不在explored表或者不在frontier表中，

? ? ? ? ? ? ? ?則將該子節(jié)點(diǎn)，插入frontier表中。

? ? ? ? 否則，如果child在frontier中，且該chilld具有最高的路徑代價

則將該子節(jié)點(diǎn)child作為當(dāng)前的frontier節(jié)點(diǎn)中。

優(yōu)先擴(kuò)展路徑代價最低的子節(jié)點(diǎn)，

與寬度優(yōu)先搜索相比，

一致代價搜索的時間復(fù)雜性和空間復(fù)雜性是一樣的。