《人工智能：計算Agent基礎》——3.8 本章小結

本節書摘來自華章計算機《人工智能：計算agent基礎》一書中的第3章，第3.8節,作者：（加）david l.poole,alan k.mackworth 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

許多實際問題可以抽象為在圖中進行路徑搜尋的問題。

寬度優先搜尋和深度優先搜尋可以在沒有任何圖以外的額外資訊的情況下通過圖來找到路徑。

a 搜尋可以使用啟發函數，來估計從一個節點到目标節點的花費。如果這個估計低于實際花費，a能保證找到最低花費路徑。

疊代深化搜尋和深度優先分支界限搜尋可以用來找到最低花費路徑，且能比像a 之類的算法節省更多的記憶體，因為a算法會儲存多條路徑。

當圖很小的時候，動态規劃搜尋可以用來紀錄從每一個節點到目标節點的最低花費路徑的實際花費，這可以用來找到最優路徑的下一段弧。