如果这篇博客帮助到你，可以请我喝一杯咖啡~

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.

#### Breadth-First

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

将当前状态的后继者放置在边界的末尾。

- Uniform-Cost

##### 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})$

#### 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)$

#### 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,\ldots,n_{k}>$ is a path to node $n_k$, and we expand $n_k$ to obtain child $c$, we have $<n_1,\ldots,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)$