Uninformed search, also known as blind search, is a search strategy that explores the search space without using any problem-specific knowledge.
- They explore the state space blindly, without any guidance on which paths are more likely to lead to the goal.
- These algorithms systematically explore the state space until they find the goal.
Types of Uniformed Search:
- Depth First Search
- Breadth First Search
- Depth Limited Search
- Iterative Deepening Search
- Bidirectional Search
1.) Depth First Search:
Depth-First Search is a search algorithm that explores a branch of a search tree as deep as possible before backtracking.
- It uses a stack (LIFO – Last In, First Out) to track nodes and continues until a goal is found or all nodes are explored.
- DFS is memory-efficient but may get stuck in infinite loops if cycles exist and is not guaranteed to find the shortest path.
How it Works:
- Start at the initial state.
- Explore one path as deep as possible until a goal state is found or no further states are available.
- If a dead-end is reached, backtrack to the previous state and explore another path.
2.) Breadth First Search:
Breadth-First Search is a search algorithm that explores all nodes at the current depth level before moving to the next level.
- It uses a queue (FIFO – First In, First Out) to track nodes and is complete and optimal when all step costs are equal. However, it requires more memory than DFS.
How it Works:
- Start at the initial state.
- Explore all neighboring states at the current depth before moving to the next level.
- Repeat until the goal state is found.
3.) Depth Limited Search:
Depth-Limited Search is a variation of DFS that imposes a predefined depth limit to prevent infinite loops.
- It helps in cases where the depth of the solution is known in advance.
- However, if the limit is too low, it may miss the goal, and if too high, it behaves like DFS.
How it Works:
- Perform DFS but stop searching when the depth limit is reached.
- If the goal is not found within the depth limit, backtrack and explore other paths.
4.) Iterative Deepening Search:
Iterative Deepening Search is a search strategy that repeatedly applies DLS with an increasing depth limit until the goal is found.
- It combines the low memory usage of DFS with the completeness and optimality of BFS, making it ideal when the depth of the goal is unknown.
How it Works:
- Perform DFS with a depth limit of 1.
- If the goal is not found, increase the depth limit by 1 and repeat.
- Continue until the goal is found.
5.) Bidirectional Search:
Bidirectional Search is a search strategy that starts simultaneously from both the initial and goal states and works toward meeting in the middle.
- It effectively reduces the search space and improves efficiency. However, it requires an efficient method to check when two searches meet.
How it Works:
- Perform BFS (or another search algorithm) from the initial state.
- Simultaneously perform BFS from the goal state.
- Stop when the two searches meet at a common state.
