Search

03 Jun 2017 | algorithms

Many problems, such as 8-puzzles, n-queens, or solving a rubic’s cube can be formulated as search problems.

Formulating Search Problems

All search problems should have these parts:

  • initial state - This is the initial state that is given to the search problem
  • goal state - There may be more than one goal state. It is the state at which the search problem is solved.
  • transition model/successor function - Describes how to move from one state to another given an action.
  • action - Each action changes the current state. Each action may also have an associated cost with it.

The goal is to find a sequence of actions to move from the initial state to the goal state and minimize the cost of your actions

Solving Search Problems

The idea behind solving all search problems is the same.

frontier = {I}
loop:
    if frontier is empty:
        return FALSE
    node = some node in the frontier
    if goal == node:
        return current state
    generate the node's children
    add the node's children to the frontier and "explored set"

A search strategy is said to be complete if it finds a solution if one exsists.

A search strategy is said to be optimal if the solution it finds is the one with the least cost.

The seperation property states that if the frontier seperates all explored states from all non-explored states that the search strategy is optimal

The branching factor describes how many actions you can take in a given state. If this number is not constant, the average branching factor or the max branching factor is usually used.

The idea of BFS is to search the closest nodes first. To implement it, we use a queue (FIFO) to represent the frontier. However the problem with BFS is that it is exponential in time and space. Exponential time is not as large of a problem as exponential space, as we quickly run out of memory. We can see that in order to expand all the nodes down to our solution depth, \(d\), we would have to expand \(b^d\) nodes, where \(b\) is the branching factor.

Let \(N(b, d)\) be the number of nodes generated for a problem with branching factor \(b\) and solution at depth \(d\).

\[N(b, d) = b^d + b^{d-1} + \ldots + 1\] \[b \times N(b, d) = b^{d+1} + b^{d-1} + \ldots + b\] \[b \times N(b, d) - N(b,d)= b^{d+1} - 1\] \[N(b, d) = \frac{b^{d+1} + 1}{b-1} \approx \frac{b^{d+1}}{b-1} \approx b^d \times \frac{b}{b-1}\]

DFS

In DFS, we try to go as deep as possible first. To implement this, we use a stack (FILO) to represent the frontier. We can see that our “explored set” needs only to be \(bd\) rather than \(b^d\). However, DFS is not optimal - our solution may not be the best one.

For both BFS and DFS, the number of nodes generated is

\[N(b, d) \approx b^d \times \frac{b}{b-1}\]

The idea of Iterative Deepening Search is to do Depth Limited Serach (DFS with a depth limit), gradually increasing the depth each time. This maintains the ideal properties of \(bd\) space. While it may seem wasteful to regenerate each node, it actually only requires twice the work, maintaining an \(b^d\) runtime as well as optimality.

Let \(N(b, d)\) be the number of nodes generated by DFS for a problem with branching factor \(b\) and solution at depth \(d\). We know from above that

\[N(b, d) \approx b^d(\frac{b}{b-1})\]

Let \(N'(b, d)\) be the number of nodes generated by Iterative Deepening for a problem with branching factor \(b\) and solution at depth \(d\). Since iterative deepening runs for each depth from \(1\) until \(d\), we can express the number of nodes generated as a sum.

\[N'(b, d) = \sum_{i = 1}^{d}{b^i(\frac{b}{b-1})}\] \[N'(b, d) = (\frac{b}{b-1})\sum_{i = 1}^{d}{b^i}\]

Now we can see that \(\sum_{i = 1}^{d}{b^i}\) is the exact same equation we had for DFS before, so we et

\[N'(b, d) = (\frac{b}{b-1})^2b^d\]

\(\frac{b}{b-1}\) is the difference between running DFS and ID. Since \(b > 1\), at most it is a 2x more work. We can see that even for relatively small \(b\) (\(b=10\)) that it is just 1.1x more work.

Comparison

  BFS DFS ID
Time \(O(b^d)\) \(O(b^d)\) \(O(b^d)\)
Space \(O(b^d)\) \(O(bd)\) \(O(bd)\)
Optimal Y N Y
Complete Y Y Y

Solving Search Problems with Cost

Nodes are expanded in increasing order of cost. Therefore, whatever we expand will have a larger cost.

An estimate of the cost at the current state is needed \(h(x)\), or a heurestic function. We can then use a greedy search - try to take the biggest bite at the current distance. However, while this search strategy is complete it is not optimal.

Determining a Heurestic

Our heurestic is consistent if \(h(n) \leq c(n, a, n') + h(n')\) where \(h(n)\) is the cost for a node \(n\), \(c(n, a, n')\) is the cost to the goal state \(a\) through \(n'\). This means that the estimate is always less than or equal to the estimated distance from any neighboring vertex to the goal, plus the cost of reaching that neighbor.

Our heurestic is admissable if it never overpredicts the distance to the goal state. This means that \(h(n) \leq h^*(n)\), where \(h^*(n)\) is the actual cost to reach the goal state.

One easy way to generate heurestics is to relax the constraints of a problem.

We can improve upon best first search by taking into account the cost used to get to a node as well as the predicted cost. We can model this with the function

\[f(n) = g(n) + h(n)\]

\(g(n)\) = the cost to get to the current node

\(h(n)\) = the predicted, heurestic cost to get to the final solution

Note that if \(h(n) = 0\), then A* is just Uniform Cost Search

A* Search is optimal if our heurestic is both consistent and admissable.

For any node \(n\), along the path from the initial state \(I\) to a goal state \(G\) with actual cost \(c^*\), we know that \(f(n) = g(n) + h(n) \leq c*\), since our heurestic is both consistent and admissable.

Suppose there is some other goal state, \(G'\), that has less cost than \(c*\). \(f(G') = g(G') + h(G') = g(G') \leq c*\). However, in this case, we would expand \(G'\) before \(n\), so we would reach the optimal solution.

Local Search Strategies

Written on June 3, 2017