演算法上課筆記 （第五章 Tree searching strategy）

這筆記好像有點久沒補充了....
唉最近都在忙專題跟其他案子
沒什麼時間整理筆記....前面的之後找時間補看看吧！Orz


第五章是 Tree searching strategy

簡單而言 ,一個問題至少會有一個或多個解,而在這裡就是把這些解做成tree。運用做成tree的方式,可以決定該發展哪個解答,這樣一來就可以加快得到想要解的速度。

首先要講講tree的寬與深
下面是tree的範例（圖片取自維基百科）

若是以寬度為優先的話 拿到裡面東西的順序就會是：
2 ->7 5 -> 2 6 9 ->5 11-> 4
若是以深度度為優先的話 拿到裡面東西的順序就會是：

2 ->7 ->2 ->6 ->5 ->11 ->5 ->9 ->4

所以就有了以下四種方法

1.Breadth-First Search (寬度優先）
2.Depath-First Search(深度優先）
1.2都是就如同上面的解釋一般


3.Hill Climbing (深度優先)
這個會先把 下一步所有的節點先找到
在選擇最符合尋找條件的節點(比如說最小或最大)
再往下發展,直到找到符合條件的節點,或是走完所有節點
p.s 若有多個節點都很符合條件 還是只會選一個
以下是範例
圖片取自（http://www-g.eng.cam.ac.uk/mmg/teaching/artificialintelligence/nonflash/problem6.htm）

4.Best-first search (深度與寬度擇優）
跟Hill Climbing很相似
但是在篩選最符合條件的節點時 ,若有多的條件都很符合的節點,則每一點都會去發展
以下是範例
圖片取自（http://www-g.eng.cam.ac.uk/mmg/teaching/artificialintelligence/nonflash/problem6.htm）

p.s 3.4 都有可能找不到最佳解