CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
搜索（Search）
Why Search
很多人工智能的问题都可以用搜索来求解（例如博弈）
形式化方法
Once the problem has been formulated as a state space search, various algorithms can be utilized to solve the problem.
A solution to the problem will be a sequence of actions/moves that can transform your current state into state where your desired condition holds.
将一个问题形式化为搜索问题的组分如下：
 搜索空间
 动作：状态间的转移
 初始状态
 目标状态
 形式化一些启发方法，使得更快到达目标状态
搜索算法
Inputs
 a specified initial state (a specific world state or a set of world states representing the agent’s knowledge, etc.)
 指定的初始状态(特定的世界状态或代表 Agent 知识的一组世界状态等)
 a successor function S(x) = {set of states that can be reached from state x via a single action}.
 后继函数 S(X)={可通过单个动作从状态 x 到达的状态集}。
 a goal test a function that can be applied to a state and returns true if the state is satisfies the goal condition.
 目标测试可应用于状态的函数，如果状态满足目标条件，则返回 TRUE。
 A step cost function C(x,a,y) which determines the cost of moving from state x to state y using action a. ($C(x,a,y) = \infty$ if a does not yield y from x)
 阶跃成本函数 C(x，a，y)，它确定使用动作 a 从状态 x 移动到状态 y 的成本。($C(x，a，y)=\infty$，如果 a 没有从 x 产生 y)
Output
 a sequence of states leading from the initial state to a state satisfying the goal test.
 从初始状态到满足目标测试的状态序列。
 The set of successors of a state x might arise from different actions, e.g.,
 状态 x 的后继者集合可能产生于不同的动作，例如，
 x → a → y
 x → b → z
 Successor function S(x) yields a set of states that can be reached from x via a (any) single action.
 后继函数 S(X)产生可以通过(任何)单个动作从 x 到达的一组状态。
 Rather than just return a set of states, we might annotate these states by the action used to obtain them:
 不只是返回一组状态，我们可以通过用于获取这些状态的操作来注释这些状态：
 S(x) = {<y,a>, <z,b>} y via action a, z via action b.
 S(x) = {<y,a>, <y,b>} y via action a, also y via alternative action b.
树形搜索
 Frontier is the set of states we haven’t yet explored/expanded, and want to explore
 Frontier（边界）是我们尚未探索/扩展并且想要探索的一组状态。
 Initial call has Frontier = the set of initial state
 Initial Call has Frontier=初始状态集
TreeSearch(Frontier, Sucessors, Goal? )
If Frontier is empty return failure
Curr = select state from Frontier
If (Goal?(Curr)) return Curr.
Frontier’ = (Frontier – {Curr}) U Successors(Curr)
return TreeSearch(Frontier’, Successors, Goal?)
无访问标记，可能导致搜索不会终止。
Selection rule（选择方式）
The example shows that the order states are selected from the frontier has a critical eﬀect on the operation of the search:
 Whether or not a solution is found
 The cost of the solution found
 The time and space required by the search
Critical Properties of Search（关键要素）
Completeness（完备性）
will the search always ﬁnd a solution if a solution exists?
Optimality（最优性）
will the search always ﬁnd the least cost solution? (when actions have costs)
Time complexity（时间复杂度）
what is the maximum number of nodes than can be expanded or generated?
Space complexity（空间复杂度）
what is the maximum number of nodes that have to be stored in memory?
无信息搜索（uninformed search）
Selecting vs. Sorting
 A simple uniform method we will exploit
 Order the elements on the frontier.
 Always select the ﬁrst element.
 Any selection rule can be achieved by employing an appropriate ordering of the frontier set.
BreadthFirst
Place the successors of the current state at the end of the frontier.
将当前状态的后继者放置在边界的末尾。
 UniformCost
Breadth First Properties
 Let b be the maximum number of successors of any state.
 Let d be the number of actions in the shortest solution.
Completeness and optimality
 All shorter paths are expanded before any longer path
 There are ﬁnitely many paths of a certain length

Eventually we must examine all paths of length d, and thus ﬁnd the shortest solution
 Time complexity: $1 + b + b2 + … + bd + b(b^d −1) = O(b^{d+1})$
 Space complexity: $b(b^d −1) = O(b^{d+1})$
DepthFirst
 Place the successors of the current state at the front of the frontier
 Therefore always expands the deepest node in the frontier
Applied to the example of Breadth First Search
Depth ﬁrst properties
 Completeness: Inﬁnite state space: No
 Finite state space with inﬁnite paths: No
 Finite state space and prune paths with duplicate states ? Yes
 Optimality: No
Time complexity
 $O(b^m)$ where m is the length of the longest path in the state space (Could explore each branch of search tree)
 Very bad if m is much larger than d
 But if there are many solution paths it can be much faster than breadth ﬁrst (Can by good luck bump into a solution quickly).
