Search is one of the corner stones of artificial intelligence. Search techniques are general problem solving methods, which mean that they do not require any knowledge specific to the problem space. All they need is a set of states, a set of operators, an initial state, and a goal criterion. It is possible to solve a wide variety of problems with these simple components.

Before trying to solve problems, let’s first define what is a problem. Here is an example of a informal search problem. Given a chess board with a Knight piece at position S, we want to move it to position E.

. . . . . . . .

. . . . . . . .

. S . . . . . .

. . . . . . . .

. . . . . E . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

To be able to use search technique, we must write this problem in a formal way. For a problem to be a valid formal search problem, it needs to define 3 things:

  1. The problem’s initial state
  2. A successor method
  3. A goal test
class Problem:
    """
    The abstract class for a formal search problem.
    """

    def __init__(self, initial):
        """
        The constructor specifies the initial state
        """
        self.initialState = initial; self.goal = goal

    def successor(self, state):
        """
        Returns the states that are reachable from a give state.
        """
        abstract

    def isGoalState(self, state):
        """
        Return True if the state is a goal.
        """
        abstract

    def pathCost(self, c, state1, state2):
        """
        Return the cost of a solution path that arrives at state2 from
        state1, assuming cost c to get up to state1.
        """
        return c + 1

The initial state is simply the state in which the search will begin. If the problem is finding a way to move from point A to point B, you would be at point A in the initial state.

By representing the position of the Knight piece by K, the initial state becomes:

. . . . . . . .

. . . . . . . .

. K . . . . . .

. . . . . . . .

. . . . . E . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

The successor function is a function that returns the list of states that are reachable from a given state by applying the operators from the given set of operators. Here are some examples of successor states from the initial state.

Ex 1:

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . K . . . .

. . . . . E . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

Ex2:

K . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . E . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

The successor states are not necessarily a step towards the solution, they are simply a set of the states that are reachable from the given state.

The goal function is a function that given a state, returns true if the state is one in which the goal is reached. In our example, this would happen when the Knight reaches the E position.

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . K . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

There are different types of search techniques. The most basic ones are uninformed search. These search algorithm will explore all the successor states until they find one that is a goal state.

For our first search techniques, lets represent the state set a tree. To find a solution, we simply have to use a breadth-first search (BFS) or depth-first search (DFS) algorithm until a solution is found. As you probably know, the only difference between a BFS and a DFS is the data structure that is used to store the nodes to visit. A BFS uses a FIFO queue, where as a DFS uses a LIFO queue, or a stack. We can therefore define our first 2 search algorithm in the following way:

def breadthFirstTreeSearch(problem):
    return treeSearch(problem, FIFOQueue())

def depthFirstTreeSearch(problem):
    return treeSearch(problem, Stack())

def treeSearch(problem, queue):
    queue.append(Node(problem.initialState))
    while len(queue) > 0:
        node = queue.pop()
        if problem.isGoalState(node.state):
            return node
        queue.extend(node.expand(problem))
    return None

This search algorithm expands the successor nodes until it finds a goal state.

We now have two different search algorithms. Great! How can we evaluate their performance?

There are 4 main criterions that can be used to compare search algorithms:

  1. Completeness: A search algorithm is complete if it always finds a solution if one exists.
  2. Time complexity: In terms of the number of nodes expanded
  3. Space complexity: The maximum number of nodes in memory
  4. Optimality: A search algorithm is optimal if it always finds a least cost solution (if one exists)

How do our algorithms perform? Breadth-first search is a complete algorithm. Since they expand all the possible nodes, one level of the tree at a time, it is guaranteed that it will eventually find a solution (although it might take a while). However, depth-first search is not a complete algorithm since it might get stuck in a recursive infinite loop, which would prevent the algorithm from finding a solution.

The time complexity of the BFS is O(b^d+1), where b is the maximum branching factor and d is the depth of the first solution. This is easily explained as each node could expand to b nodes at each level. The time complexity of the DFS is O(b^m), where m is the depth of the first goal found. It is important to note that the first goal found is not necessarily the one at the lowest depth as it is for BFS.

DFS is therefore non-optimal as it may find a solution that is not the least cost one. However, BFS is optimal.

It is possible to modify these search techniques to avoid repeating states. This can possibly speed up the search and allows DFS to be complete since it becomes impossible to get stuck in recursive loops. To do so, one must simply represent the state set as a graph instead of a tree, and keep track of the states that were already visited, visiting only the new ones.

def graphSearch(problem, queue):
    closed = {}
    queue.append(Node(problem.initialState))
    while len(queue) > 0:
        node = queue.pop()
        if problem.isGoalState(node.state):
            return node
        if node.state not in closed:
            closed[node.state] = True
            queue.extend(node.expand(problem))
    return None

However, this technique comes at a non-negligible cost. When using a graph, all the visited nodes must be kept in memory at all time, this means that even though repeated states can be avoided, the search won’t always be better since it is easy to outgrow the available memory.

BFS and DFS are the two basic uniformed search method. They however are not the only techniques, nor are they the best solutions to every search problems.