AI 筆記9 - Un-informed Search: Uniform cost search

UCS: BFS的變形

這個cost我們之前都沒有考慮過，如果path cost不是1的話，對BFS來說，不能保證optimality，因為search tree中最淺的solution不見得是optimal的。

BFS的搜尋是以深度當作layer，而UCS的則是以cost function g當作layer：

改寫expand function

先定義expand: 意思就是從fringe中拿出下一個要explore的node。

當cost不再是1的時候，我們改成以least cost children來優先從fringe中拿出來explore。

注意我們除了用min-heap之外，我們也要update heap中的unexplored node cost，因為我們可能找到cost of path to root更少的path。

Performance

complete: Yes! 如果solution是finite cost 。UCS保證會找到solution。

time: 這比較難分析了，因為他search layer是by cost不是by depth，但是我們的search space仍然用search tree model，所以還是要給一個近似深度的函數。我們假設optimal solution的path cost to root = C*，而每個state - state action cost至少是e，則可以定義出一個“effective depth”＝ C* / e，至少要搜尋這麼多的layer，這相當於d factor in BFS ，所以time complexity:

space: 和time complexity一樣。

optimal: YES，因為這就是UCS彌補BFS的目的。



這是一個complete & optimal search algorithm!

範例

我們要找以下graph S->G的最短路徑。

1. explore and expand S

2. explore C，因為cost最少：

3. explore A

4. explore E，注意我們update B的cost成 5，因為經由explore E我們發現一條cost更少的路徑從S到B (S -> C -> E -> B)，這就是演算法中所謂decreaseKey的意義：

5. explore B:

6. explore D:

7. explore F:

8. reach Goal