C Program For Christofides Algorithm for TSP
Learn How To Implement Christofides Algorithm in C Programming for solving Travelling Salesman Problem (TSP). Here, you will get complete details of the Algorithm for solving Christofides Problem.
What is Christofide’s Algorithm Travelling Salesman Problem?
Christofides Algorithm is an approximation algorithm to find the optimum and most efficient solution to the Travelling Salesman Problem. The Christofides Heuristic approach for solving TSP Algorithm is an approximation algorithm that offers the solution for Travelling Salesman Problem via Christofides Heuristic Algorithm within the range of 3/2 of the optimal solution length.
This is the best approximation ratio for solving the Travelling Salesman Problem using Christofides Solution Algorithm in C Programming. The Christofides Approximation Algorithm, therefore, helps to achieve 3/2 approximation to the Travelling Salesperson Problem Algorithm
Need of Heuristics Approach
- No Perfect Estimation on the Quality of the Solution
- Guaranteed to Execute in Polynomial Time
- Generates Intuitive Algorithms
Need of Approximation Algorithms
- Guaranteed to Execute in Polynomial Time
- Finds Better Solution within 1 – 2% of the Optimal Solution to the problem
Christofides Algorithm
Let G be a complete graph with a set of vertices v and a function w makes every edge with a non-negative value for its real weight.
- Create a Minimum Spanning Tree T from the Graph G.
- O is a set of vertices having an Odd Degree in the Minimum Spanning Tree.
- Find Minimum Weight perfect matching M in the abstracted subgraph from O.
- Build a Connected Multigraph H where each vertex has an even degree by combining edges of M and T.
- Develop and Eulerian Circuit in the graph H.
- Construct the Hamiltonian Circuit by excluding repeated vertices from the circuit of the previous step.
C Program For Christofides Algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | function Minimum_Spanning_Tree(G = (vertices, edges)) for vertices in vertices do value[vertices] <-- infinity parent_element[vertices] <-- NULL insert vertices into Queue end for value[0] <-- 0 while !Queue.empty() do vertices <-- Queue.removerticeseMin() for x adjacent to vertices do if x ∈ Queue and weight(x, vertices) < value[x] then parent_element[x] <-- vertices end if value[vertices] <-- weight(x, vertices) end for end while end function |
In case you get any Compilation Errors or any doubts in this Christofides Algorithm Implementation in C Programming, let us know about it in the Comment Section below. Find more information about Christofides Solution Algorithm on Wikipedia.
After so many searches gone in vain, I finally found out a good explanation and an algorithm in C programming for Christofides algorithm. Thanks.
The travelling salesman problem can’t be approximated better than 1.0081 in polynomial time.
You can get 1-approximation can be obtained by adapting a truncated version of Held and Karp’s exact O∗(2n)O∗(2n) where n is the number of cities or points.