Understanding Classic Algorithms: Divide‑and‑Conquer, DP, Greedy, Backtracking

Today I unexpectedly found my old university textbook “Algorithm Design and Analysis” and, despite not using algorithms much at work, the algorithmic thinking still deeply influences system design. I skimmed through and revisited several classic algorithms, summarizing them below.

Divide‑and‑Conquer

Dynamic Programming

Greedy Algorithms

Backtracking

Branch‑and‑Bound

Divide‑and‑Conquer

Basic Idea

Break a problem into smaller independent subproblems of the same nature, solve them recursively, and merge their solutions to obtain the original problem’s solution.

Applicable Problem Features

The problem becomes easy to solve once its size is reduced sufficiently.

The problem exhibits optimal substructure.

The subproblems are independent (no overlapping subproblems).

Key Points

How to decompose the problem into smaller, similarly solvable subproblems.

The granularity of the decomposition.

Steps

Decompose → Recursively solve → Merge

divide-and-conquer(P)
{
    if (|P| <= n0) adhoc(P); // solve small instance
    divide P into smaller subinstances P1,P2,...,Pk; // split problem
    for (i = 1; i <= k; i++)
        yi = divide-and-conquer(Pi); // solve each subproblem
    return merge(y1,...,yk); // combine solutions
}

Google’s core MapReduce algorithm is a derivative of divide‑and‑conquer.

Example: Merge Sort

Dynamic Programming

Basic Idea

Decompose the problem into overlapping subproblems, store solutions of subproblems, and reuse them to avoid redundant computation.

Applicable Problem Features

Optimal substructure.

Repeated subproblems in recursive computation.

Steps

Identify the property of the optimal solution and characterize its structure.

Define the optimal value recursively.

Compute the optimal values bottom‑up.

Construct the optimal solution using the computed information.

Greedy Algorithms

Basic Idea

Make the locally optimal choice at each step, aiming for a globally optimal solution through a series of locally optimal decisions.

Applicable Problem Features

Greedy‑choice property: a global optimum can be reached by making a sequence of local optimum choices.

Optimal substructure.

Steps

Continuously seek the locally optimal solution.

Examples

Coin change, Huffman coding, single‑source shortest paths, minimum spanning trees (Prim and Kruskal).

Backtracking

Basic Idea

Explore the solution space tree depth‑first; at each node, decide whether to continue exploring its subtree or backtrack based on feasibility.

Applicable Problem Features

Problems whose solution space can be easily constructed.

Steps

Define the solution space of the problem.

Identify a searchable structure of the solution space.

Perform depth‑first search, using pruning functions to eliminate invalid branches.

Example

N‑Queens problem.

Branch‑and‑Bound

Basic Idea

Search the solution space tree using breadth‑first or best‑first (minimum cost) strategies; each live node can be expanded once, generating all its children, discarding those leading to infeasible or non‑optimal solutions, and adding the rest to the live node list until the optimal solution is found or the list is empty.

Example

Single‑source shortest path problem in a directed graph with non‑negative edge weights.

Source: http://blog.csdn.net/cutesource/article/details/5810171