Search Strategies Lecture Flashcards

Uninformed search algorithms only use information provided within the state space graph itself, rather than external guidance toward a specific goal location.
A solution in these search strategies is a sequence of actions required to move from a start node to a goal node.
Three primary types of uninformed search include:
- Breadth First Search (BFS): Explores all nodes at one level before moving to the next. It guarantees the shortest path in terms of actions but not necessarily path cost.
- Uniform Cost Search (UCS): Finds the optimal solution by considering path costs on the edges of the graph. It is both complete and optimal.
- Depth First Search (DFS): Explores as deep as possible into a branch before backtracking.

Frontier Implementation: The frontier for DFS is implemented as a Stack.
Insertion and Retrieval: Newly generated states are inserted at the front of the queue and retrieved from the same end (LIFO - Last In, First Out).
Exploration Strategy: DFS focuses on exploring the most freshly generated nodes first. It "chases" one branch until it reaches a leaf node.
Backtracking: If a leaf node is not the goal state, the algorithm traces back to the closest unexplored neighbor of a parent node.
Visual Representation: The expansion pattern of DFS is often described as "lightning-like" because it is less consistent than the wave-like patterns of BFS. It takes one branch to its end, leaving space closer to the start state unexplored until much later.
Optimality: DFS does not guarantee an optimal solution. It may return a path that is significantly longer than the actual shortest path. For example, if a goal state $f$ is two actions away but a deeper branch contains the goal three actions away, DFS may find the deeper one first.

Completeness: DFS is not complete. It can fail if the search space has infinite depth or contains loops where the algorithm might get stuck in a cycle.
Space Complexity: The primary advantage of DFS is its linear space complexity, defined as $O(b \times m)$ , where $b$ is the branching factor and $m$ is the maximum depth of the search tree. This makes it much more memory-efficient than UCS in finite spaces because it does not need to store all nodes at every level.
Time Complexity: In the worst-case scenario, the time complexity is $O(b^m)$ . While it may sometimes find a solution faster than BFS if the goal is located at the end of an early branch, on average it must still explore large portions of the state space.
Practical Use Cases:
- Useful when memory is a limiting factor for finding optimal solutions.
- Applicable in scenarios where any valid solution is acceptable rather than a perfect/optimal one (e.g., solving a Rubik's Cube to demonstrate a solution regardless of the number of moves).

Question 1: Applying Uniform Cost Search (UCS)
- Prompt: Given a graph with start state $s$ and goal state $g$ , what is the shortest path and cost using UCS?
- Analysis: UCS prioritizes the path with the lowest cumulative cost. By checking the paths, the solution was identified as the sequence $S \rightarrow B \rightarrow D \rightarrow g$ .
- Numerical Result: The path cost for this sequence is $6$ .
Question 2: Complete vs. Admissible Algorithms
- Prompt: If a search algorithm is guaranteed to find a solution if one exists, what is it called? If it is guaranteed to find the optimal solution, what is it called?
- Answer: An algorithm that always finds a solution if one exists is Complete. An algorithm that always finds the optimal solution is Admissible (or optimal).

Limitations of Uninformed Search: Algorithms like UCS are "blind" because they treat every direction similarly unless specified by edge costs. They explore in all directions equally, which can be inefficient because they do not prioritize paths that move physically closer to the goal state.
Heuristics ( $h(n)$ ): This is the "extra information" that makes a search strategy "informed." A heuristic is an estimation of the distance from a current state to the goal state.
- Estimation vs. Knowledge: If the exact cost were known, no search would be required. Heuristics provide a "rule of thumb."
- Metaphor: The "Warmer/Colder" game. As you move closer to a hidden object, being told you are "warmer" is a heuristic guiding the search without revealing the exact location.
- Relaxed Problems: Heuristics can be thought of as the cost of a solution to a "relaxed" version of the problem where some constraints are removed.
Heuristic Notation:
- $h(n)$ represents the heuristic value for node $n$ .
- The heuristic for a goal state is generally defined as $h(g) = 0$ .

Euclidean Distance: The straight-line distance between two coordinates, calculated via a vector.
Manhattan Distance: The sum of the absolute differences of the coordinates (e.g., in a grid where you can only move up, down, left, or right).
Application in Navigation: In map problems, a heuristic might be the straight-line distance to the target city, even though the actual roads are longer and winding.

Definition: An informed search strategy that prioritizes nodes based solely on their heuristic value ( $h(n)$ ).
Frontier Implementation: Implemented as a Priority Queue, where nodes with the lowest $h(n)$ are at the front.
Example Case (Romania Map):
- If traveling from Arad to Bucharest, the algorithm ignores the actual travel costs on the edges ( $g(n)$ ).
- It only looks at the straight-line distance from each city to Bucharest.
- If Arad is $366$ units from the goal, and its neighbor Sibiu has a lower heuristic value, the algorithm moves to Sibiu.
Properties of Greedy Search:
- Optimality: It is not optimal. It may "chase" a path that seems close to the goal (low heuristic) but is actually a dead end or a much longer path because it ignores the cost already traveled ( $g(n)$ ).
- Completeness: It is not complete in its basic form as it can get stuck in loops. It is only guaranteed to be complete if implemented with a Closed List (to avoid revisiting nodes).
- Complexity: Time and space complexity in the worst case are $O(b^m)$ . However, with a high-quality heuristic, the practical performance is often much faster and more memory-efficient than uninformed strategies.
Behavioral Note: Greedy search tries to make the "biggest jump" toward the goal at every step. If it hits a "wall" (a leaf node that isn't a goal), it must backtrack to find an alternative.