I will talk about P vs NP, NP-complete, and NP-hard, define heuristics in computer science, Hamiltonian cycles, TSP and Metric TSP, approximation algorithms, and optimal vs suboptimal solutions. I will also mention local minima, combinatorial explosion, and why exact solutions become infeasible. Finally, we will see an optimal solution and also an approximation algorithm.
I’ll also discuss the limitations of the chosen approximation algorithm, what could be improved, and mention other options like MST-based solutions, k-opt methods, and metaheuristics such as genetic algorithms, and their trade-offs.
The project code and analysis were developed in collaboration with Matheus Persch as part of the DSA III class at Federal University of Pelotas (UFPel), Brazil.
Prerequisites
Types of problems
Decision problem: You want to answer yes or no.
E.g. “Is there any Hamiltonian cycle in this graph G?” (YES/NO)
Search problem: You want to find a valid solution (if it exists).
E.g. “Find a Hamiltonian cycle in this graph G.”
Optimization problem: You want to find the best solution according to some objective (min/max).
“Find the shortest Hamiltonian cycle in this graph G.” (TSP) - minimization problem
“Find the maximum clique in graph G.” - maximization
clique = subset of vertices in a graph that forms acomplete subgraph
Time complexity class
Informal definition: Set of problems solvable in O(TIME(n)) time.
Example: sorting is in P because it has polynomial-time algorithms.
Formal definition: TIME(t(n)) is the set of languages decidable by a deterministic Turing machine in O(t(n)) time.
Note: “decidable” is formal for languages; for problems like sorting, this feels unnatural, so focus on the informal version for now.
P, NP, NP-Complete, NP-Hard
Polynomial time (P): Those problems which are decidable in polynomial time using a deterministic Turing machine.
TIME(O(n^k)) → k constant
Nondeterministic Polynomial time (NP): Those decision problems whose solutions can be verified in polynomial time by a deterministic Turing machine.
Verification: Given a candidate solution (certificate), we check if it is valid.
E.g. “Given a graph and a certificate, check if it is a valid Hamiltonian cycle.”
NP-Complete (NPC):
is NP
Every problem in NP can be reduced to it in polynomial time
Imagine you can compute 1 billion tours per second: 10^9 tours
10^47 / 10^9 = 10^38 seconds ~= 3 * 10^30 years required to run it
age of universe ^= 13.8 * 10^10 years
It would take far longer than the age of the universe.
What I’ve shown above is called “combinatorial explosion”.
For first city you have n options
For second you have n-1 options
And so on
It is factorial: n * (n - 1) * (n - 2) * ... * 1 = n!
How to solve something that requires this amount of time?
As mentioned, it would require literally more time than is possible in this universe for a small n. To solve this type of problem, one possible approach is using approximation algorithms, which will provide you an approximate solution instead of the optimal one.
Heuristics in Computer Science
Hromkovič, J. (2004), Chapter 6, defines: ‘A heuristic algorithm in a very general sense is a consistent algorithm for an optimization problem that is based on some transparent (usually simple) strategy of searching in the set of all feasible solutions, and that does not guarantee finding any optimal solution’.
They must be much faster than the optimal solution, otherwise you would choose the optimal one.
Types of heuristics:
Constructive: Build a solution following a set of pre defined rules.
Improvement: Start with a feasible solution (any one), and apply successive small changes to improve it.
Compound: Use both, constructive solution and then an improvement phase.
Approximation algorithms
If an optimization problem is NP-hard such as the TSP one, there is no polynomial-time algorithm to solve it, unless P=NP (something we don’t know yet).
Optimal solution = the best solution using a non-approximation algorithm, for example, in TSP using brute force to test all possible tours would provide us for sure the cheapest Hamiltonian cycle.
Suboptimal solution = an approximate solution, isn’t the optimal one, but is close to it.
What an approximation algorithm does is exactly this: instead of trying to get an optimal solution for an NP-hard problem until the universe ends, we use an approximation algorithm to achieve an approximate solution with much faster execution time.
k-approximate approximation algorithm = Means that it is no worse than k times the optimal solution.
for minimization: optimal = 1;2-approximate = 2 (2*opt)
for maximization: optimal = 2;2-approximate = 1 (1/2*opt)
As you can see, an approximation algorithm is never better than the optimal; otherwise it would be the optimal one.
It can even be equal to the optimal solution in some cases (but not always).
Note: To develop approximation algorithms we generally use heuristics (defined in the prerequisites).
Optimal solution for the TSP
There are many optimal solutions, all of them are too slow since this is an NP-hard problem.
We call brute force solution a solution that relies on exhaustive search.
The one I'll show you today is the Branch-and-Bound solution, that consists in backtracking plus pruning unnecessary paths before opening them.
Bound = check the upper/lower bound and cut if already worse to avoid unnecessary paths
lower if is a minimization problem
upper if is a maximization problem
We fix the starting position as 0
Then we start checking permutations, such as (01230, 02130, 02310, …).
If we can identify that, before reaching the end, the current path is already worse than our current best, we do not need to continue (prune), and we stop exploring this path.
Since TSP is a minimization problem, if our currCost is already worse than our bestCost (lower bound), there is no reason to continue exploring that path.
When we reach the end of a path, we return to start and check if currCost < bestCost
// Time Complexity: O(V!)// Space complexity: O(V)unsignedintGraph::runTSPBranchAndBound(TSPStatestate)const{intpathSize=state.path.size();intvertices=getVertices();if(pathSize==vertices){intlastUsedPos=state.path.back();unsignedinttotalCost=state.currCost+getDistance(lastUsedPos,0);returntotalCost<state.bestCost?totalCost:state.bestCost;}for(inti=0;i<vertices;i++){if(state.visited[i]){continue;}// key diff from brute-force versionintcurrDist=getDistance(state.path.back(),i);intnewCost=state.currCost+currDist;if(newCost>=state.bestCost){// cleaning unnecessary paths (prune = Branch-and-Bound)continue;// if I use a specific graph where pruning never happens, it becomes as bad as brute force because// it ends up exploring the entire search space without cutting any branches// fortunately, this is not the case in most situations}state.currCost+=currDist;state.visited[i]=true;state.path.push_back(i);state.bestCost=std::min(state.bestCost,runTSPBranchAndBound(state));state.path.pop_back();state.visited[i]=false;state.currCost-=currDist;}returnstate.bestCost;}
But it is still too slow. Since TSP is an NP-hard problem, we still require an approximation algorithm to get a faster, approximate solution for that problem.
Approximation Algorithm for TSP
The difference between a heuristic and an approximation algorithm is that an approximation algorithm has a proven bound on how far its solution can be from the optimal one.
For example, a 2-approximation algorithm guarantees that in the worst case it will return a solution at most twice as bad as the optimal one. This is proven mathematically.
There are multiple approximation algorithms for the same problem, and this also happens in TSP, where you can solve it using, for example, the MST double-tree algorithm, Christofides algorithm, and more.
Branch-And-Bound is already 10x faster than pure brute force for the 11x11 graph. Even though both algorithms have the same worst case, since branch-and-bound prunes some unnecessary paths.
But as we can see, running it for 15x15 would already take too much time so we didn't.
Approximate: time O(V^2)
And obviously the approximation is much faster and has a worst-case 2-approximation guarantee, and in our files the worst was not 2 but only ~11.45% worse than the optimal.
Extra: Metaheuristic and Genetic algorithm for TSP
Metaheuristics in Computer science
A metaheuristic is a high-level framework with some guidelines to build a heuristic (abstract idea to solve high-level).
A Genetic heuristic is made of:
populations
select
crossover
mutate (small percentage)
improve
repeat
It still requires problem specific solutions, where we use heuristics, for example:
crossover operator (e.g., EAX for TSP)
local search heuristics (2-opt, k-opt, …)
Genetic Algorithm with Edge Assembly Crossover (EAX-GA)
It is a TSP approximation algorithm that does the following:
Populations
N Hamiltonians cycles: [(A→B→C→D→E→A), ham cycle 2, …, ham cycle N]
Select (parents)
Choose randomly X pairs of hamiltonians cycle within your population
Crossover (Edge Assembly Crossover)
Combine the pair parent1 and parent2 (both hamiltonian cycles) to generate a child hamiltonian cycle.
Mutate
Here we select a small rate such as 5% of the generated children and we try to improve them by mutating
Local Search (apply one heuristic to improve)
child = improve_with_2opt_or_LK(child)
Repeat N times until reaching the stop condition (time or iterations)
Now you have a new population of children, you can even get some of the best parents to put in your population and remove the “worst children”.
read best as smaller cost and worst as biggest cost to travel
“Keep best solutions within parents and children and repeat.”
And within this population, select, crossover, mutate, and improve with local search once again until reaching the stop condition.
More solutions for the TSP
There are multiple solutions for the TSP:
2-opt: swap two edges (small neighborhood), fast but weak
k-opt: swap k (constant) edges (larger neighborhood), better solutions, but slower
Lin–Kernighan heuristic (LK): adaptive k-opt, usually best trade-off between solution approximation and running time.
MST-based: build a Minimum Spanning Tree (MST), then do a preorder DFS traversal and shortcut repeated nodes (works for Metric TSP, gives a 2-approximation)
Some of those such as the 2-opt stop in the local minimum, it means that it gets stuck with the best local solutions but it doesn’t mean it’s the global optimal solution.
That means: for every pair of edges you try to swap, but the total distance does not decrease.
It can’t improve anymore but there may exist better solution.
The problem isn’t getting stuck in a local minimum, but how good that local minimum is.
