Informed search algorithms (接收資訊的搜尋演算法)

Presentation on theme: "Informed search algorithms (接收資訊的搜尋演算法)"— Presentation transcript:

1 Informed search algorithms (接收資訊的搜尋演算法)

2 Outline Best-first search (最佳優先搜尋法)
Greedy best-first search (貪婪最佳優先搜尋) A* search

3 Review(複習): Tree search
A search strategy is defined by picking the order of node expansion (搜尋策略為挑選節點展開的順序)

4 Review: Uninformed search strategies(無接收資訊的搜尋策略)
(無接收資訊的的搜尋策略僅使用問題本身定義的可用資訊) Breadth-first search Uniform-cost search Depth-first search Depth-limited search Iterative deepening search

5 Best-first search(最佳優先搜尋)
Idea: use an evaluation function f(n) for each node 想法：對每個節點使用一個評估函數 estimate of "desirability" 有利條件的評估 展開最有利之未展開節點 Implementation:實作 Order the nodes in fringe in decreasing order of desirability 依據有利條件的評估值由大而小排列待展開的節點順序 Special cases　（特別的例子） greedy best-first search A* search

6 增加各個城鎮到Bucharest的直線距離之資訊

7 Greedy best-first search
Evaluation function評估函數 f(n) = h(n) (heuristic啟發式) 從n狀態到目標狀態的花費 e.g., hSLD(n) = straight-line distance from n to Bucharest（到Bucharest的直線距離) (貪婪最佳優先搜尋法展開似乎最接近目標的節點)

8 Greedy best-first search example

9 Greedy best-first search example

10 Greedy best-first search example

11 Greedy best-first search example

12 Properties of greedy best-first search(貪婪最佳優先搜尋法的特質)
Complete? No – can get stuck in loops(可能遭遇迴圈), e.g., Iasi  Neamt  Iasi  Neamt  (m is the maximum depth of the search space)但一個好的啟發式可以產生極大的改善 Space? O(bm) -- keeps all nodes in memory Optimal? No, why? (如何改進貪婪最佳優先搜尋法)

13 A* search (想法:避免展開已知較大花費的路徑)
Evaluation function(評估函數) f(n) = g(n) + h(n) g(n) = cost so far to reach n (到n點的已知花費) h(n) = estimated cost from n to goal(評估從n點到目標還需要的花費, 啟發式) (評估經由n 到目標所需的總花費)

14 A* search example

15 A* search example

16 A* search example

17 A* search example

18 A* search example

19 A* search example

20 Admissible heuristics (可採納的啟發式)
(簡言之:低估) An admissible heuristic never overestimates the cost to reach the goal, i.e., it is optimistic 直線距離不會超過實際的距離

21 Optimality of A* A* expands nodes in order of increasing f value
Gradually adds "f-contours" of nodes Contour i has all nodes with f=fi, where fi < fi+1

22 Properties of A* Complete? Yes (指數成長) Space? Keeps all nodes in memory
Optimal? Yes Optimally efficient No other optimal algorithm is guaranteed to expand fewer nodes than A* (沒有其他的最佳解演算法能保證展開較A*少的節點數)

23 Memory-bounded heuristic search
IDA* (Iterative-deepening A*) RBFS (Recursive best-first search) MA* (Memory-bounded A*) SMA* (Simplified MA*)

24 IDA* The main difference (與ID method比較主要差別)
Cutoff using f-cost rather than the depth 使用花費取代深度來加深展開層數

25 RBFS (Recursive best-first search)
Its structure is similar to that of a recursive depth-first search, it keeps track of the f-value of the best alternative path available from any ancestor of the current node.(其結構與RDFS相似, 但他記錄其他路徑的最佳f-value) If the current node exceeds this limit, the recursion unwinds back to the alternative path. (如果目前的展開節點花費已超過紀錄的限制, 則轉換到另一個路徑展開) 用途: 節省記憶體的使用

26

27 Example of RBFS Arad Sibiu Timisoara Zerind Arad Fagaras Oradea
∞ Arad 366 447 Sibiu Timisoara Zerind 449 393 447 415 Arad Fagaras Oradea Rimmicu 413 646 415 526 Craiova Pitesti Sibiu 526 417 553

28 Example of RBFS (cont.) Arad Sibiu Timisoara Zerind Arad Fagaras
∞ Arad 366 447 Sibiu Timisoara Zerind 449 393 447 417 Arad Fagaras Oradea Rimmicu 417 646 415 526 Sibiu Bucharest 450 591

29 Example of RBFS (cont.) Arad Sibiu Timisoara Zerind Arad Fagaras
∞ Arad 366 447 Sibiu Timisoara Zerind 449 393 447 447 Arad Fagaras Oradea Rimmicu 417 646 450 526 447 Craiova Pitesti Sibiu 526 417 553 Bucharest Craiova Rimmicu 418 615 607

30 SMA* Proceeds just like A* (處理過程像A*)
Expanding the best leaf until memory is full (持續展開最佳的節點直到記憶體已經用完) Drops the worst leaf node (with highest f-value) 丟掉最糟的節點資料 Backs up the value of the forgotten node to its parent (將丟掉節點的花費值記在他們的父節點內)

31 隨堂作業 在地圖的問題中, 直線距離作為啟發函數可以達到很好的效果, 那在8 puzzles 的問題中, 你會如何定啟發函數(沒有標準答案, 盡量發揮…)