Uninformed Search Algorithms in Artificial Intelligence

Artificial intelligence (AI) refers to the ability of computers or machines to

perform tasks that typically require human intelligence, such as learning, problem-
solving, decision-making, perception, and natural language understanding. To
solve any task, AI uses certain problem-solving technique to give the best optimal
result quickly which is mostly a Search technique or Search algorithm.

Uninformed search strategies in AI refers to a class of search algorithms that do

not use specific knowledge or heuristics about the problem domain to guide their
search.

The space of all feasible solutions (the set of solutions among which the
desired solution resides) is called search space.

Instead, they systematically explore the search space starting from an initial state
and generating all possible successors until reaching a goal state. Uninformed
search algorithms are generally simple and easy to implement but could be more
efficient in large search spaces or for problems with complex or irrelevant paths.
Uninformed search algorithms are useful for solving simple problems or as a
baseline for more complex search algorithms incorporating domain-specific
knowledge.

In some cases, they may need to be more efficient and effective for more complex
problems, where informed search algorithms, such as A* search, may be more
appropriate.

Various Types Of Uninformed Search Algorithms

Breadth-first Search

Breadth-first search (BFS) is one of the most important uninformed search

strategies in artificial intelligence to explore a search space systematically. BFS
explores all the neighbouring nodes of the initial state before moving on to explore
their neighbours. This strategy ensures that the shortest path to the goal is found.

The algorithm works by starting at the initial state and adding all its neighbours to
a queue. It then dequeues the first node in the queue, adds neighbours to the end of
the queue, and repeats the process until the goal state is found or the queue is
empty.
Steps for performing BFS in a search space:

BFS explores all the nodes at a given distance (or level) from the starting node
before moving on to explore the nodes at the next distance (or level) from the
starting node. This means that BFS visits all the nodes that are closest to the
starting node before moving on to nodes that are farther away.

We use the queue data structure to implement BFS.

 Add the initial state to a queue.
 While the queue is not empty, dequeue the first node.
 If the node is the goal state, return it.
 If the node is not the goal state, add all its neighbors to the end of the queue.
 Repeat steps 2-4 until the goal state is found or the queue is empty.

Advantages
Breadth-first search (BFS) is an algorithm used in artificial intelligence to explore
a search space systematically. Some advantages of BFS include the following:
 Completeness:
BFS is guaranteed to find the goal state if it exists in the search space,
provided the branching factor is finite.
 Optimal solution:
BFS is guaranteed to find the shortest path to the goal state, as it explores all
nodes at the same depth before moving on to nodes at a deeper level.
 Simplicity:
BFS is easy to understand and implement, making it a good baseline
algorithm for more complex search algorithms.
 No redundant paths:
BFS does not explore redundant paths because it explores all nodes at the
same depth before moving on to deeper levels.
Disadvantages
 Memory-intensive:
BFS can be memory-intensive for large search spaces because it stores all
the nodes at each level in the queue.
 Time-intensive:
BFS can be time-intensive for search spaces with a high branching factor
because it needs to explore many nodes before finding the goal state.

 Inefficient for deep search spaces:

BFS can be inefficient for search spaces with a deep depth because it needs
to explore all nodes at each depth before moving on to the next level.

Time and Space Complexity

The time and space complexity of breadth-first search (BFS) in artificial
intelligence can vary depending on the size and structure of the search space.

Time complexity:
The time complexity of BFS is proportional to the number of nodes in the search
space, as BFS explores all nodes at each level before moving on to deeper levels.
For example, if the goal state is at the deepest level, BFS must explore all nodes in
d
the search space, resulting in a time complexity of b , where b is the branching
factor, and d is the depth of the search space.

Space complexity:
The space complexity of BFS is proportional to the maximum number of nodes
stored in the queue during the search. For example, if the search space is a tree, the
maximum number of nodes stored in the queue at any given time is the number of
d
nodes at the deepest level, which is proportional to b . Therefore, the space
d
complexity of BFS is O(b ).

Example
Suppose we have a search space with an initial state "A" and a goal
state "E" connected by nodes as follows:
To perform BFS on this search space, we start by adding the initial state "A" to a
queue:

Queue: A

Explored: {}

We dequeue the first node in the queue, which is "A", and add its
children "B" and "C" to the end of the queue:
Queue: B, C

Explored: {A}

We then dequeue "B" and "C" and add their children to the end of the queue:
Queue: C, D

Explored: {A, B}

We dequeue "C" and add its child "E" to the end of the queue:
Queue: D, E

Explored: {A, B, C}

Finally, we dequeue "D" and "E" and find that "E" is the goal state, so we have
successfully found a path from "A" to "E" using BFS.
Depth-first Search
Depth-first search (DFS) is popular among the uninformed search strategies in
artificial intelligence to explore and traverse a graph or tree data structure. The
algorithm starts at a given node in the graph and explores as far as possible along
each branch before backtracking.

DFS is a recursive algorithm that follows the following steps:

 Mark the starting node as visited.
 Explore all adjacent nodes that have not been visited.
 For each unvisited adjacent node, repeat steps 1 and 2 recursively.
 Backtrack if all adjacent nodes have been visited or there are no unvisited
nodes.
 DFS can be implemented using a stack data structure or recursion. The
recursive implementation is simpler to understand but can cause a stack
overflow if the graph or tree is too large.
DFS has several applications in AI, including path finding, searching for solutions
to a problem, and exploring the state space of a problem. It is particularly useful
when the solution is far from the starting node because it can explore the graph
deeply before exploring widely.
Advantages
 Memory efficiency:
DFS uses less memory than breadth-first search because it only needs to
keep track of a single path at a time.
 Finds a solution quickly:
If the solution to a problem is located deep in a tree, DFS can quickly reach
it by exploring one path until it reaches the solution.
 Easy to implement:
DFS is a simple algorithm to understand and implement, especially when
using recursion.
 Can be used for certain types of problems:
DFS is particularly useful for problems that involve searching for a path,
such as maze-solving or finding the shortest path between two nodes in a
graph.
Disadvantages
 Can get stuck in infinite loops:
DFS can get stuck in an infinite loop if there are cycles in the graph or tree.
This can be avoided by keeping track of visited nodes.
 May not find the optimal solution:
DFS only sometimes finds the shortest path to a solution. It may find a
suboptimal path before finding the shortest one.
 Can take a long time:
In some cases, DFS may take a long time to find a solution, especially if the
solution is located far from the starting node.
Time and space complexity
The time and space complexity of depth-first search (DFS) depend on the size of
the graph or tree being traversed and the implementation of the algorithm.
Time Complexity:
In the worst-case scenario, DFS has a time complexity of O(∣V∣+∣E∣), where |V|
is the number of vertices in the graph or tree and |E| is the number of edges. This is
because DFS visits every vertex and edge once. However, the time complexity can
be reduced to O(∣V∣) if the graph or tree is a simple connected graph.
Space Complexity:
The space complexity of DFS is proportional to the tree's height or the graph's
maximum depth. In the worst-case scenario, where the tree or graph is very deep
and has no branches, the space complexity of DFS is O(h), where h is the tree's
height. This is because DFS uses a recursive function call stack to keep track of the
current path being traversed.
Example
Traversing a binary tree

Consider the following binary tree:

To traverse this tree using DFS, we start at the root node (1) and explore as far as
possible along each branch before backtracking. Here is the order in which the
nodes would be visited.
1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7

We first visit the root node (1), then the left child (2), and so on. Once we reach
a leaf node (4), we backtrack to the last node with an unexplored child (2) and
continue exploring its other child (5). We continue this process until all nodes have
been visited.