Uninformed Search Strategies Practice Flashcards

Problem Representation and the State Space

Problem-solving in artificial intelligence often utilizes a state space representation, commonly visualized as a graph. This conceptual framework includes several key components and dynamics:

State Space Graph: A graphical representation of all possible states in a problem and the transitions between them.
Search Tree: A hierarchical structure superimposed on the state space to trace the progress of a search. It records the paths explored from the initial state.
Node Classifications:
- Start Node: The initial state where the problem begins.
- Explored Nodes: Nodes that have already been visited and checked against the goal condition.
- Frontier: A data structure recording all nodes that are currently planned for future exploration. It acts as the boundary between the explored and unexplored regions of the state space.
- Unexplored Nodes: States that have not yet been seen or considered by the search algorithm.
Search Progression: As the search proceeds, nodes move from being unexplored to the frontier, and finally to the explored set. This is often visualized as a frontier moving through a space, turning unexplored points into frontier points and then into explored status.

Breadth First Search (BFS)

Breadth First Search is a systematic search strategy that explores nodes at the shallowest level before moving deeper into the search tree.

Frontier Data Structure: BFS utilizes a Queue, which operates on a First-In-First-Out (FIFO) basis. This means the first node added to the frontier is the first one to be expanded.
Expansion Process: When the algorithm visits a node, it checks if it has any children or neighbors. If neighbors exist, they are added to the end of the queue to be considered after all current level nodes have been processed.
Systematic Nature: BFS expands all nodes at depth $d$ before moving to nodes at depth $d+1$ . It begins at root level 0, moves to level 1, then level 2, and so on.
Stopping Condition: The search stops immediately upon finding the goal state. If multiple goals exist, BFS guarantees finding the one located at the shallowest level (the one closest to the start state).
Maze Visualization Example: In a maze where green represents the start and red the goal, BFS progresses like a "big wave." Because it explores equally in all directions, it may end up covering almost the entire searchable space if the goal is far away.

BFS Walkthrough Implementation

In a scenario with a directed graph starting at node $A$ :

Initiate Frontier: The frontier starts with the root node $[A]$ .
Retrieve A: Node $A$ is removed and explored. It generates neighbors $B$ , $C$ , and $D$ . Frontier: $[B, C, D]$ .
Retrieve B: Node $B$ is removed. It generates neighbors $E$ and $F$ . These are added to the end. Frontier: $[C, D, E, F]$ .
Retrieve C: Node $C$ is removed. It generates neighbor $J$ . Frontier: $[D, E, F, J]$ .
Retrieve D: Node $D$ is removed. It generates neighbors $E$ and $H$ , but since it is a directional graph, we only follow valid arcs. Frontier: $[E, F, J, ADE, ADH]$ .
Cycle/Exploration Note: Some implementations maintain an "explored list" to avoid re-adding nodes like $D$ if they appear in a different path (e.g., via $F$ ). Without this list, the algorithm might record the same node multiple times, creating a trade-off between memory usage and speed.

Properties and Complexity of BFS

Completeness: BFS is complete, meaning if a solution exists, BFS is guaranteed to find it.
Admissibility (Optimality): BFS is admissible (finds the shortest path) only if all action costs are identical (e.g., every arc has a cost of $1$ ). It minimizes the number of arcs, not necessarily the sum of edge weights.
Time Complexity: This is denoted as $O(b^{d})$ , where $b$ is the branching factor (average number of children per node) and $d$ is the depth of the shallowest solution.
Space Complexity: Also $O(b^{d})$ . The primary drawback of BFS is managing the memory required to store all nodes at the current level of the frontier.

Uniform Cost Search (UCS)

Uniform Cost Search is a modification of BFS designed to handle problems where transitions have different action costs or weights.

Frontier Data Structure: UCS uses a Priority Queue instead of a standard queue. Nodes in the frontier are ranked based on their path cost.
Ranking Mechanism: The algorithm calculates the path cost by summing all the costs associated with the arcs constituting that specific path from the start node.
Cost Constraints: UCS assumes non-negative costs ( $cost \ge 0$ ). If costs are negative, the properties of the algorithm do not hold.
Relationship to BFS: If all transition costs are equal (e.g., all costs = $1$ ), UCS becomes identical to BFS.
Goal Test Rule: Crucially, the algorithm does not stop when a goal is generated or added to the frontier. It only stops when the goal node is retrieved and expanded from the priority queue. This ensures that no shorter path to the goal exists.

Properties and Complexity of UCS

Completeness: UCS is complete provided that the cost of every action is greater than or equal to a small positive constant $\epsilon$ . This prevents the algorithm from getting stuck in an infinite path of infinitesimally small costs.
Admissibility: UCS is guaranteed to find the optimal (shortest) path.
Time and Space Complexity: The complexity is denoted as $O(b^{C^{*}/\epsilon})$ , where $C^{*}$ is the cost of the optimal solution and $\epsilon$ is the smallest action cost. This represents the worst-case scenario where the algorithm must explore all paths with costs less than the optimal solution cost.
Edge Case Scenario: If one path has a high single-step cost (e.g., $100$ ) and another path has many small-step costs (e.g., 100 steps of cost $1$ ), UCS will explore the many small steps first because their cumulative cost remains lower for a longer duration, even if they eventually lead to a more expensive total path.

Depth First Search (DFS)

Depth First Search is often characterized as the "nemesis" or opposite strategy to BFS.

Frontier Data Structure: DFS uses a Stack, operating on a Last-In-First-Out (LIFO) basis.
Expansion Process: DFS expands the first node generated from its frontier, diving as deep as possible into one branch before backtracking.
Implementation Variants: DFS can be implemented by changing the frontier of a BFS algorithm to a stack or by using a recursive function that calls itself for each neighbor generated.
Progress Visualization: DFS moves down the search tree to the end of a branch. If it fails to find the goal, it traces back up and explores the next most recent branch.

Questions & Discussion

Question: In the maze visualization, how does the BFS search look?
Response (Zach): It moves like a big wave. When it hits a junction, it explores a bit and moves back, slowly filling the space systematically.
Question: If you apply Uniform Cost Search to a maze where every cell transition costs the same, how will it look?
Response (Krishna): It will look exactly the same as BFS because with uniform costs, the priority queue behaves exactly like a standard FIFO queue.
Question: Given a search tree with goal nodes at various depths, which one would DFS find first?
Response: In a tree with nodes labeled alphabet-wide at depth, DFS would find the goal node furthest to the "left" at the deepest level first (e.g., Goal node $D$ in the provided search tree example).
Complexity Inquiry: A student asked about the big O notation for BFS; it was clarified that $O$ notation represents the worst-case scenario. BFS complexity is polynomial/exponential ( $O(b^{d})$ ), which is less ideal than logarithmic or linear complexity.