---
# System prepended metadata

title: 'Ch03: Solving Problems by Searching'
tags: [人工智慧]

---

<!-- markdownlint-disable MD013 MD024 -->

<style>
  .r {
    color: rgb(224, 60, 46);
    font-weight: bold;
  }
  
  .b {
    color: rgb(45, 123, 238);
    font-weight: bold;
  }
  
  .g {
    color: rgb(33, 147, 66);
    font-weight: bold;
  }
  
  .y {
    color: rgb(247, 191, 25);
    font-weight: bold;
  }
</style>

# Solving Problems by Searching

## Problem-solving Agents

- A kind of <font class="r">goal-based</font> agent
- Use **atomic** representations with no internal structure visible to the problem solving algorithms
- First Step: <font class="b">goal formulation</font>
  - Based on current situation and the agent's performance measure
  - A goal is considered as a set of world states
- By given a goal, <font class="b">the problem formulation</font> is
  - The process of deciding what actions and states to consider

> Assuming the environment is observable, discrete known, and deterministic, then *the solution to any problem is a fixed sequence of actions*

- The process of looking for a sequence of actions that reaches the goal is called <font class="g">search</font>
- Carry out the solution is called the <font class="g">execution</font> phase
- The design of an agent can be considered as a simple "**formulate**, **search**, **execute**"

### Example: Romania

- On holiday in Romania; currently in Arad
- Flight leaves tomorrow from Bucharest
- Formulate goal:
  - Be in Bucharest
- Formulate prolem
  - States: various cities
  - Actions: drive between cities
