搜索（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 effect 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 find a solution if a solution exists?

Optimality（最优性）

will the search always find 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 first 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 finitely many paths of a certain length

• Eventually we must examine all paths of length d, and thus find 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 first properties

• Completeness: Infinite state space: No
  • Finite state space with infinite 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 first (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 significant advantage of DFS

Uniform-cost(一致代价)

• Keep Frontier ordered by increasing cost of the path
• Always expand the least cost path
• Identical to breadth first 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 finitely 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-first 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-first has problems with space complexity
• Depth-first can run down a very long or infinite path
• Perform depth first search but only to a pre-specified depth limit L
• Now infinite length paths are not a problem But will only find 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-first and breadth-first 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 off any nodes because of the depth limit
• If no nodes were cut off, 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 first 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-first: $1 + b + b^2 + … + b^d + b(b^d −1) = O(b^{d+1})$
• IDS can be more efficient than breadth first 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-first
• 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-first search?
• High space complexity, only useful with breadth first search

Issue with optimality

• With uniform-cost search, we still find an optimal solution
• The first 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)$