圖搜索算法

圖搜索技術(shù)時(shí)人工智能中的核心技術(shù)之一，并且在其他場(chǎng)合也有著非常廣泛的應(yīng)用。這里的圖稱(chēng)為狀態(tài)圖，指由節(jié)點(diǎn)和有向(帶權(quán))邊所做成的網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)即狀態(tài)。按照搜索的方式不同，圖搜索一般分為樹(shù)式搜索和線(xiàn)式搜索。兩者最大的區(qū)別就在于搜索過(guò)程中所記錄的軌跡不同，顧名思義，樹(shù)式搜索記錄的是一顆搜索樹(shù)，而線(xiàn)式搜索是一條折線(xiàn)。我們一般用一個(gè)Closed表的數(shù)據(jù)結(jié)構(gòu)來(lái)記錄搜索節(jié)點(diǎn)，對(duì)于樹(shù)式搜索來(lái)說(shuō)，Closed表存儲(chǔ)的正是一顆不斷成長(zhǎng)的搜索樹(shù)，而線(xiàn)式搜索存儲(chǔ)的則是一條不斷伸長(zhǎng)的折線(xiàn)，如果能找到目標(biāo)節(jié)點(diǎn)的話(huà)，它本身就是搜索的路徑。而樹(shù)式搜索需要通過(guò)目標(biāo)節(jié)點(diǎn)進(jìn)行回溯，直至初始節(jié)點(diǎn)，從而找到路徑。