AI - Ch2 無資訊的搜尋策略 Uninformed Search Strategies

無資訊(uninformed)就是指我們只會根據問題定義的資訊來搜尋，所以又稱為blind search。以下的各種方法只是在決定從邊緣(frontier)拿出結點的順序。

• 廣度優先搜尋(Breadth-first search, BFS)
• 成本一致搜尋(Uniform-cost search)
• 深度優先搜尋(Depth-first search, DFS)
• 有限深度搜尋(Depth-limited search)
• 疊代深入搜尋(Iterative deepening search)

廣度優先搜尋 (Breadth-first search, BFS)

• 做法 : 邊緣節點為一個先進先出的佇列。
• 使用時機 : Used when branching factor is small and shallow solutions exist
• Quality of the result
• Completeness : Yes
• Optimality : No
• Time: $O(b^{d+1})$, very bad. (b: avg branching factor, d: goal depth)
• Space: $O( b^{d+1})$, very bad.
• why the exp is "d+1" ?    Because level‐d will be expanded except Goal, $b+b^2+…+b^d+(b^{d+1}‐b) = O(b^{d+1})$

成本一致搜尋 (Uniform-cost search)

• 做法：將邊緣節點存為一個由$g$排序的序列。每次都選取路徑成本最低的邊緣節點。
• $g(n)$：路徑成本，$n$代表節點(狀態)。由起始節點至節點n的路徑成本。
• 使用時機 : find the shortest path (measured by sum of distances along path)
• Quality of the result
• Completeness : Yes
• Optimality : Yes, but ONLY IF path costs are non‐negative.
• Time : very bad, in some cases $O(b^{d+1})$ such as BFS.
• Space : very bad, in some cases $O(b^{d+1}) $such as BFS.

深度優先搜尋 (Depth-first search, DFS)

• 做法：邊緣節點為一個堆疊
• 使用時機 : Used when many solutions of unknown depth; avoid deep or infinite trees.
• Quality of the result
• Completeness : No,  除非狀態空間有限，而且沒有loop產生
• Optimality : No.  因為找到解就停止
• Time : $O(b^m)$, very bad.
• Space: $O\left(b \times m \right)$, very good.
• Techniques for Avoiding Repeated States
• Method 1 : Do not allow return to parent state(cannot avoid triangle loops)
• Method 2 : Do not create paths containing cycles (do not keep any child-node which is also an ancestor in the tree)
• Method 3 : Never generate a state generated before (Must keep track of all possible states, using a lot of memory)
• E.g., 8-puzzle problem, we have 9! = 362,880 states
• Methods 1 and 2 are most practical, and work well on most problems

有限深度搜尋 (Depth-limited search)

• 做法：對DFS的搜尋深度$L$加以限制。
• Quality of the result
• Completeness : No, UNLESS $S_{depth} < L$.
• Optimality : No, UNLESS $S_{depth} < L$.
• Time: $O(b^L)$, bad but limited.
• Space: $O\left(b \times L\right)$, great and controllable.

疊代深入搜尋演算法 (Iterative deepening search, IDS)

• 做法：反覆用逐漸增加的深度限制來進行有限深度搜尋。
• 使用時機 : Preferred when search space is large and solution depth is unknown.
• DFS is efficient in space, but has no min path length guarantee
• BFS finds min‐step path but requires exponential space
• In chess playing, computers usually do iterative deepening search.
• Quality of the result
• Completeness : Yes.
• Optimality : No, UNLESS path cost is a nondecreasing function of depth.
• Time : $O(b^d)$, bad. 
• Why $O(b^d)$?   Because $(d)b+(d‐1)b^2+…+(1)b^d = O(b^d)$, unlike $BFS = b+b^2+…+b^d+(b^{d+1}‐b) = O(b^d+1)$
• Space : $O\left(b \times d\right)$, great. 
• Each run of depth‐limited search $k$ require $O\left(b \times k \right)$, Max space requirement $O\left( b \times d \right)$

雙向搜尋(Bidirectional search)

• 做法：出自起始節點的一個分支與出自目標節點的另一個分支相遇。
• 使用時機 : Used when operators are reversible, and goal states are known and few.
• Quality of the result
• Completeness : Yes, if both BFS, and cost function is monotonic in terms of steps.
• Optimality : Yes, when both searches are BFS.
• Time : $O(b^{d/2})$, bad but better than $O(b^d)$
• Space : $O(b^{d/2})$, bad but better than $O(b^d)$

Summary

• A review of search
• A search space consists of states and operators: it is a graph
• A search tree represents a particular exploration of search space
• There are various extensions to standard “blind search”
• Iterative deepening
• Bidirectional search
• Repeated states can lead to infinitely large search trees
• We looked at methods for detecting repeated states
• All of the search techniques so far are “blind” in that they do not look at how far away the goal may be: next we will look at informed (heuristic) search, which directly tries to minimize the distance to the goal.