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

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

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

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

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

Example: Romania

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 每一個抽象化的行動一定比原來真實的問題要簡單些

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

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]

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

Tree search example

Tree search example

Tree search example

Implementation: general tree search

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 ∞)

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

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

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

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

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

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) 缺點: 使用空間的問題很嚴重

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*/ ε)) 節點展開順序由小而大

Uniform-cost search 3 5

Uniform-cost search 3 5 4 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

Iterative deepening search l =0

Iterative deepening search l =1

Iterative deepening search l =2

Iterative deepening search l =3

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 = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111 NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456 Overhead = (123,456 - 111,111)/111,111 = 11%

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

Summary of algorithms Step cost =1

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

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