Travelling Salesman Problem:
The Traveling Salesman Problem (TSP) is a well-known algorithmic problem that asks for the shortest
route a salesperson can take to visit a set of cities and return to the starting point
The Traveling Salesman Problem (TSP) involves finding the shortest possible route to multiple
destinations and returning to the starting point. However, this is a complex task due to various
constraints such as traffic, last-minute customer requests, and strict delivery windows.
Given a set of cities and the distance between every pair of cities, the problem is to find the
shortest possible route that visits every city exactly once and returns to the starting point.
Note the difference between Hamiltonian Cycle and TSP. The Hamiltonian cycle problem is
to find if there exists a tour that visits every city exactly once. Here we know that
Hamiltonian Tour exists (because the graph is complete) and in fact, many such tours exist,
the problem is to find a minimum weight Hamiltonian Cycle.
For example, consider the graph shown in the figure on the right side. A TSP tour in the
graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80. The problem is a
famous NP-hard problem. There is no polynomial-time know solution for this problem. The
following are different solutions for the traveling salesman problem.
Travelling Sales Person Problem
The traveling salesman problems abide by a salesman and a set of cities. The salesman has to
visit every one of the cities starting from a certain one (e.g., the hometown) and to return to
the same city. The challenge of the problem is that the traveling salesman needs to minimize
the total length of the trip.
Suppose the cities are x1 x2..... xn where cost cij denotes the cost of travelling from city xi to xj.
The travelling salesperson problem is to find a route starting and ending at x1 that will take in
all cities with the minimum cost.
Example: A newspaper agent daily drops the newspaper to the area assigned in such a
manner that he has to cover all the houses in the respective area with minimum travel cost.
Compute the minimum travel cost.
The area assigned to the agent where he has to drop the newspaper is shown in fig:
Solution: The cost- adjacency matrix of graph G is as follows:
costij =
The tour starts from area H1 and then select the minimum cost area reachable from H1.
Mark area H6 because it is the minimum cost area reachable from H1 and then select
minimum cost area reachable from H6.
Mark area H7 because it is the minimum cost area reachable from H6 and then select
minimum cost area reachable from H7.
Mark area H8 because it is the minimum cost area reachable from H8.
Mark area H5 because it is the minimum cost area reachable from H5.
Mark area H2 because it is the minimum cost area reachable from H2.
Mark area H3 because it is the minimum cost area reachable from H3.
Mark area H4 and then select the minimum cost area reachable from H4 it is H1.So, using the
greedy strategy, we get the following.
4 3 2 4 3 2 1 6
H1 → H6 → H7 → H8 → H5 → H2 → H3 → H4 → H1.
Thus the minimum travel cost = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroids:
A matroid is an ordered pair M(S, I) satisfying the following conditions:
2. I is a nonempty family of subsets of S, called the independent subsets of S, such that if B ∈ I
1. S is a finite set.
and A ∈ I. We say that I is hereditary if it satisfies this property. Note that the empty set ∅ is
3. If A ∈ I, B ∈ I and |A| <|B|, then there is some element x ∈ B ? A such that A∪{x}∈I. We
necessarily a member of I.
say that M satisfies the exchange property.
assigns a strictly positive weight w (x) to each element x ∈ S. The weight function w extends
We say that a matroid M (S, I) is weighted if there is an associated weight function w that
to a subset of S by summation:
w (A) = ∑x∈A w(x)
for any A ∈ S.
Next TopicDynamic Programming vs Greedy Method
← prev next →
Latest Courses