- Find solution:
  - Sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest
  ![](https://hackmd.io/_uploads/H1v5Oeae6.png =600x)

### Problem types

- **Deterministic, full observable** $\rightarrow$ single-state problem
  - Agent knows exactly which state it will be in; solution is a sequence
- **Non-observable** $\rightarrow$ conformant (一致的) problem 
  - Agent may have no idea where it is; solution (if any) is a sequence
- **Nondeterministic and/or partially observable** $\rightarrow$ contingency (意外事件) problem 
  - Percepts provide new information about current state
  - Solution is a contingent plan or a policy
  - Often interleave (交錯) search, execution
- **Unknown state space** $\rightarrow$ exploratotion problem ("online")

### Well-defined Problems and Solutions

A search problem can be defined formally as follows:

- A set of possible <font class="b">states</font> that the environment can be in. (Called <font class="b">state space</font>)
- <font class="lb">Initial state</font> that the agent starts in, such as *Arad*
- A set of one or more <font class="b">goal states</font>
- The <font class="g">actions</font> available to the agent
  - Given a particular state $s, Action(s)$ returns the finite set of actions that can be executed in $s$.
  - Ex. $Action(Arad) = \{ToSibiu, ToTimisoara, ToZerind\}$
- A <font class="y">transition model</font>, which describes what each action does. $Result(s, a)$ returns the state that results from doing action a in state s.
  - e.g. $Result(Arad, ToZerind) = Zerind$
- An <font class="r">action cost function</font>, denoted by Action-Cost(`s`, `a`, `s'`) that gives the numeric cost of applying action `a` in state `s` to reach state `s'`.
  - A problem solving agent should use a cost function that reflects its own performance measure
  - e.g. for route-finding agents, the cost of an action might be the length in miles, or it might be the time it takes to complete the action.

## Formulating Problems

- Abstraction 抽象
  - The  process of removing detail from a representation
- The abstraction is valid if we can expand any abstract solution into a solution in the more detailed world
- The abstraction is useful if carrying out each of the actions in the solutions is easier than the original problem

## Example Problems

- Standardized problems and real-world problems
  - Standardized problem: intended to illustrate or exercise various problem-solving methods (旨在說明或練習各種解決問題的方法)
  - Real-world problem: people actually care about their solutions

## Standardized Problems

### Vaccum world

- **States**: 2 $\times$ 2^2^ = 8 possible states
- **Initial state**: any state can be designed as the initial state
- **Actions**: *Left, Right, Suck, NoOP*
- **Transition model**: see the figure below
- **Goal test**: checks whether all squares are clean
- **Path cost**: each step costs 1, so the path cost is the number of steps in the path
  ![image.png](https://hackmd.io/_uploads/Byz-lv97T.png =600x)

### 8-puzzle

- **States**: integer locations of tiles
- **Initial state**: any state can be designed as the initial state
- **Actions**: move blank *left, right, up, down*
- **Transition model**: given a state and action, this returns the resulting state
- **Goal test**: = goal state
- **Path cost**: 1 per move
  ![image.png](https://hackmd.io/_uploads/HJMwbwcXT.png =300x)

### 8-queens

- Two kinds of formulation: *incremental* and *complete-state* formulation
  - Incremental formulation
    - **States**: any arrangement of 0 to 8 queens on the board 
    - **Initial state**: no queens on the board 
    - **Actions**: add a queen to any empty square
    - **Transition model**: returns the board with a queen added to the specified square
    - **Goal test**: 8 queens are on the board, none attacked
    - **Path cost**: don't care
  - A better formulation that reduces # of states (from 1.8 * 10^14^ to 2057)
    - **States**: all possible arrangements of n queens (0 $\le$ n $\le$ 8), one per column in leftmost n columns, with no queen attacking another
    - **Actions**: add a queen to any square in the leftmost empty column such that it is not attacked by any other queen

  ![image.png](https://hackmd.io/_uploads/r1yhWPqXT.png =200x)

## Real-world Problems

### Route-finding Problem

- Airline travel problem
  - **States**: each state includes a location, current time, other extra information about historical aspects, such as previous segments of flight, fare bases, status as domestic or international
  - **Initial state**: specified by user's query
  - **Actions**: take any flight from current location, in any seat class, leaving after current time, leaving enough time for within-airport transfer if needed
  - **Transition model**: flight's destination as the current location and arrival time as the current time
  - **Goal test**: are we at the final destination specified by the user
  - **Path cost**: depends on monetary cost, waiting time, flight time, customs and immigration procedures, seat quality, and so on

### Other Real-world Problems

- Touring problems 
  - Closely related to route-finding problems
  - State space is quite different. Each state must include not only the current location but also the set of cities the agent has visited
  - Goal state, for example, check the agent is in Bucharest and all 20 cities have been visited
- Traveling Saleperson Problem (TSP)
  - a touring problem in which each city must be visited exactly once
  - The aim is to find the *shortest* tour
  - NP-hard problem
- VLSI layout
  - Positioning, millions of components and connections on a chip to minimize area, circuit delays, stray capacitances, and maximize manufacturing yield
- Robot navigation
  - A generalization of the routing-finding problem
  - A robot can move in a continuous space with an infinte set of possible actions and states
- Automatic assembly sequencing
  - Find an order in which to assemble the parts of some object 

## Searching for Solutions

- Search Tree
  - Root as the initial state
  - Branches as actions
  - Nodes correspond to states in the state space
- Search by expanding the current state
  - Generate a new set of states by applying each legal action to the current state
  ![image.png](https://hackmd.io/_uploads/H1RgPw9QT.png =500x)

### Informal Description of Tree-search and Graph Search:

![](https://hackmd.io/_uploads/S1vsfyaea.png)

> Frontier: The set of all leaf nodes available for expansion at any given point is called the frontier

### Loopy Path and Redundant Path

<!-- Tree 怎麼 loopy? -->
- <font class="b">Loopy path</font>: A <font class="b">repeated state</font> in the search tree.
  - Ex. A -> B -> A
  - Can be easily avoid, since the **path costs are additive** and step costs are **nonnegative**.
    - A loopy path to any given state is never better than the same path with the loop removed.
- <font class="g">Redundant Path</font>: There is more than one way to get from one state to another.
  - **Loopy paths are special case of redundant path**.
  - Ex. Arad->Sibiu (140 km) vs Arad-Zerind-Oradea-Sibiu (297 km)
    - The second path is redundant
  - In other cases, redundant paths are **unavoidable**.
  - To avoid exploring redundant paths is to **remember** where one has been. (See graph search in the previous slide)
  - 要列出所有可能的答案時要保留 redundant path.

### Node and State

- A node is a **data structure** constituting part of a search tree including parent, children, depth, path cost g(x).
- A state is a (representation of) a **physical configuration**.
- States do not have parents, children, depth, or path cost!

### Concepts used to implement search algorithms

- **Queue**: FIFO (First In First Out)
- **Stack**: LIFO (Last In First Out)
- **Priority queue**: pops the element of the queue with **highest priority**.
- **Hash table**: allow efficient checking for repeated states.

### Measuring Problem-solving Performance

- A strategy is defined by picking the <font class="r">order of node expansion</font>
- Strategies are evaluated along the following dimensions:
  - **Completeness**
    - Does it always find a solution if one **exits**?
  - **Optimality**
    - Does the strategy find the **least-cost (optimal) solution**?
  - **Time Complexity**
    - Number of nodes **generated/expanded**.
  - **Space Complexity**
    - Maximum number of nodes **in memory**.
- Time and space complexity are measured in terms of
  - $b$ – **maximum branching factor** of the search tree
  - $d$ – **depth of the least-cost solution**
  - $m$ – **maximum depth** of the state space (may be $\infty$)

## Uninformed Search Strategies 不知情的搜索策略

Uninformed strategies use only the information available in the problem definition. Also called **blind search**.

- Breadth-first search
- Uniform-cost search
- Depth-first search
- Depth-limited search
- Iterative deepening depth-first search
- Bidirectional search

### Breadth-first search on a graph

![](https://hackmd.io/_uploads/S125OJ6e6.png)

- Expand shallowest unexpanded node
- Implementation
  - fringe is a FIFO queue, i.e., new successors go at end
    ![image.png](https://hackmd.io/_uploads/r15St_qXa.png =300x)


#### Properties of Breadth-first Search

- Complete
  - Yes, if $b$ is finite.
- Time
  - $1 + b + b^2 + b^3 + \cdots + b^d = O(b^d)$
- Space
  - $O(b^d)$ (keeps every node in memory)
- Optimal
  - Yes (if **cost = 1 per step**); not optimal in general.
- **Space** is the big problem; can easily generate nodes at 100MB/s, so 24hrs = 8640GB

### Uniform-cost Search

![](https://hackmd.io/_uploads/HyRP-eplT.png)

- Expand least-cost unexpanded node, denoted by lowest path cost $g(n)$
- Two significant difference from breadth-first search
  - Goal test is applied to a node when it is selected for expansion (rather than it is first generated)
  - A test is added in case a better path is found to a node currently on the frontier
- Implementation:
  - fringe = queue ordered by path cost, lowest first
- Equivalent to breadth-first if step costs all equal
- Complete
  - Yes, if step cost >= $\varepsilon$
- Time
  - \# of nodes with g <= cost of optimal solution, $O(b^{1 + [C^*/\varepsilon]})$
  - Where $C^*$ is the cost of the optimal solution
- Space
  - \# of nodes with g <= cost of optimal solution, $O(b^{1 + [C^*/\varepsilon]})$
- Optimal
  - Yes, nodes expanded in increasing order of $g(n)$

#### Why not goal-test when generating child nodes

![](https://hackmd.io/_uploads/rJIo-gTgT.png)

- Goal: From Sibiu to Bucharest
- Successors of Sibiu: Rimnicu Vilcea and Fagaras (cost 80 and 99)
- Least-cost node will be Rimnicu Vilcea, and is expanded next, adding Pitesti with cost 80+97=177.
- Least-cost node will be Fagaras, and is expanded, adding Bucharest with cost 99+211 =310.
- Now a goal node has been generated, but uniform-cost search keeps going, choosing Pitesti for expansion and adding a second path to Bucharest with cost 80 + 97 + 101 = 278.
- Now the algorithm checks to see **if this new path is better than the old one**; it is, so the old one is discarded. Bucharest, now with cost 278 is selected for expansion and the solution is returned.

### Depth-first Search

- Complete
  - No, fails in infinite-depth spaces, spaces with loops
    - Modify to avoid repeated states along path -> complete in finite spaces
- Time
  - $O(b^m)$: terrible if $m$ is much larger than $d$
  - But if solutions are **dense**, may be much faster than breadth-first
- Space
  - $O(bm)$, i.e., linear space!
- Optimal
  - No

### Depth-limited Search

- = depth-first search with depth limit $l$,
- i.e., nodes at depth $l$ have no successors
- Recursive implementation

![](https://hackmd.io/_uploads/r1Y8Qe6e6.png)

### Iterative Deepening Search

![](https://hackmd.io/_uploads/HJIc7l6xT.png)

- $l$ = 0
  ![](https://hackmd.io/_uploads/HksV4g6xT.png =400x)
- $l$ = 1
  ![](https://hackmd.io/_uploads/Bk28VxagT.png)
- $l$ = 2
  ![](https://hackmd.io/_uploads/ryTvVgplT.png)
- $l$ = 3
  ![](https://hackmd.io/_uploads/H1xYEgaep.png)

#### Properties of Iterative Deepening Search

- Complete
  - Yes
- Time
  - $db^1 + (d - 1)b^2 + \cdots + b^d = O(b^d)$
- Space
  - $O(b^d)$
<!-- TODO -->

### Bidirectional Search

- Run two simultaneous searches and hope that the two searches meet in the middle
  - One **forward** from the initial state, the other **backward** from the goal.
- Motivated by $b^{d/2} + b^{d/2}$ is much less then $b^d$
- Goal test is replaced by checking whether the frontiers of the two searches intersect
  - However, this **may not be the optimal solution**.
- Bidirectional search requires a method for **computing predecessors**.
  - 8-puzzle and find a route in Romania, backward search is very much like the forward search
  - 8-queen, “no queen attacks another queen”
    - it is hard to find such a function for backward search

### Comparison of Uninformed Search Strategies

![](https://hackmd.io/_uploads/ryS0Be6l6.png)

- $b$ is the branching factor
- $d$ is the depth of the shallowest solution
- $m$ is the maximum depth of the search tree
- $l$ is the depth limit

## Informed (Heuristic) Search Strategies

- Best-first search
  - Instance of the general tree-search or graph-search algorithm
  - A node is selected for expansion based on an **evaluation function**, $f(n)$
    - Node with the lowest evaluation is expanded first.
    - Implementation is identical to that for uniform-cost search, except for the use of $f$ instead of $g$ to order the priority queue.
  - Special cases:
    - Greedy search
    - A* search

### Heuristic Functions

- Most best-first algorithms include as a component of $f$ a heuristic function, denoted $h(n)$:
  - $h(n)$ = estimated cost of the cheapest path from the state at node $n$ to a goal state.
    - $h(n)$ takes a node as input, $g(n)$ depends only on the state at that node.

### Greedy Best-first Search

- Greedy search expands the node that appears to be closest to goal
- It evaluates nodes by using just the heuristic function, i.e. $f(n) = h(n)$
- In Romania example, **straight-line distance** heuristic is used, as $h_{SLD}$.

![](https://hackmd.io/_uploads/B1ZWOl6e6.png)

Value of $h_{SLD}$:

![](https://hackmd.io/_uploads/H13f_eTgp.png)

#### Properties of Greedy Search

- Complete
  - No, can get stuck in loops
    - Ex. From Iasi to Fagaras
    - Iasi -> Neamt -> Iasi -> Neamt ->
  - Complete in finite space with repeated-state checking
- Time
  - $O(b^m)$, but a good heuristic can give b dramatic improvement
- Space
  - O(b^m) keeps all nodes in memory
- Optimal
  - No

### A* Search

- Idea: avoid expanding paths that are **already expensive**
- Evaluation function: $f(n) = g(n) + h(n)$
  - $g(n)$: cost so far to reach the node $n$
  - $h(n)$: estimated cost to goal from $n$
  - $f(n)$ = estimated total cost of path through $n$ to goal
- A* search uses an admissible heuristic
  - i.e., $h(n) \le h^*(n)$ where $h^*(n)$ is the true cost from $n$.
  - (Also require $h(n) \ge 0$, so $h(G) = 0$ for any goal $G$.)
    - E.g., $h_{SLD}(n)$ never overestimates the actual road distance
- Provided that the heuristic function satisfied certain **conditions**, A* search is both complete and optimal

![](https://hackmd.io/_uploads/ryIfql6g6.png)
![](https://hackmd.io/_uploads/BkI79eTep.png)

---

- Conditions for optimality: **Admissibility** and **consistency**
- $h(n)$ be an admissible heuristic
  - Admissible heuristic is one that **never overestimates** the cost to reach the goal.
  - e.g. the straight-line distance in Romania example
- Consistency or monotonicity
  - A $h(n)$ is consistent if, for every node $n$ and every successor $n'$ of $n$ generated by any action $a$, the estimated cost of reaching the goal from $n$ is no greater than the step cost of getting to $n'$ plus the estimated cost of reaching the goal from $n'$
  - $h(n) <= c(n, a, n') + h(n')$
  - A form of the general **triangle inequality**

![](https://hackmd.io/_uploads/H1QOslaea.png)

#### Optimality of A*

- Suppose some suboptimal goal $G_2$ has been generated and is in the queue.
- Let $n$ be an unexpanded node on a shortest path to an optimal goal $G_1$.
- $$f(G2) = g(G2) since h(G2) = 0
  $$
<!-- TODO -->

#### Properties of A*

- Complete
  - Yes, unless there are infinitely many nodes with f <= f(G)
- Time
  - Exponential in [relative error in h * length of soln.]
- Space
  - Keeps all nodes in memory
- Optimal
  - Yes, cannot expand $f_{i+1}$ until $f_i$ is finished

#### Proof of Lemma: Consistency

<!-- TODO -->

#### A* Search

- Main drawback
  - It keeps all generated nodes in memory
- Iterative-deepening A\* (IDA*) algorithm
  - The simplest way to reduce memory requirements for A*
  - The cutoff is the f-cost (g+h)
  - At each iteration, the cutoff value is the smallest f-cost of any node that exceeded the cutoff on the previous iteration

### Memory-bounded Heuristic Search

- RBFS (Recursive best-first search)
  - A simple recursive algorithm
  - Attempts to mimic the operation of standard best-first search
  - Using only linear space

#### RBFS

![](https://hackmd.io/_uploads/HyAkg-Tl6.png)

- It uses the $f\_limit$ variable to keep track of the f-value of the best alternative path available from an ancestor of the current node
- If the current node exceeds this limit, the recursion unwinds back to the alternative path
- Back-up value
  - The best f-value of its children
  - Decide whether it’s worth reexpanding the subtree at some later time

![](https://hackmd.io/_uploads/HJTsgZpgT.png)
![](https://hackmd.io/_uploads/SJT2l-pep.png)

- More efficient than IDA*
- Excessive node re-generation
- Each mind change corresponds to an iteration of IDA* and could require many reexpansions of forgotten nodes to recreate the best path and extend it one more node.

---

- It is optimal
  - If the heuristic function is admissible
- Space complexity
  - It is linear in the depth of the deepest optimal solution
- Time complexity
  - Depends both on the accuracy of the heuristic function and on how often the best path changes as nodes are expanded.

---

- MA\* (Memory-bounded A*)
- SMA\* (Simplified MA*)
  - It expands the best leaf until memory is full
  - Always drops the worst leaf node – the one with the highest f-value
  - Backs up the value of the forgotten node to its parent

### Heuristic Functions

- The 8-puzzle was one of the earliest heuristic search problems.
- The average solution cost is about 22 steps
- The branching factor is about 3

![](https://hackmd.io/_uploads/BySjz-6xT.png)

#### Two Commonly Used Heuristics

- h1 = the number of misplace tiles
  - An admissible heuristic
  - Any tile that is out of place must be moved at least once
- h2 = the sum of the distances of the tiles from their goal positions. (i.e., total Manhattan distance)
  - An admissible heuristic
  - All any move can do is move one tile one step closer to the goal
  - Tiles 1 to 8 in the start state give a **Manhattan distance**
    - h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18

#### Dominance

- If $h_2(n) \ge h_1(n)$ for all $n$ (both admissible)
- Then $h_2$ dominates $h_1$ and is better for search
- Typical search costs
  - d = 14 IDS = 3,473,941 nodes
    - A*($h_1$) = 539 nodes
    - A*($h_2$) = 113 nodes
  - d = 24 IDS ~= 54,000,000,000 nodes
    - A*($h_1$) = 39,135 nodes
    - A*($h_2$) = 1,641 nodes
- Given any admissible heuristics $h_a, h_b$
  - $h(n) = max(h_a(n), h_b(n))$
  - Is also admissible and dominates $h_a, h_b$
- Comparison of the search costs and effective branching factors for the iterative deepening search and A* algorithms with $h_1, h_2$

![](https://hackmd.io/_uploads/rkcnvW6lT.png)

#### The effect of heuristic accuracy on performance

#### Relaxed Problems

- Admissible heuristics can be derived from the exact solution cost of a relaxed version of the problem
- If the rules of the 8-puzzle are relaxed so that a tile can move **anywhere**, then $h_1(n)$ gives the shortest solution
- If the rules are relaxed so that a tile can move to **any adjacent square**, then $h_2(n)$ gives the shortest solution
- Key point: the optimal solution cost of a relaxed problem is no greater than the optimal solution cost of the real problem

---

- Well-known example: travelling salesperson problem (TSP)
- Find the shortest tour visiting all cities exactly once
- Minimum spanning tree can be computed in $O(n^2)$, and is a lower bound on the shortest (open) tour

[後面的演算法相關筆記](https://fu-sheng-wang.blogspot.com/search/label/AI?updated-max=2017-02-12T01:12:00-08:00&max-results=20&start=33&by-date=false)
