A problem is defined by four items: initial state, successor function, goal test, path cost
A solution is a sequence of actions leading from the initial state to a goal state
Tree search algorithm
Basic idea:
offline, simulated exploration of state space by generating successors of already-explored nodes
A state is a (representation of) a physical configuration
A node is a data structure constituting part of a search tree includes state, parent, children, depth, path cost g(n)
States do not have parents, children, depth, or path cost!
The Expand function creates new nodes, filling in the various fields and using the SuccessorFn of the problem to create the corresponding states.
Frontier implemented as priority queue of nodes ordered according to strategy
Uninformed search strategies
A strategy is defined by picking the order of node expansion
Uninformed strategies use only the** information available** in the definition of the problem（uninformed 表示 该策略探测所有相应顺序的点或者只能根据Initial点到下一个点的情况 来决定下一个点的选择，不能参考下一个点到目标点的情况；inform 则可以同时参考这两种情况，并对下一个点做出选择。）
Breadth-first search (blind search)
Uniform-cost search
Depth-first search (blind search)
Depth-limited search (blind search)
Iterative deepening search(blind search)
Search strategies
Strategies are evaluated along the following dimensions:
- completeness—does it always find a solution if one exists?
- solution optimality—does it always find a least-cost solution?
- time complexity—number of nodes generated (or expanded)
- space complexity—maximum number of nodes in memory
Time and space complexity are measured in terms of
- b—maximum branching factor of the search tree（一个node一次最多可以产生的nodes数量）
- d—depth of the shallowest solution
- m—maximum depth of the state space (may be ∞)
Breadth-first search
Definition: Expand shallowest unexpanded node, frontier is a FIFO queue（随机选择一个点）
Effect:
Complete: Yes (if b and d are finite)
Time: 1 + b + b^2 + b^3 + . . . + b^d + (b^(d+1) − b) = O(b^(d+1))
Space: O(b^(d+1))
Optimal: Yes if cost = 1 per step; not optimal in general
Uniform-cost search
Definition: Expand least-cost unexpanded node, frontier = queue ordered by path cost, lowest first（和上一个的遍历方式一样，不同处在于选择next node 的方式）
Equivalent to breadth-first if step costs all equal.
Effect:
Complete: Yes, if step cost ≥ ǫ
Optimal: Yes—nodes expanded in increasing order of g(n)
区别：
- 贪婪算法只选择当前下一步cost最小的值，然后提交。
- uniform cost 会计算tree 里 所有探测到的non-visited node的total-cost（从root 到下一个点），选择最小的点提交。
eg. For a given node A, having child nodes B,C,D with associated costs of (10, 5, 7), uniform cost algorithm will choose C, as it has a lower cost. After expanding C, see nodes E, F, G with costs of (40, 50, 60). uniform cost algorithm will choose D(0+7, E is 40 +5).
greedy algorithm will choos C and E.
Depth-first search
Definition: Expand deepest unexpanded node, frontier = LIFO queue
Effect:
Complete: No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path ⇒ complete in finite spaces
Time: O(b^m): 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! (deepest node+ancestors+their siblings)
Optimal: No
Iterative deepening search
Performs a series of depth limited depth-first searches
Combines advantages of breadth-first and depth-first search:
- completeness
- returns shallowest solution
- use linear amount of memory
Effect:
Complete: Yes (if b and d are finite)
Time: O(b^d)
Space: O(bd)
Optimal: Yes, if step cost = 1 Can be modified to explore uniform-cost tree
Depth-limited search
depth-first search with depth limit l
cutoff: no solution within the depth limit
failure: the problem has no solution
