Chapter 8: Optimization and Search Strategies

Optimization problems ask for the best solution under constraints; search strategies guide how we explore the space of possibilities. This chapter explains practical techniques that range from exhaustive enumeration to clever shortcuts that deliver near optimal answers when exact search would be too slow.

Brute Force and Backtracking

Brute force tries every candidate and returns the best; it is simple and guarantees correctness but can be slow. Backtracking improves on naive enumeration by abandoning partial candidates that cannot lead to a valid or better solution.

Exploring full spaces with plain enumeration

When the search space is small or heavily pruned elsewhere, plain enumeration is acceptable. You generate all candidates, evaluate each objective, and keep the best seen so far. This pattern shows up in small combinatorial tasks and in baseline implementations used for testing more advanced solvers.

# Brute force: choose best subset under a weight limit
best_val, best_set = 0, []
items = [(value, weight) for value, weight in [(6,2),(10,4),(12,6)]]
limit = 6
n = len(items)
for mask in range(1 << n):
  val = wt = 0
  pick = []
  for i in range(n):
    if mask & (1 << i):
      v, w = items[i]; val += v; wt += w; pick.append(i)
  if wt <= limit and val > best_val:
    best_val, best_set = val, pick

Pruning with a recursive backtracking search

Backtracking builds solutions incrementally and abandons a partial branch when a constraint fails or a bound shows no improvement is possible. Good pruning hinges on early detection of impossibility or suboptimality.

# N-Queens with column and diagonal pruning
def n_queens(n):
  cols, d1, d2, sol, out = set(), set(), set(), [], []
  def dfs(r):
    if r == n:
      out.append(sol.copy()); return
    for c in range(n):
      if c in cols or (r-c) in d1 or (r+c) in d2:
        continue
      cols.add(c); d1.add(r-c); d2.add(r+c); sol.append(c)
      dfs(r+1)
      sol.pop(); cols.remove(c); d1.remove(r-c); d2.remove(r+c)
  dfs(0); return out

Bounding and ordering to speed up search

Branch and bound augments backtracking with a numeric bound that estimates the best possible outcome below the current node. If the bound is no better than the current best, the branch is cut. Ordering choices so that promising options are tried first helps find good incumbents early, which improves pruning later.

Heuristics and Approximation

Heuristics guide choices using informed guesses; approximation algorithms provide provable closeness to optimal in polynomial time. Both approaches trade perfect accuracy for speed while aiming to keep solutions useful and consistent.

Designing a useful heuristic score

A heuristic function estimates progress toward a goal. In informed search such as A*, the evaluation combines cost so far and estimated remaining cost. The estimate must never overstate remaining cost for A* to guarantee optimality when the graph edges are nonnegative.

# A* on a grid with Manhattan-distance heuristic
import heapq
def astar(start, goal, passable, neighbors):
  def h(p): return abs(p[0]-goal[0]) + abs(p[1]-goal[1])
  g = {start: 0}; came = {}
  pq = [(h(start), 0, start)]
  while pq:
    f, gc, u = heapq.heappop(pq)
    if u == goal:
      path = [u]
      while u in came:
        u = came[u]; path.append(u)
      return list(reversed(path))
    for v in neighbors(u):
      if not passable(v): continue
      t = gc + 1
      if t < g.get(v, 1e18):
        g[v] = t; came[v] = u
        heapq.heappush(pq, (t + h(v), t, v))
  return None

Achieving guarantees with approximation ratios

An approximation algorithm returns a solution within a known factor of optimal. For example, a greedy set cover achieves a logarithmic factor bound and Christofides for metric TSP achieves a 1.5 factor bound. These guarantees assume problem properties such as triangle inequality or submodularity.

Using greedy and randomized construction

Greedy strategies build solutions step by step using a local rule such as pick the largest benefit per cost. Randomized construction samples many starts and keeps the best result; this often helps escape poor deterministic choices. Both ideas are fast and compose well with local improvement passes.

The Traveling Salesperson Problem

The traveling salesperson problem asks for the shortest tour that visits each city once and returns to the start. Exact solutions scale poorly with city count; practical solvers combine bounding, heuristics, and local search to reach high quality tours.

Solving exactly with DP and branch-and-bound

The Held–Karp dynamic program uses bitmasks and achieves O(n^2 2^n) time; this is feasible for a few dozen cities. Branch-and-bound improves search by cutting subtrees that cannot beat the current best, which extends the usable range on structured instances.

