Graph Search

Graphs are extremely useful structures for keeping track of the effects of several sequences of rules.

Graph search follows the rule, "do not expand the same node more than once"

Graph search is optimal only when the forward cost between two successive node \(A\) and \(B\) (given by \(h(A) - h(B)\)) is less than or equal to the backward cost between those two nodes (given by \(g(A \rightarrow B)\)). This properly of graph search heuristic is called consistency.

\[h(A) - h(B) \leq g(A \rightarrow B)\]

Example: Using Graph Search to Find Paths in a Graph

In the following example, we use graph search to find paths from node \(S\) to node \(G\).

@TODO: Insert graph search example

Classification of Search Algorithms

The common graph search algorithms can be classified as follows:

  • Uninformed/Blind Search

    • Depth-First Search

    • Breadth-First Search

    • Uniform Cost Search

  • Informed Search

    • Greedy search

    • General Graph Search

    • A* Search

Uninformed Search

The algorithms under uninformed search have no additional information about the goal state other than the information provided in the problem definition.

The plans to reach the goal state from the start state differ only by the order and/or length of actions.

It is also known as blind search as these algorithms can only generate successors and differentiate between the goal and non-goal states.

These search algorithms play a crucial role in the field of AI by providing basic search strategies for exploring problem spaces where no additional knowledge is available beyond the problem definition.

These algorithms do not have a heuristic function to guide the search towards the goal; instead, they explore the search space systematically to find a solution.

Examples: Breadth-First Search (BFS), Depth-First Search (DFS), Uniform Cost Search (UCS)

Breadth-First Search (BFS)

It is an algorithm to traverse or a search tree or graph data structure.

It starts at any arbitrary node of a graph and explores all of the neighbouring nodes of the current node before moving on to the next node at the next depth/level.

It uses a queue for its implementation.

Example

@TODO: add BFS example

Time Complexity of BFS

  • \(O(V + E) \rightarrow\) if it explores all the vertices (\(V\)) and edges (\(E\)) of the graph

  • \(O(m^d) \rightarrow\) where

    • \(d\) is the depth of the shallowest solution

    • \(m\) is the maximum number of nodes at level \(d\)

Depth-First Search (DFS)

The algorithm starts at any arbitrary node and explores as far as possible along each branch before backtracking.

It is implemented using a stack.

Example

@TODO: add DFS example

Time Complexity of DFS

  • \(O(V + E) \rightarrow\) if it explores all the vertices (\(V\)) and edges (\(E\)) of the graph

  • \(O(m^d)\), where

    • \(d\) is the depth of the shallowest solution

    • \(m\) is the maximum number of nodes at level \(d\)

Uniform Cost Search (UCS)

In this algorithm, a cost is associated with each of the edges of the graph.

The goal is to find the path where the cumulative sum of costs is least.

The algorithm checks all the available routes until the least cost route is found. When a lower cost route is found, the algorithm discards the other paths.

Note
 Uniform cost search does not work for negative costs!

Example

In the following example, the goal is to apply UCS to find the least cost path from node \(S\) to node \(G\).

@TODO: add UCS example

Thus, the UCS path from \(S\) to \(G\) is \(S \rightarrow A \rightarrow B \rightarrow G\) with a cost of 5.

Time Complexity of UCS

  • \(O(m^\frac{C}{\epsilon})\), where:

    • \(C\) is the cost of the optimal solution

    • \(\epsilon\) is the arc cost

    • \(m\) is the number of nodes

← Previous: Backtracking | ↑ Up: Advanced Artificial Intelligence | Next: Commutative Production Systems →