無(wú)信息搜索的意思并不是無(wú)目的搜索，而是沒有問題定義之外額外的信息

目的信息是搜索的必要條件，只有明確的目的，才能使搜索的后繼節(jié)點(diǎn)判斷，當(dāng)前節(jié)點(diǎn)是否離目標(biāo)狀態(tài)越來越近。

拓展后繼節(jié)點(diǎn)的三種類型

寬度優(yōu)先，深度優(yōu)先，一致代價(jià)搜索

無(wú)信息搜索的評(píng)價(jià)和分類，是以三種方式生成后繼節(jié)點(diǎn)的順序來定義的。

評(píng)價(jià)標(biāo)準(zhǔn)包括下面四條：

數(shù)值化判斷三種擴(kuò)散后繼節(jié)點(diǎn)的方式

寬度優(yōu)先搜索

FIFO，先進(jìn)先出

關(guān)于圖的寬度優(yōu)先搜索的算法說明：

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

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

frontier 參數(shù)指的是一個(gè)先進(jìn)先出的隊(duì)列，里面記錄了當(dāng)前節(jié)點(diǎn)，作為唯一的元素

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

算法的主要步驟是loop do這個(gè)循環(huán)

首先判斷 frontier這個(gè)參數(shù)是否為空，如果為空則報(bào)錯(cuò)（無(wú)當(dāng)前節(jié)點(diǎn)，即報(bào)錯(cuò)）

然后從frontier表中， 按照FIFO先進(jìn)先出的原則，彈出一個(gè)最前面的節(jié)點(diǎn)，記錄入node中，作為當(dāng)前節(jié)點(diǎn)，

并將當(dāng)前節(jié)點(diǎn)的node狀態(tài)，放入explored表中，代表已探索過該節(jié)點(diǎn)。

對(duì)于該問題當(dāng)中的每一個(gè)動(dòng)作，再做如下循環(huán)

首先擴(kuò)展一個(gè)節(jié)點(diǎn)，并將該節(jié)點(diǎn)放入child 子節(jié)點(diǎn)參數(shù)中，

如果該子節(jié)點(diǎn)，不在explored集合，也不在frontier集合中，

則進(jìn)一步子循環(huán)，判斷

是否該子節(jié)點(diǎn)通過了問題所對(duì)應(yīng)的目標(biāo)，如果已通過，則返回該子節(jié)點(diǎn)對(duì)應(yīng)的解 solution

否則，將該子節(jié)點(diǎn)插入frontier中，作為下一個(gè)探索的可能對(duì)象（FIFO，因?yàn)閒rontier智能包括一個(gè)節(jié)點(diǎn)狀態(tài)，所以該子節(jié)點(diǎn)將作為下一個(gè)被探索的對(duì)象。）

簡(jiǎn)單的二叉樹寬度優(yōu)先搜索的方式。

寬度優(yōu)先搜索的擴(kuò)散，

先是出發(fā)節(jié)點(diǎn)A

然后是A的兩個(gè)后繼節(jié)點(diǎn)B和C

然后是B的兩個(gè)后繼節(jié)點(diǎn) D和E

寬度優(yōu)先搜索相當(dāng)于簡(jiǎn)單遍歷方式的搜索，

所以它的時(shí)間復(fù)雜性和空間復(fù)雜性是一致的。

寬度優(yōu)先搜索的最大問題是這是一個(gè)簡(jiǎn)單遍歷搜索，

對(duì)于系統(tǒng)的內(nèi)存、時(shí)間都造成很大的壓力

比如下面的漢諾塔問題就是一個(gè)簡(jiǎn)單遍歷的操作方式。