資料結構應用 : Search Strategies

LUFOR129

5 min readApr 14, 2019

最近好久沒有寫文章了 (ಥ﹏ಥ)。上禮拜聽聞成大電機系大一計概要用C++寫走迷宮，有夠猛! 今天這篇來講如何有效率的走出迷宮吧!!

問題描述 :

出現了一個迷宮用 "%" 做為外牆、"S"為起點、"G"為終點，請問由S走向G的策略有哪些?

一、問題思考

我們可以將迷宮問題拆分為五塊:

Initial State : 起始值為S。
Actions: 你可以上下左右走動
Transition Model : 我們的行走策略，是該漫無目的走?
Goal State: 碰到G代表為終點
Path Goal : 本迷宮各個路徑沒有權重

如何走動? 我們可以將行走的過程看作是一個樹狀結構，我今天想從新竹走到高雄，可以畫作。

從新竹出發有桃園、苗栗、宜蘭，等選項，試著走到桃園後，又出現了新北、新竹…等選項。這顆長出來的樹，我們稱之為Search Tree。Tree的葉節點被稱作是Frontier，意味著那些等待被探索的區域。當我們能夠將迷宮簡化為Search Tree後，下一步的問題是，我們該如何最有效率的遍歷樹找到終點。

二、DFS 深度優先

每一次的遍歷節點都會將其所有子節點放入Stack中，利用Stack的後進先出特性，下一個遍歷節點為當前節點的兒子(如果有兒子的話)。結果會是不斷的在同一樹枝上繼續前進，也就是深度優先。為了避免重複遍歷節點，將已將遍歷過的節點存入Set中，並且在遍歷時前先查詢是否在Set中了。

虛擬碼可以寫做:explored = Set() //走過的
frontier = Stack(S)  //將start加入
while frontier!=empty:
    node = frontier.pop()  //先進後出 pop()
    if node == G:
        print("get goal")    //node 不是牆壁且未被探索過時 
    else if node!="%" and node not in explored:
        explored.add(node)
        forEach Actions:   //對於迷宮來說，加入上下左右節點
            frontier.add(node.sonNode)

當goal在樹的深處時DFS會相當容易找到，然而當迷宮可選擇方向過多(樹很寬)，時會相當的廢時間。

三、BFS 廣度優先搜索

和DFS 差不多，唯一差在BFS利用Queue來做遍歷順序的決定，由於Queue的先進先出特性，演算法會優先遍歷同儕節點(sibling)，讓整棵樹以寬度為優先的方向生長。

優缺點與DFS恰好相反，適合那些分支很多的迷宮。

虛擬碼可以寫做:explored = Set()     //走過的
frontier = Queue(S)  //將start加入Queue
while frontier!=empty:
    node = frontier.pop()  //先進先出 pop()
    if node == G:
        print("get goal")
    else if node!="%" and node not in explored:
        explored.add(node)
        forEach Actions:   
            frontier.add(node.sonNode)

四、貪婪算法 Greedy Best First

剛剛上面兩個是我不知道終點在哪裡時，試想今天，我從新竹出發往高雄，雖然不知道高雄怎麼走，但我總知道高雄在南邊我是總不會往北走吧!!

Greedy算法是這樣，我先算出我要走的每一步(Frontier)與終點之間的距離，我選擇走距離最短的那一個。當我每一步都是距離最短時，我們就能得到全局最短距離 (嗎?)

如何快速找出所有Frontiers中與終點最短距離?可以用Min Heap。

虛擬碼可以寫做:explored = Set()     //走過的
frontier = Heap(S)  //將start加入Heap，按距離排序
while frontier!=empty:
    node = frontier.pop()  //pop出最小Node
    if node == G:
        print("get goal")
    else if node!="%" and node not in explored:
        explored.add(node)
        forEach Actions:   
            frontier.add(node.sonNode)

Geedy說的好聽是好聽啦，難道每一步最小就能全局最佳解?

試想一個情境，從新竹到高雄之間的最短距離，假設開車每經過一個縣市時間成本為20、飛機5。利用Greedy 我們會一步步開車向下走當走到高雄時成本為140。如果我們先開車到桃園再搭飛機下去時間成本為60。

可以知道，當路徑有權重時，Greedy不一定為最佳解。也因此出現了A*算法。*當中間沒有死路且所有路徑權重相同時，Greedy最佳解。