# 人工智能（二）

## 搜索（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?

#### 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.

Place the successors of the current state at the end of the frontier.

• Uniform-Cost
• 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})$

#### Depth-First

• 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
• Depth-First 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

#### Uniform-cost(一致代价)

• 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

#### Depth-limited 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 pre-speciﬁ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
##### Depth-limited 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)$
• 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 uniform-cost search, we still ﬁnd an optimal solution
• The ﬁrst time uniform-cost 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 uniform-cost 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)$