3.2. Uninformed Search Strategies

Uninformed (or blind) search algorithms do not have any domain-specific knowledge. They explore the search space blindly.

Uninformed search strategies are a type of search algorithm that operates without any prior knowledge about the problem domain. Unlike informed search strategies that utilize specific knowledge (like heuristics) to guide the search, uninformed searches rely solely on the structure of the problem. This means they explore the search space without any direction, often inspecting all possibilities until the goal is found.

Imagine searching for a lost item in your house without any hints about its location. You would need to check every room and drawer systematically because you have no clues to help you narrow down where the item could be. This is similar to how uninformed search works.

● Strategy: Explores all nodes at one depth level before moving to the next. ● Data Structure: Queue (FIFO) ● Complete: Yes ● Optimal: Yes (if all step costs are equal) ● Time Complexity: O(b^d) ● Space Complexity: O(b^d) Where b is the branching factor and d is the depth of the shallowest goal. Use Case: When the shallowest solution is desired and the space is small.

Breadth-First Search (BFS) is a search algorithm that explores nodes layer by layer. It starts at the initial state and looks at all neighboring nodes before moving on to nodes that are one layer deeper, ensuring that it finds the shallowest solution first. BFS uses a queue data structure to keep track of the nodes to explore. The algorithm is complete, meaning it will find a solution if one exists, and it is optimal when all steps have equal cost, as it always seeks the shortest path. However, the time and space complexity can grow exponentially, depending on the branching factor and the depth of the problem.

Think of BFS like a methodical approach to searching a multi-story building. You would check all the offices on one floor before moving up to the next floor. This ensures that if someone is on the first floor, you find them before exploring higher floors.

● Strategy: Explores as far as possible along each branch before backtracking. ● Data Structure: Stack (LIFO) or recursion ● Complete: No (infinite-depth spaces) ● Optimal: No ● Time Complexity: O(b^m) ● Space Complexity: O(bm) Where m is the maximum depth. Use Case: When memory is limited and the solution is deep.

Depth-First Search (DFS) is a search algorithm that dives deep into one branch of the search space before backtracking to explore another branch. This method uses a stack data structure (or recursion) to keep track of the nodes. While DFS is space efficient because it does not need to store all nodes at once like BFS, it is not guaranteed to find a solution if the search space has infinite depths. Additionally, it does not guarantee the shortest path to the goal. The time complexity depends on the maximum depth reached, and this can also become exponential.

Imagine exploring a cave system where you choose to follow one path as far as it goes before retracing your steps to try another path. You may miss a shorter route because you followed one path to its end.

--