What Is Uninformed Search?

Uninformed search algorithms explore a problem's state space without using additional information about how close a state is to the goal.

They rely on the initial state, available actions, transition model, goal test, and, where relevant, path costs.

Three important uninformed search algorithms are Breadth-First Search, Depth-First Search, and Uniform-Cost Search.

1. Breadth-First Search (BFS)

Breadth-First Search explores states level by level. It examines all nodes at one depth before moving to the next depth.

BFS typically uses a queue, which follows the First In, First Out (FIFO) principle.

Consider the following graph:

A

/ \

B   C

/ \   \

D   E   F

Starting at A, BFS visits the nodes in this order:

A → B → C → D → E → F

BFS is useful when all actions have equal cost and the objective is to find the solution with the fewest steps.

Python Implementation

from collections import deque
graph = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": ["F"],
"D": [],
"E": [],
"F": []
}
def bfs(graph, start):
queue = deque([start])
visited = {start}
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
bfs(graph, "A")

Output:

A B C D E F

The visited set prevents the algorithm from repeatedly exploring the same node.

2. Depth-First Search (DFS)

Depth-First Search explores one branch as deeply as possible before returning to explore other branches.

DFS can be implemented using a stack or recursion.

Using the same graph, one possible traversal order is:

A → B → D → E → C → F

The exact order depends on the order in which neighbors are processed.

Python Implementation

def dfs(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
print(node, end=" ")

Reverse the list to preserve left-to-right traversal

for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
dfs(graph, "A")

Output:

A B D E C F

DFS can use less memory than BFS in some search trees because it does not need to store every node at the current breadth. However, its memory usage depends on the graph and implementation.

3. Uniform-Cost Search (UCS)

Uniform-Cost Search expands the state with the lowest accumulated path cost.

Unlike BFS, UCS supports paths whose individual actions have different costs.

Consider these routes:

• A → B costs 2, and B → D costs 8.
• A → C costs 4, and C → D costs 3.

The total costs are:

• A → B → D = 10
• A → C → D = 7

UCS finds the lower-cost route when the edge costs are non-negative and the algorithm is implemented correctly.

UCS typically uses a priority queue ordered by accumulated path cost.

Comparing Uninformed Search Algorithms