Solving problems by searching 利用搜尋法解決問題

Presentation on theme: "Solving problems by searching 利用搜尋法解決問題"— Presentation transcript:

1 Solving problems by searching 利用搜尋法解決問題

2 Outline 問題解決代理人 問題種類 問題公式化 範例 基本搜尋演算法 一種目標導向代理人 單一狀態(完全可被觀察) 在部分資訊下搜尋
Uninformed

3 Problem-solving agents
解決問題的四步驟 目標公式化Goal formulation 定義何謂成功的狀態 問題公式化Problem formulation 再給定目標的情況下有哪些可行的動作與狀態 搜尋Search 決定可能達到目標的行動順序然後決定最佳的動作 執行Execute 產生動作

4 Problem-solving agents
The environment is static, observation, discrete, deterministic. (Open-loop system)

5 Example: Romania地圖 某人目前在Romania的Arad 明天有飛機要從Bucharest起飛
公式化目標: Formulate goal 準時到達Bucharest 公式化問題: Formulate problem 狀態:許多城市 動作:在城市間開車 尋找問題解法 一序列的城市, 例如: Arad, Sibiu, Fagaras, Bucharest

6 Example: Romania

7 Selecting a state space
真實世界是複雜的 為解決問題, 狀態空間必須抽象化 (Abstract) state = set of real states (Abstract) action = complex combination of real actions e.g., "Arad  Zerind" represents a complex set of possible routes, detours, rest stops, etc. The abstraction is valid if the path between two states is reflected in the real world. (Abstract) solution = set of real paths that are solutions in the real world 每一個抽象化的行動一定比原來真實的問題要簡單些

8 Example: The 8-puzzle states? Initial state? actions? goal test?
path cost?

9 Example: The 8-puzzle states? locations of tiles
Initial state? Any state can be initial actions? move blank left, right, up, down goal test? = goal state (given) path cost? 1 per move [Note: optimal solution of n-Puzzle family is NP-hard]

10 Tree search algorithms
Basic idea: 在已探索的狀態下持續展開探索後繼者的狀態(expanding states) Basic search algorithms 搜尋狀態空間Search the state space 經由樹狀結構搜尋 Root=initial state. Nodes and leafs generated through successor function.

11 Tree search example

12 Tree search example

13 Tree search example

14 Implementation: general tree search

15 Search strategies 搜尋策略:展開節點的順序 策略的好壞可依下列量度決定:
完整性(completeness): does it always find a solution if one exists? 時間複雜度(time complexity): number of nodes generated 空間複雜度(space complexity): maximum number of nodes in memory 最佳化(optimality): does it always find a least-cost solution? Time and space complexity are measured in terms of b: maximum branching factor of the search tree d: depth of the least-cost solution m: maximum depth of the state space (may be ∞)

16 Uninformed search strategies
廣先搜尋Breadth-first search 一致花費搜尋Uniform-cost search 深先搜尋Depth-first search 深度限制搜尋Depth-limited search 反覆加深搜尋Iterative deepening search

17 Breadth-first search 逐層展開未展開過的節點 Implementation:
使用 FIFO queue, i.e., new successors go at end

18 Breadth-first search 逐層展開未展開過的節點 Implementation:
使用 FIFO queue, i.e., new successors go at end

19 Breadth-first search 逐層展開未展開過的節點 Implementation:
使用 FIFO queue, i.e., new successors go at end

20 Breadth-first search 逐層展開未展開過的節點 Implementation:
使用 FIFO queue, i.e., new successors go at end

21 Properties of breadth-first search
Complete? Yes (if b is finite) Time? 1+b+b2+b3+… +bd + b(bd-1) = O(bd+1) Space? O(bd+1) (keeps every node in memory) Optimal? Yes (if cost = 1 per step) 缺點: 使用空間的問題很嚴重

22 Uniform-cost search 展開最少花費的節點 Implementation:
(佇列順序依據路徑花費排列) Equivalent to breadth-first if step costs all equal Complete? Yes Time? O(bceiling(C*/ ε)) where C* is the cost of the optimal solution, step cost ≥ ε Space? O(bceiling(C*/ ε)) 節點展開順序由小而大

23 Uniform-cost search 3 5

24 Uniform-cost search 3 5 4 3

25 Uniform-cost search 3 5 2 4 3 3 4 goal

26 Depth-first search 往深度展開節點 Implementation:
使用 LIFO queue, i.e., put successors at front

27 Depth-first search 往深度展開節點 Implementation:
使用 LIFO queue, i.e., put successors at front

28 Depth-first search 往深度展開節點 Implementation:
使用 LIFO queue, i.e., put successors at front

29 Depth-first search 往深度展開節點 Implementation:
使用 LIFO queue, i.e., put successors at front

30 Depth-first search 往深度展開節點 Implementation:
使用 LIFO queue, i.e., put successors at front

31 Depth-first search 往深度展開節點 Implementation:
使用 LIFO queue, i.e., put successors at front

32 Depth-first search 往深度展開節點 Implementation:
使用 LIFO queue, i.e., put successors at front

33 Depth-first search 往深度展開節點 Implementation:
使用 LIFO queue, i.e., put successors at front

34 Depth-first search 往深度展開節點 Implementation:
使用 LIFO queue, i.e., put successors at front

35 Depth-first search 往深度展開節點 Implementation:
使用 LIFO queue, i.e., put successors at front

36 Depth-first search 往深度展開節點 Implementation:
使用 LIFO queue, i.e., put successors at front

37 Depth-first search 往深度展開節點 Implementation:
使用 LIFO queue, i.e., put successors at front

38 Properties of depth-first search
Complete? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path  complete in finite spaces Time? O(bm): terrible if m is much larger than d but if solutions are dense, may be much faster than breadth-first Space? O(bm), i.e., linear space! Optimal? No (e.g. node J is a solution, DFS stops)

39 Depth-limited search = depth-first search with depth limit l,
i.e., nodes at depth l have no successors Recursive implementation:

40 Iterative deepening search
由Depth-limited search 演化而成 每輪將深度放大一層

41 Iterative deepening search l =0

42 Iterative deepening search l =1

43 Iterative deepening search l =2

44 Iterative deepening search l =3

45 Iterative deepening search
Number of nodes generated in a depth-limited search to depth d with branching factor b: NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd Number of nodes generated in an iterative deepening search to depth d with branching factor b: NIDS = (d+1)b0 + d b^1 + (d-1)b^2 + … + 3bd-2 +2bd-1 + 1bd For b = 10, d = 5, NDLS = , , ,000 = 111,111 NIDS = , , ,000 = 123,456 Overhead = (123, ,111)/111,111 = 11%

46 Properties of iterative deepening search
Complete? Yes Time? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd) Space? O(bd) Optimal? Yes, if step cost = 1

47 Summary of algorithms Step cost =1

48 Repeated states 如果在搜尋過程中,未解決重複狀態的問題可能導致無法求解

49 隨堂作業 The 8-puzzle 請用BFS向下展開兩層(繪出樹狀結構) 說明如果採用DFS可能會產生何種問題?要如何解決?
如果使用Uniform-cost search會退化成那種基本的搜尋法(BFS or DFS), 理由?