Space complexity
 DepthFirst Backtrack Points = unexplored siblings of nodes along current path
 Only explore a single path at a time.
 The Frontier only contains the deepest node on the current path along with the backtrack points.
 O(bm), linear space!
 A signiﬁcant advantage of DFS
Uniformcost(一致代价)
 Keep Frontier ordered by increasing cost of the path
 Always expand the least cost path
 Identical to breadth ﬁrst if each action has the same cost.
Completeness and optimality
 Suppose that each transition has $costs\ge\epsilon >0$
 All cheaper paths are expanded before any more expensive path
 There are ﬁnitely many path costs less that the cost of the optimal solution
 Eventually we must examine the optimal solution
Time and space complexities
 Recall the time and space complexity for breadthﬁrst search is $O(b^{d+1})$ where d is the length of the optimal solution
 $O(bC^∗/\epsilon+1)$ where $C^∗$ is the cost of the optimal solution
Depthlimited search（深度受限搜索）
 Breadthﬁrst has problems with space complexity
 Depthﬁrst can run down a very long or inﬁnite path
 Perform depth ﬁrst search but only to a prespeciﬁed depth limit L
 Now inﬁnite length paths are not a problem But will only ﬁnd a solution if a solution of length ≤ L exists
Depthlimited properties
 Completeness: No
 Optimality: No Time complexity: $O(b^L)$
 Space complexity: $O(bL)$
Iterative deepening search（迭代加深搜索）
 Solve the problems of depthﬁrst and breadthﬁrst by extending depth limited search
 Starting at depth limit L = 0, we iteratively increase the depth limit, performing a depth limited search for each depth limit
 Stop if a solution is found, or if the depth limited search failed without cutting oﬀ any nodes because of the depth limit
 If no nodes were cut oﬀ, the search examined all paths in the state space and found no solution, hence no solution exists.
Completeness and optimality
 Completeness: Yes
 Optimality: Yes if costs are uniform
 If costs are not uniform, we can use a cost bound instead
 Only expand paths of cost less than the cost bound.
 Keep track of the minimum cost unexpanded path in each depth ﬁrst iteration, increase the cost bound to this on the next iteration.
 This can be very expensive. Need as many iterations of the search as there are distinct path costs.
Time and space complexities
 $(d + 1)b^0 + d^b + (d−1)b^2 + … + b^d = O(b^d)$
 Recall the time complexity for breadthﬁrst: $1 + b + b^2 + … + b^d + b(b^d −1) = O(b^{d+1})$
 IDS can be more eﬃcient than breadth ﬁrst search: nodes at limit are not expanded. BFS must expand all nodes until it expand a goal node
 Space complexity: $O(b^d)$
Bidirectional search
 Simultaneously search both forward from the initial state and backward from the goal, and stop when the two searches meet in the middle
 Suppose both directions use breadthﬁrst
 Completeness: Yes
 Optimality: if edges have uniform costs Time and space complexity: $O(b^{d/2})$
Path checking
 Recall paths are stored on the frontier
 If $<n_1,\dots,n_{k}>$ is a path to node $n_k$, and we expand $n_k$ to obtain child $c$, we have $<n_1,\dots,n_{k},c>$ as the path to $c$
 Path checking ensures that the state $c$ is not equal to the state reached by any ancestor of $c$ along this path
 That is, paths are checked in isolation!
Cycle checking / multiple path checking
 Keep track of all states previously expanded during the search
 When we expand nk to obtain child c, ensure that c is not equal to any previously expanded state
 Why can’t we utilize this technique with depthﬁrst search?
 High space complexity, only useful with breadth ﬁrst search
Issue with optimality
 With uniformcost search, we still ﬁnd an optimal solution
 The ﬁrst time uniformcost expands a state it has found the minimal cost path to it.
 This means that the nodes rejected by cycle checking can’t have better paths.
 We will see later that we don’t always have this property when we do heuristic search.
Path / cycle checking
 Path checking: when we expand n to obtain child c, ensures that the state c is not equal to the state reached by any ancestor of c along this path
 Cycle checking: keep track of all states previously expanded during the search; when we expand n to obtain child c, ensure that c is not equal to any previously expanded state
 For uniformcost search, cycle checking preserves optimality
The missionaries and cannibals problem
 N missionaries and N cannibals are at the left bank of a river
 There is a boat that can hold K people
 Find a way to get everyone to the right bank
 So that at any time, at any place (on either bank, or in the boat), #missionaries ≥ #cannibals or #missionaries =0
Formulation of the MC problem
 States (M,C,B) where M – #missionaries, C – #cannibals at the left bank, B = 1 indicates the boat is at the left bank
 Actions (m,c) where m – #missionaries, c – #cannibals on the boat
 Precondition: #missionaries and #cannibals satisfy the constraint
 Effects: $(M,C,1)\to^{(m,c)}(M −m,C −c,0)$ and $(M,C,0)\to^{(m,c)}(M+m,C+c,1)$