Search

Summary

The lecture explains how search algorithms work, why they matter for AI, and how approaches have developed from systematically exploring paths to using heuristics and population-based optimization. A shortest-path problem on a weighted graph serves as the main example.

1. Define the search problem

Before choosing an algorithm, specify what counts as a candidate solution. In the shortest-path example, a solution is a path—a sequence of nodes from the start to the destination—and its cost is the sum of its edge weights.

This differs from ordinary node search, where the goal is to find a particular node and the route taken may be secondary. The way a problem is represented determines which algorithms can be applied.

2. Classical graph-search approaches

• Brute-force or exhaustive search: Enumerate possible paths and compare their costs. This can find the true shortest path, but checking every candidate may be too expensive.
• Depth-first search (DFS): Explore one branch deeply before returning to try alternatives.
• Breadth-first search (BFS): Visit nodes level by level, exploring shallower possibilities before deeper ones. DFS and BFS are primarily ways to order node exploration; they are not, by themselves, general solutions to weighted shortest-path problems.
• Uniform-cost search / Dijkstra’s algorithm: Expand the currently least-cost route, using accumulated path cost to guide which candidate is considered next.
• Bidirectional search: Search forward from the start and backward from the destination, aiming to reduce the amount of exploration when the two searches can meet.
• Heuristic-guided search: Use additional information to prioritize promising candidates. Such guidance can make search faster, but its guarantees depend on the properties of the heuristic.

3. Pruning and avoiding wasted computation

The lecture distinguishes methods that reduce search effort while preserving a guarantee of finding an optimal solution from methods that guide search using estimates.

• Backtracking with pruning

  • Keep track of the best complete solution found so far.
  • Extend a partial path only while it could still beat that solution.
  • If all edge weights are positive and a partial path already costs more than the best known route, stop exploring extensions of that path: adding more edges cannot make its cost smaller.
  • Return to an earlier decision point and explore another option.

• Branch and bound

  • Maintain an upper bound from the best complete solution found so far.
  • Estimate a lower bound on the best possible completion of each partial candidate.
  • Prune a branch when its lower bound is no better than the current upper bound.
  • The lecture presents this as a general optimization technique, including in settings such as linear programming.

• Dynamic programming

  • Break a problem into overlapping subproblems.
  • Store results for subproblems and reuse them instead of calculating them repeatedly.
  • For shortest paths, partial minimum costs can be recorded and used to compute costs for longer paths.
  • Unlike heuristic pruning, this approach avoids repeated work by exploiting shared subproblems. Its usefulness depends on the problem having the right structure.

4. A* search and heuristics

A* ranks candidates using both the cost already incurred and an estimate of the remaining cost. In standard notation, this is commonly expressed as (f(n)=g(n)+h(n)), where (g) is the cost so far and (h) is the heuristic estimate to the goal.

The lecture illustrates a heuristic based on the minimum number of remaining hops, ignoring edge weights. This can help prioritize routes that appear to reach the destination quickly. A heuristic can reduce computation, but whether it preserves completeness or optimality depends on its properties and how the algorithm uses it.

5. Sequential search and reinforcement learning

Many traditional search methods build a solution one decision at a time: select a next step, extend the partial solution, and backtrack or try alternatives when needed. The lecturer relates this sequential structure to reinforcement learning, where an agent learns a sequence of actions that produces a good outcome.

Sequential decisions can be difficult because the value of an action may depend on what happens later. The lecture mentions this connection but does not develop the reinforcement-learning details.

6. Evolutionary computation

The lecture then introduces methods that maintain and improve a population of candidate solutions rather than relying only on a single path being built step by step.

Genetic algorithm (GA):

1. Represent each candidate solution as an individual in a population.
2. Evaluate each individual with a fitness function. For shortest paths, the path’s total weight is the quantity to minimize.
3. Select better-performing individuals as parents; choosing especially strong candidates is described as elitism.
4. Generate new candidates using:
   • Crossover: Combine parts of two parent solutions.
   • Mutation: Randomly alter part of a candidate.
5. Reject invalid candidates where necessary—for example, a recombined path that does not form a connected route.
6. Evaluate the new population and repeat the process until a stopping condition or satisfactory solution is reached.

The lecture describes useful parts of good candidates as “building blocks” that can be combined to produce better solutions. Unlike exhaustive search, a genetic algorithm does not generally guarantee that it will find the global optimum.

Other evolutionary and population-based methods:

• Evolutionary strategies: Traditionally emphasize mutation-based changes to candidate solutions.
• Differential evolution: Uses differences between population members to guide how candidates change.
• Particle swarm optimization (PSO): Individuals adjust their movement using information from the wider group, balancing individual and collective guidance.
• Ant colony optimization: Models how repeated ant journeys and pheromone trails can make promising routes increasingly likely to be followed.

7. Searching structured representations

The lecture distinguishes searching for a single candidate solution from searching over models or structured objects.

• Genetic programming (GP): Represents candidates as structures—often trees—such as mathematical expressions or program code. The search aims to find a good function or program, evaluated using a fitness or loss measure.
• Evolutionary programming: The lecture associates this area with representations such as finite-state machines, which can be expressed as graphs. More complex representations can capture dependencies, but can also make effective search harder.

Main takeaways

• Start by clearly defining the search space and what a solution looks like.
• The representation of the problem affects which search method is appropriate.
• Classical algorithms often generate solutions sequentially; pruning and dynamic programming can reduce unnecessary computation in different ways.
• Heuristics and evolutionary methods can guide search toward promising regions, but their guarantees differ from exhaustive or rigorously bounded methods.
• Search can target not just paths or individual solutions, but also functions, programs, and other structured models.

Speakers and sources

• Presenter: A single speaker gives the lecture. The subtitles do not identify the speaker by name; the video is attributed to the Kangil Kim channel. No other speakers or external sources are featured in the subtitles.