# Held–Karp sketch: minimal cost to reach subset S ending at j
from functools import lru_cache
def tsp_dp(dist):
  n = len(dist)
  @lru_cache(None)
  def F(S, j):
    if S == 1 << j:
      return dist[0][j]
    best = 1e18
    S2 = S & ~(1 << j)
    k = 0
    while k < n:
      if S2 & (1 << k):
        best = min(best, F(S2, k) + dist[k][j])
      k += 1
    return best
  full = (1 << n) - 1
  ans = min(F(full, j) + dist[j][0] for j in range(1, n))
  return ans

Getting strong tours with MST and Christofides

In metric TSP, an MST gives a cheap lower bound and forms the basis for Christofides. The algorithm builds an MST, adds a minimum matching on odd degree vertices, then shortcuts an Eulerian walk. The resulting tour length is within a factor of 1.5 of optimal on triangle-inequality distances.

Constructing and improving with 2-opt and 3-opt

Local improvements swap tour edges to remove crossings and shorten detours. The 2-opt move replaces two edges with two different edges if the total becomes shorter; 3-opt considers three edges for larger gains. These moves are fast and deliver major improvements over naive greedy tours.

Hill Climbing and Local Search

Local search starts from a candidate and repeatedly improves it by small moves. Hill climbing uses the best local move; simulated annealing sometimes accepts worse moves to escape traps. These methods are simple and often work well for large problems where exact optimization would be too slow.

Ascending with simple hill_climb

At each step you evaluate neighbors and move to the best improvement. The method can stall on plateaus or local maxima, which suggests restarts or diversification. Good neighborhood design matters; tiny moves can be too slow, very large moves can be too random.

# Hill climbing for bitstrings to maximize a score
import random
def hill_climb(bits, score, steps=1000):
  cur = bits[:]; best = score(cur)
  for _ in range(steps):
    i = random.randrange(len(cur))
    cur[i] ^= 1
    s = score(cur)
    if s >= best:
      best = s
    else:
      cur[i] ^= 1
  return cur, best

Escaping traps with simulated_annealing

Simulated annealing accepts worse moves with a probability that shrinks over time. Early exploration helps jump between basins; late exploitation refines the current basin. A cooling schedule controls the transition from broad search to fine tuning.

# Simulated annealing skeleton
import math, random
def anneal(x0, neighbors, cost, T0=1.0, alpha=0.995, iters=20000):
  x, cx, T = x0, cost(x0), T0
  for _ in range(iters):
    y = neighbors(x)
    cy = cost(y)
    if cy <= cx or random.random() < math.exp((cx - cy)/T):
      x, cx = y, cy
    T *= alpha
  return x, cx

Balancing intensification and diversification

Intensification pushes deeper around the best found region; diversification spreads effort across the search space. Techniques such as tabu lists, restarts, or adaptive neighborhoods help maintain this balance and reduce premature convergence.

Balancing Accuracy and Efficiency

Exact methods provide guarantees but may be slow; heuristic and approximate methods are faster but may miss the true optimum. The art lies in matching method to requirement, then combining strategies so that you validate quality without overspending time.

Choosing acceptable error with budget and deadline constraints

Define what error or suboptimality you can tolerate and what time or memory you can spend. If you have a hard deadline, prefer algorithms that deliver an anytime solution and improve steadily. If exactness is required for small instances, run an exact solver first and fall back to approximate methods when size crosses a threshold.

Measuring quality with bounds and anytime behavior

Upper bounds come from found solutions; lower bounds come from relaxations such as MST for TSP or linear programming relaxations. Reporting both numbers shows the optimality gap. Anytime algorithms keep a valid best-so-far and refine it as resources allow.

Composing hybrid solvers for robust results

Strong systems often combine methods: seed a local search with a greedy or randomized constructor; interleave branch-and-bound with heuristic incumbents; maintain bounds to know when to stop; record partial states as checkpoints like {…} so that restarts resume quickly. Compose simple parts that you can reason about and test against small exact instances.

Never be tempted to offer a Euclidean algorithm

When location matters, avoid using straight-line (Euclidean) distance as a shortcut for real travel cost. The Earth's surface, roads, rivers, bridges, and elevation all break the clean geometry that Euclid imagined. A simple Pythagorean formula may give an illusion of proximity while ignoring the actual effort required to reach a point.

In practice, “as the crow flies” distance can be dramatically misleading. Two locations may be only 7 km apart in a direct line yet separated by an estuary, mountain, or limited bridge crossings that turn a short trip into hours of detour. A system that claims a store or service is “nearby” based only on Euclidean distance fails users who must travel through real terrain.

Euclidean algorithms are valuable for an early bound or rough clustering, but once a path or travel estimate is needed, switch to graph-based search with real constraints. The integrity of an optimization depends on modeling the world as it is, not as a flat and frictionless plane.