Uninformed Search Algorithms

Introduction to search algorithms - a fundamental for understanding artificial intelligence.

Maximilian Weichart


September 23, 2023

1 Introduction

Search is a very broad term in the field of artificial intelligence. What seems so intuitive to us as humans, such as finding an efficient route from city A to city B when looking at a map, is not so straightforward when we want a computer to do the same thing.

At very first glance, a simple thing such as search may seem irrelevant when we want to create artificial intelligence. It may seem boring, over-simplistic or useless to solve this problem, but it turns out that most of what’s considered artificial intelligence today is per definition just a search problem and in fact, it is solved by one of these simple search algorithms - gradient descent - which is just as simple as any of its relatives, be it from the informed or uninformed, global or local category.


This article is based on the chapter about uninformed search in “Artificial Intelligence: A Modern Approach, 4th Edition” by Stuart Russell and Peter Norvig.

1.1 Informed vs Uninformed

The first important distinction to make for understanding search is to differentiate between informed and uninformed search. You can think of the former, like searching for your phone in your living room when you have no idea where you left it. The latter is like searching for it while giving it a call, so you hear the general direction where it might be.

There are different kinds of uninformed search algorithms, but the ones we’ll be focusing on in this article are Depth-First, Breadth-First and Uniform-Cost search. Each section will briefly introduce the concept and follow up with a concise Python implementation that you can copy and play around with.

1.2 Setup

We’ll start by defining an example scenario for our search. A common search problem is finding a path to a goal state, for example, you may wonder how to find the quickest way from your home to work.

Graph initialization
nodes = ['A', 'B', 'C', 'D', 'E', 'F']
edges = [
    ('A', 'B', 2),
    ('A', 'C', 10),
    ('B', 'C', 3),
    ('B', 'D', 4),
    ('C', 'E', 2),
    ('D', 'F', 3),
    ('E', 'F', 2),
    ('E', 'B', 2)

import networkx as nx
import matplotlib.pyplot as plt

# Create an empty graph
graph = nx.Graph()

# Add nodes to the graph

# Add edges with associated costs
for edge in edges:
    graph.add_edge(edge[0], edge[1], cost=edge[2])
Visualization functions
import colorsys

# Generates a color palette from fully-saturated to unsaturated with the
# specified amount of steps.
def generate_color_gradient(num_steps):
    hue = 0.4  # Neon Green
    lightness = 0.5
    saturation_step = 1.0 / num_steps

    colors = []
    for i in range(num_steps):
        # Calculate the current saturation
        saturation = (i+1) * saturation_step

        # Convert HSL to RGB
        rgb_color = colorsys.hls_to_rgb(hue, lightness, saturation)

        # Convert RGB values to 8-bit integers
        rgb_color = tuple(int(value * 255) for value in rgb_color)


    colors.reverse() # Saturated -> Unsaturated
    node_colors = [(r/255, g/255, b/255) for r, g, b in colors] # Conversion for networkx

    return node_colors

# Visualizes a graph and tints all visited nodes with a gradient (earliest to latest)
def visualize(graph, visited_nodes=[], start_node="A", end_node="F"):
    pos = nx.spring_layout(graph, seed=42)  # or nx.circular_layout(graph)

    labels = {edge[:2]: edge[2] for edge in edges}  # Dictionary for edge labels
    color_array = generate_color_gradient(len(visited_nodes)) if visited_nodes else []

    node_colors = []
    for node in graph.nodes():
      if node in visited_nodes:
        # Tint visited nodes from earliest to latest visit
      elif node == start_node or node == end_node:
        # If there are no visited nodes, mark start and goal with main colors
        # Default color for nodes

    nx.draw(graph, pos, with_labels=True, node_size=500, node_color=node_colors, font_size=10, font_color='black')
    nx.draw_networkx_edge_labels(graph, pos, edge_labels=labels)


def evaluate(algorithm, graph):
  visited = algorithm(graph)
  visualize(graph, visited)

Figure 1: Graph of locations A-F, with green locations (A,F) being the start- and goal-states. The edges represent the cost of transitioning from one state to another.

5 Summary

Search is a fundamental problem in artificial intelligence, and it can be divided into many categories. In this article, we explored uninformed search, which is searching without having any clue of the general direction of the goal. BFS, DFS and UCS are three basic algorithms to tackle this problem and they each have their strengths and weaknesses. Depending on the state space one may perform better than the other, but each one has their drawbacks when being measured in space & time-complexity, completeness and cost-optimality. We explored each algorithm by getting an intuition of how it works and by looking at a simple implementation to solve our example problem.