人工智能（二）

29 Aug 2019 7775字 26分
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,\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)$