Uninformed and heuristic search strategies notes — Unit 2

Once a problem is formulated as a state-space graph, we use search algorithms to find a solution path.

⇒1.1 Evaluation Criteria

Search algorithms are evaluated based on 4 metrics:

• Completeness: Is the algorithm guaranteed to find a solution when there is one?
• Optimality: Does the strategy find the highest-quality (lowest cost) solution when there are several different solutions?
• Time Complexity: How long does it take to find a solution? (measured in number of nodes expanded).
• Space Complexity: How much memory is needed to perform the search?

Uninformed search strategies have no additional information about states beyond that provided in the problem definition. They can only generate successors and distinguish a goal state from a non-goal state.

They have no concept of 'are we getting closer to the goal?'

⇒2.1 Types of Uninformed Search

The primary difference between these algorithms is the order in which they expand nodes (implemented via a queue mechanism).

Expands the shallowest unexpanded node first. Implemented using a FIFO queue.

⇒3.1 Properties

• Complete: Yes (if the branching factor b is finite).
• Optimal: Yes (but only if step costs are all equal, e.g., 1).
• Time Complexity: `O(b^d)` where b is branching factor, d is depth.
• Space Complexity: `O(b^d)`. This is the massive drawback of BFS. It must keep every node in memory.

An extension of BFS for problems where step costs are not equal (e.g., routing a car through cities). Expands the node n with the lowest path cost `g(n)`.

⇒4.1 Implementation

Implemented using a Priority Queue ordered by path cost `g(n)`.

• Complete: Yes (if step costs > 0).
• Optimal: Yes. (UCS is Dijkstra's Algorithm).
• Time/Space: Can be worse than BFS if the algorithm gets stuck exploring large trees of small-cost actions.

Expands the deepest unexpanded node first. Implemented using a LIFO queue (Stack) or recursion.

⇒5.1 Properties

• Complete: No. It fails in infinite-depth spaces or spaces with loops (unless modified to keep track of visited nodes).
• Optimal: No. It will return the first solution it finds, even if a much shallower, cheaper solution exists.
• Space Complexity: `O(bm)` where m is maximum depth. This is DFS's massive advantage over BFS. It requires very little memory.

A strategy that combines the benefits of DFS (low memory) and BFS (completeness and optimality).

⇒6.1 How it works

It runs a DFS with a depth limit of 0. If it fails, it runs a brand new DFS with a depth limit of 1. Then 2. Then 3. Until a goal is found.

While it seems incredibly wasteful to regenerate the top of the tree repeatedly, mathematically, the majority of nodes are at the bottom layer anyway, so the overhead is minimal (about 11%). IDS is the preferred uninformed search method when the search space is large and depth is unknown.

Informed search strategies use problem-specific knowledge to find solutions more efficiently than blind search.

⇒7.1 The Heuristic Function h(n)

`h(n)` = Estimated cost of the cheapest path from the state at node n to a goal state. (e.g., In a road map problem, `h(n)` could be the straight-line distance from city n to the destination).

If n is a goal node, `h(n) = 0`.

An informed search that expands the node that appears to be closest to the goal.

⇒8.1 Evaluation Function

`f(n) = h(n)`

The algorithm completely ignores the cost of how it got to node n (which is `g(n)`). It is strictly forward-looking.

• Complete: No (can get stuck in loops).
• Optimal: No (greedily taking the immediately obvious path might lead into a massive canyon you have to walk around).

The most widely known form of best-first search. It combines the advantages of Uniform-Cost Search (optimality) and Greedy Search (speed).

⇒9.1 Evaluation Function

`f(n) = g(n) + h(n)`

• `g(n)` = Actual cost to reach n from the start node (Past).
• `h(n)` = Estimated cost to reach the goal from n (Future).
• `f(n)` = Estimated total cost of the path through n.

A is mathematically guaranteed to be Optimal and Complete* if and only if the heuristic `h(n)` is Admissible.

⇒10.1 What is an Admissible Heuristic?

An admissible heuristic is one that never overestimates the true cost to reach the goal. It is optimistic.

Example: Straight-line distance is an admissible heuristic for driving, because roads have to curve around buildings. The actual driving distance will always be greater than or equal to the straight-line distance, but never less.

In many AI problems (like the N-Queens problem or factory scheduling), the path to the goal is irrelevant; only the goal state itself matters. Local search algorithms evaluate and modify the current state directly, rather than building a massive search tree from the start.

⇒11.1 The State Space Landscape

Imagine a 3D landscape where X and Y are configurations of the problem, and Z (Elevation) is the objective function. We want to find the highest peak (Global Maximum).

A loop that continually moves in the direction of increasing value (uphill). It terminates when it reaches a peak where no neighbor has a higher value.

⇒12.1 The Problem: Local Maxima

Hill-climbing does not look beyond its immediate neighbors (it is a 'greedy local' search). If it climbs to the top of a small hill (a local maximum), it will stop, completely missing Mount Everest (the global maximum) right next to it.

To solve the Local Maxima problem in Hill Climbing, an algorithm must sometimes take 'bad' steps (downhill) to escape a local peak and find a larger one.

⇒13.1 Borrowing from Metallurgy

Annealing is the process of heating metals to high temperatures and cooling them slowly, allowing atoms to reach a low-energy crystalline state.

In the algorithm, a 'Temperature' variable `T` starts very high. When `T` is high, the algorithm frequently accepts bad (downhill) moves. As the algorithm progresses, `T` cools down, and the algorithm becomes greedier, locking into a peak.

A variant of stochastic beam search inspired by evolutionary biology.

⇒14.1 The Evolutionary Loop

• Population: A set of randomly generated states.
• Fitness Function: Evaluates how 'good' each state is.
• Selection: The highest fitness states are chosen as parents.
• Crossover (Mating): Parts of two parents are spliced together to create offspring.
• Mutation: Randomly flipping a bit in the offspring's genetic code to introduce diversity.