To install StudyMoose App tap and then “Add to Home Screen”
Save to my list
Remove from my list
Kruskal's algorithm is an efficient approach for finding minimum spanning trees, particularly suited for sparse graphs. Unlike Prim's algorithm, Kruskal's algorithm does not start with a specific vertex.
Kruskal's algorithm works by gradually building connected components of vertices. Initially, each vertex forms its own separate component in the prospective tree.
The algorithm repeatedly examines the lightest remaining edge and checks whether the two endpoints belong to the same connected component. If so, the edge is discarded because including it would create a cycle in the prospective tree. If the endpoints belong to different components, the edge is added, and the components are merged.
Kruskal's algorithm employs a greedy approach to finding a minimum spanning tree. It treats each node as an independent tree and connects them only if it offers the lowest cost compared to all other available options.
In the past, when salespeople traveled door-to-door to promote their products, they had to plan their routes efficiently, from house to house or city to city.
Verified writer
Proficient in: Technology
5 (876)
“ Have been using her for a while and please believe when I tell you, she never fail. Thanks Writer Lyla you are indeed awesome ”
The shorter the route, the more advantageous it was for them. Finding the shortest route that visits a set of locations is a challenging problem, especially when dealing with a large number of locations, such as 20 instead of 10.
The Traveling Salesman Problem (TSP) was first formulated in 1930. This problem arises when a salesperson faces routing difficulties in finding the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers. It generalizes the well-known Traveling Salesman Problem (TSP).
The Traveling Salesman Problem (TSP) poses the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city? This problem is a fundamental one in combinatorial optimization and holds great importance in operations research and theoretical computer science.
Let's consider a TSP involving 5 cities with a known distance matrix, denoted as D.
For illustrative purposes, we will explain the formulation using this 5-city TSP. The distance matrix is presented in the following table:
| -- | 10 | 8 | 9 | 7 |
| 10 | -- | 10 | 5 | 6 |
| 8 | 9 | -- | 9 | 5 |
| 8 | 7 | 6 | -- | 8 |
| 6 | 7 | 6 | 9 | -- |
Let Xij = 1 if the salesman visits city j immediately after visiting city i. The objective function is to minimize the sum of distances traveled:
Minimize ∑i∑j dij Xij
Subject to the following constraints:
∑j Xij = 1 for all i
∑i Xij = 1 for all j
Xij = 0, 1
Let's verify whether this formulation is adequate and satisfies all the requirements of a TSP. The objective function aims to minimize the total distance traveled, and the constraints ensure that every city is visited exactly once. However, this formulation is insufficient since it resembles the formulation of the assignment problem. For instance, a feasible solution to a 5x5 assignment problem could be:
X12 = X23 = X31 = X45 = X54 = 1
This solution is not suitable for the TSP because it suggests that the person leaves city 1, goes to city 2, then to city 3, and returns to city 1. Additionally, the person goes to city 4 (from city 5?) and comes back from city 5, resulting in infeasible sub-tours. For example:
X12 = X23 = X31 = 1
Forms a sub-tour of cities 1-2-3-1. It is evident that if one sub-tour exists, there will always be more in the solution. Another sub-tour is represented by:
X45 = X54 = 1
Forming the solution 1-2-4-5-3-1, which is not a sub-tour but a full tour and is feasible for the TSP. The formulation should yield solutions without sub-tours, so we need to add sub-tour elimination constraints.
For a 5-city TSP, sub-tours can have lengths of 1, 2, 3, or 4. For example, Xjj = 1 represents a sub-tour of length 1. We can indirectly eliminate length-1 sub-tours by considering djj = ∞ (shown as a "-" in the distance matrix). Setting djj = ∞ will not allow Xjj = 1. This will also indirectly eliminate 4-city sub-tours because if a 4-city sub-tour exists in a 5-city TSP, there must be a 1-city sub-tour.
A constraint of the form Xij + Xji ≤ 1 will eliminate all 2-city sub-tours. This constraint must be added to the formulation. It will also eliminate all 3-city sub-tours because a 3-city sub-tour should result in a 2-city sub-tour in a 5-city TSP. Therefore, adding the 2-city sub-tour elimination constraint completes the formulation for the 5-city TSP:
Minimize ∑i∑j dij Xij
Subject to:
∑j Xij = 1 for all i
∑i Xij = 1 for all j
Xij + Xji ≤ 1 for all i, j
Xij = 0, 1
If we consider a six-city TSP, we need to add 2-city sub-tour elimination constraints and also include a 3-city sub-tour elimination constraint of the form:
Xij + Xjk + Xki ≤ 1 for all i, j, k
This increases the number of constraints significantly.
In general, for an n-city TSP, when n is odd, we must add sub-tour elimination constraints for eliminating sub-tours of lengths 2 to n-1, and when n is even, we have to add sub-tour elimination constraints for eliminating sub-tours of lengths 2 to n.
For n = 6, the number of 2-city sub-tour elimination constraints is 6C2 = 15, and the number of 3-city sub-tours is 6C3 = 20.
An intriguing application of the minimum spanning tree (MST) is its use in approximating solutions to the Traveling Salesman Problem (TSP). A formal way to define the TSP is to find the shortest path that visits each point at least once.
If we have a path that visits all points exactly once, it forms a special kind of tree. Even if we have a path that visits some vertices more than once, we can always eliminate some edges to obtain a tree. In general, the weight of the MST is less than the weight of the TSP because it involves minimization over a strictly larger set of possibilities.
Conversely, if we trace a path around the minimum spanning tree, we traverse each edge twice and visit all points, making the TSP weight less than twice the MST weight. Therefore, this tour is guaranteed to be within a factor of two of the optimal solution.
It is essential to note that there is no known polynomial-time algorithm to solve the Traveling Salesman Problem exactly. Instead, we rely on estimation algorithms based on heuristic rules. One of the simplest methods to state is as follows: obtain the minimum spanning tree of the given points (using Kruskal's algorithm or Prim's algorithm) and then traverse it in pre-order (visiting the root first and then recursively performing a pre-order traversal of each of its subtrees). Since we can choose any point as the root of the tree, there are several potential solutions. We select the best among them. The solutions obtained through this method have a length of at most double the optimal solution. Due to its efficiency, it can be combined with other heuristics, such as the 2-opt, to further improve the result.
In the typical statement of the TSP, it is explicitly mentioned that the salesperson visits each city exactly once and returns to the starting point. If the distance matrix consists of Euclidean distances, it automatically satisfies the triangle inequality (given three points i, j, k, dik ≤ dij + djk), which enforces the requirement that the salesperson visits each city once and only once. However, if the distances do not satisfy the triangle inequality, or if we are dealing with cost or time instead of distances, it may be necessary to explicitly state that the salesperson visits each city once and only once.
The Traveling Salesman Problem (TSP) involves finding the shortest possible route that visits every city in a given set exactly once and returns to the starting point, while considering the distances between each pair of cities.
It's important to distinguish between the Hamiltonian Cycle problem and TSP. The Hamiltonian Cycle problem seeks to find if a tour that visits every city exactly once exists. In the case of TSP, we already know that a Hamiltonian Tour exists (because the graph is complete), and our goal is to find the minimum weight Hamiltonian Cycle.
For instance, consider the graph shown on the right side. A TSP tour in the graph could be 1-2-4-3-1, with a total cost of 80 (10+25+30+15).
TSP is a well-known NP-hard problem, meaning there is no known polynomial-time solution for it.
There are various approaches to solving the Traveling Salesman Problem:
Dynamic Programming offers a method to solve TSP by defining a recursive relation in terms of subproblems. We consider the given set of vertices as {1, 2, 3, 4, ….n}, with 1 as the starting and ending point. For each vertex i (other than 1), we find the minimum cost path with 1 as the starting point, i as the ending point, and all vertices appearing exactly once. Let the cost of this path be cost(i), and the cost of the corresponding cycle would be cost(i) + dist(i, 1), where dist(i, 1) is the distance from vertex i to 1. The objective is to return the minimum of all [cost(i) + dist(i, 1)] values.
To calculate cost(i) using Dynamic Programming, we define a term C(S, i) to represent the cost of the minimum cost path that visits each vertex in set S exactly once, starting at 1 and ending at i.
We start with subsets of size 2, calculate C(S, i) for all such subsets where S is the subset, and then proceed to subsets of size 3, and so on. It's essential to note that 1 must be present in every subset.
For a set of size n, we consider n-2 subsets, each of size n-1, such that none of these subsets includes the nth vertex. By using the recurrence relation, we can develop a dynamic programming-based solution. There are at most O(n*2^n) subproblems, each of which takes linear time to solve. Therefore, the total running time is O(n^2 * 2^n). While this time complexity is significantly better than O(n!), it remains exponential. Additionally, the space required is also exponential, making this approach infeasible for relatively larger numbers of vertices.
In conclusion, the Traveling Salesman Problem (TSP) is a challenging combinatorial optimization problem that has practical applications in various fields, including logistics, transportation, and circuit design. Its objective is to find the shortest possible route that visits a set of cities exactly once and returns to the starting point while considering the distances or costs between each pair of cities.
While TSP is known to be NP-hard, meaning that there is no known polynomial-time solution that can solve it exactly for all instances, there are several approaches and algorithms to tackle this problem and find approximate solutions that come close to the optimal solution. One such approach we discussed in this report is the use of minimum spanning trees (MST) as an approximation technique. Specifically, Kruskal's algorithm is employed to construct an MST, and this MST is then used to guide the search for a good TSP solution.
By tracing a path around the MST, we create a tour that guarantees a solution within a factor of two of the optimal solution. However, it's important to note that this approach provides an approximation and may not always yield the optimal result.
We also explored the dynamic programming approach for solving TSP, which offers a systematic way to calculate the minimum cost path for visiting all cities exactly once. While this method provides an exact solution, it becomes computationally infeasible for a large number of cities due to its exponential time and space complexity.
In practice, solving TSP often involves a trade-off between solution quality and computational efficiency. Depending on the specific problem instance and its constraints, various algorithms and heuristics can be applied to find satisfactory solutions within reasonable timeframes.
Overall, the Traveling Salesman Problem remains a fascinating problem in the realm of optimization, and researchers continue to explore innovative approaches and techniques to address its complexities and real-world applications.
Kruskal's Algorithm for Solving the Traveling Salesman Problem. (2024, Jan 24). Retrieved from https://studymoose.com/document/kruskal-s-algorithm-for-solving-the-traveling-salesman-problem
👋 Hi! I’m your smart assistant Amy!
Don’t know where to start? Type your requirements and I’ll connect you to an academic expert within 3 minutes.
get help with your assignment
