Hard Problems and Heuristics

Classic NP-Hard Problems and Heuristic Methods

Three canonical NP-Hard optimisation problems illustrate the need for heuristic approaches when exact solutions are computationally intractable.

Graph Colouring Problem

Problem: Assign colours to the vertices of a graph so that no two adjacent vertices share the same colour, using the minimum number of colours (the chromatic number \(\chi(G)\)).

Applications: Exam scheduling (vertices = exams, edges = shared students), register allocation in compilers, frequency assignment in wireless networks.

Complexity: Finding \(\chi(G)\) is NP-Hard. Deciding whether a graph is 3-colourable is NP-Complete.

Greedy Heuristic

function GreedyColour(G):
    sort vertices by degree (largest first)
    for each vertex v in order:
        assign the smallest colour not used by any neighbour of v
    return colouring

Runs in \(O(V + E)\) but does not guarantee the minimum number of colours.

KEY TAKEAWAY: The greedy colouring heuristic is fast but may use more colours than the chromatic number. The order in which vertices are processed affects solution quality.

0-1 Knapsack Problem

Problem: Given \(n\) items each with weight \(w_i\) and value \(v_i\), and a knapsack of capacity \(W\), choose a subset of items to maximise total value without exceeding capacity. Each item is either included (1) or excluded (0).

Complexity: \(2^n\) possible subsets. NP-Hard in general.

Greedy Heuristic (Value-to-Weight Ratio)

function GreedyKnapsack(items, W):
    sort items by v_i / w_i descending
    total_weight = 0; total_value = 0
    for each item in sorted order:
        if total_weight + w_i <= W:
            include item
            total_weight += w_i
            total_value += v_i
    return total_value

This greedy approach does not guarantee the optimal solution for the 0-1 variant (it is optimal for the fractional variant).

EXAM TIP: Know the difference: in the fractional knapsack, the greedy value/weight ratio strategy is optimal; in the 0-1 knapsack, it is a heuristic only.

Travelling Salesman Problem (TSP)

Problem: Given a complete weighted graph, find the shortest Hamiltonian cycle (visit every vertex exactly once and return to the start).

Applications: Delivery routing, circuit board drilling, supply chain optimisation.

Complexity: \(\frac{(n-1)!}{2}\) distinct tours for \(n\) cities. NP-Hard; no known polynomial algorithm.

Nearest-Neighbour Heuristic

function NearestNeighbour(G, start):
    tour = [start]; visited = {start}; current = start
    while not all vertices visited:
        next = nearest unvisited vertex to current
        tour.append(next); visited.add(next); current = next
    tour.append(start)
    return tour

Runs in \(O(V^2)\). Typically produces tours 20-25% longer than optimal.

Other TSP Heuristics

COMMON MISTAKE: Heuristics for TSP do not guarantee the optimal tour. They trade optimality for tractability. Always state this limitation.

Summary

VCAA FOCUS: Understand why these problems are computationally intractable, describe at least one heuristic for each, and explain the trade-off between solution quality and computational cost. Heuristics overcome the soft limits of computation.