**Uninformed searches**, also known as blind searches, are search algorithms that explore a problem space without using any specific knowledge or heuristics about the problem domain. They operate in a brute force, meaning they try out every part of search space blindly.

Uninformed searches rely solely on the given problem definition and operate systematically to find a solution. Examples of uninformed search algorithms include breadth-first search (BFS), depth-first search (DFS),uniform-cost search (UCS), depth-limited search , and iterative deepening depth-first search. Although all these examples work in a brute force way, they differ in the way they traverse the nodes.

The **breadth-first search** (BFS) algorithm is commonly used for traversing trees or graphs, where it explores the neighboring nodes in a breadth-first manner, visiting the nodes at the same level before moving to the next level. The breadth-first search approach uses a

You can see more in-depth details about the algorithmic approach here.

Here is a simulation of a breadth-first search, where S represents the starting node, and G represents the goal node. The search will terminate once we reach goal node G.

Let's write a Python code for breadth-first search to find the path in the above graph with starting node `S`

and ending node `G`

.

from collections import dequedef bfs(graph, start, goal):visited = set() # Set to keep track of visited nodesqueue = deque([[start]]) # Queue for BFS, starting with the initial nodeif start == goal:return "Start and goal nodes are the same"while queue:path = queue.popleft() # Get the first path from the queuenode = path[-1] # Get the last node from the pathif node not in visited:neighbors = graph[node] # Get neighbors of the current nodefor neighbor in neighbors:new_path = list(path) # Copy the current pathnew_path.append(neighbor) # Add the neighbor to the pathqueue.append(new_path) # Add the new path to the queueif neighbor == goal:return new_path # If neighbor is the goal, return the pathvisited.add(node) # Mark the node as exploredreturn "No path found between start and goal"# Example graph represented as an adjacency listgraph = {'S' : ['A','H'],'A': ['B', 'C'],'B': ['D', 'E', 'E'],'C': ['F', 'G'],'H': ['I'],'I': ['J']}start_node = 'S'End_node = 'G'print("BFS Path:", bfs(graph, start_node, End_node))

You can find in-depth details about the algorithmic approach at here.

Here is a depiction of a depth-first search simulation, where S represents the starting node, and G represents the goal node. The search will terminate once we reach goal node G.

Let's write a Python code for depth-first search to find the path in the above graph with starting node `S`

and ending node `G`

.

def dfs(graph, start, goal, path=None):if path is None:path = [start] # Initialize the pathif start == goal:return path # If start is goal, return the pathif start not in graph:return None # If start is not in graph, return Nonefor node in graph[start]:if node not in path: # Avoid cyclesnew_path = path + [node] # Append node to the pathresult = dfs(graph, node, goal, new_path) # Recursive callif result is not None:return result # If a path is found, return itreturn None # If no path is found, return None# Example graph represented as an adjacency listgraph = {'S' : ['A','H'],'A': ['B', 'C'],'B': ['D', 'E', 'E'],'C': ['F', 'G'],'H': ['I'],'I': ['J']}start_node = 'S'End_node = 'G'print("DFS Path:", dfs(graph, start_node, End_node))

**Uniform-cost search** (UCS) is an uninformed search algorithm that explores nodes in a graph based on the lowest cumulative cost, aiming to find the most cost-efficient path from the source to the destination. It starts from the root node and expands nodes in order of their minimum cumulative cost. The UCS approach uses a

You can find in-depth details about the algorithmic approach here.

Here is a simulation of a uniform-cost search, with S representing the starting node and G representing the goal node. The search will conclude upon reaching goal node G. The path with the lowest cost is S -> A -> C -> G, which has a total cost of 9.

The **depth-limited search **(DLS) algorithm works like a depth-first search but with a predefined limit. It resolves the issue of infinite paths in depth-first search by imposing a depth restriction. It is generally helpful when a graph has a very large number of nodes. Nodes at the depth limit are considered as having no further successors in this process, and the search terminates.

You can find in-depth details about the algorithmic approach here.

Here is a depth-limited search simulation with a depth level of 2, with S representing the starting node and G representing the goal node. Once the search reaches Level 2, it will halt, preventing us from discovering the goal node.

**Iterative Deepening Search **(IDS) is an uninformed searching strategy that combines the completeness of breadth-first search with the memory efficiency of depth-first search by using a depth limit.

This approach ensures completeness by avoiding infinite or lengthy branches and explores each branch of a node from left to right until the desired depth is reached. IDS then returns to the root node and explores a different branch, resembling the behavior of DFS.

You can find in-depth details about the algorithmic approach at here.

To determine the time complexities of different types of uninformed searches, we can consider the total number of nodes (V) in the case of a tree, and the number of nodes (V) and edges (E) in the case of a graph.

For the scenarios where the level is significant, such as in depth-limited search and iterative deepening depth-first search, we can specify the maximum level (L),

The time complexities for each search algorithm are as follows.

Uninformed search algorithm | Tree | Graph |

Breadth-first search | O ( V ) | O( V+E ) |

Depth-first search | Oï»¿ï»¿ï»¿ï»¿( V ) | O( V+E ) |

Uniform-cost search | O( (V + E) log V ) | O( (V + E) log V ) |

Depth-limited search | O( b | O( b |

Iterative deepening depth-first search | O( b | O( b |

Uninformed search algorithms provide basic strategies for exploring search spaces without additional knowledge about the problem domain. These search algorithms are valuable for solving various problems and are a foundation for more advanced search techniques.

Copyright Â©2024 Educative, Inc. All rights reserved

TRENDING TOPICS