文章目錄
- 一、狀态空間圖
- 二、搜尋方法
一、狀态空間圖
（深度優先）
1.狀态空間圖不一定總能畫出來，隻有兩個要素：狀态、連接配接
2.建立狀态空間圖，需要：
– 定義狀态形式
– 定義狀态之間的連接配接的意義
– 定義問題的解的形式（狀态解、路線解、最優值解等）
執行個體：
二、搜尋方法
1.盲目/通用搜尋
主要指：深度優先搜尋、寬度優先搜尋
2.貪心搜尋
貪婪搜尋政策：總是做出在目前看來最好的選擇，或者采用使得目前步驟獲利最大的選擇，是以也叫做貪婪算法。
– 貪婪搜尋政策不考慮整體最優，僅求取局部最優。因而也可以看作是一種“盲目”的政策。
– 貪婪搜尋不能保證得到最優解，但搜尋速度非常塊。
– 對一些特定問題很有效。
總結：
深度、寬度優先搜尋通用性強，但效率慢
貪婪搜尋速度非常塊，但基本上找不“準”
3.啟發式搜尋
3.1 A算法
3.2 A算法*