Scribd
Upload
3 views17 pages

Traveling Salesman Problem Analysis

The document discusses the Traveling Salesman Problem (TSP), which involves a salesman visiting a set of cities and returning to the starting point while minimizing the trip length. It highlights the limitations of the greedy algorithm in solving TSP, noting that it may not yield optimal solutions for larger and more complex instances. The document also references key literature on algorithms and provides a brief overview of the advantages and disadvantages of the greedy method.

Uploaded by

manishchauhan20561
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
3 views17 pages

Traveling Salesman Problem Analysis

The document discusses the Traveling Salesman Problem (TSP), which involves a salesman visiting a set of cities and returning to the starting point while minimizing the trip length. It highlights the limitations of the greedy algorithm in solving TSP, noting that it may not yield optimal solutions for larger and more complex instances. The document also references key literature on algorithms and provides a brief overview of the advantages and disadvantages of the greedy method.

Uploaded by

manishchauhan20561
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Amity School of Engineering and Technology

Amity School of Engineering &


Technology
[Link] CSE, Semester 5
Analysis and Design of Algorithms

1
Solution to MST Problem

2
Traveling Salesman Problem
• The traveling salesman problem consists of a
salesman and a set of cities.

• The salesman has to visit each one of the cities


starting from a certain one (e.g. the hometown) and
return to the same city.

• The challenge of the problem is that the traveling


salesman wants to minimize the total length of the
trip.
3
Traveling Salesman Problem
• The traveling salesman problem can be described as
follows:

• TSP = {(G, f, t): G = (V, E) a complete graph,


– f is a function V×V → Z,
– t ∈ Z,
– G is a graph that contains a traveling salesman tour with
cost that does not exceed t}.

4
Traveling Salesman Problem

5
Traveling Salesman Problem

6
Traveling Salesman Problem

7
Traveling Salesman Problem

8
Traveling Salesman Problem

9
Traveling Salesman Problem
• The greedy algorithm fails quite spectacularly for
the Traveling Salesman Problem

• Cycle ABDCA
• Cycle ACBDA
10
Traveling Salesman Problem

•TSP Cycle ABDCA = ?

11
Traveling Salesman Problem

•Cycle ACBDA = ?

12
Traveling Salesman Problem

• TSP Cycle ABDCA = 9

• Other Cycle ACBDA = 8

• TSP is not producing optimal solution!!!

13
Advantage of Greedy
• Greedy method is easy to implement. Just search the
best choice from the current state

• In simple case, Greedy method often gives us the


best solution

14
Disadvantage of Greedy
• In large and complex problems, greedy method may
not always give the best solution.

• Usually it takes longer time than any other algorithm


for bigger case of a problem

15
Summary & Expected
Learning

16
References

• T. H. Cormen, Leiserson, Rivest and Stein, “Introduction of Computer algorithm,”


PHI Publication

• E. Horowitz, S. Sahni, and S. Rajsekaran, “Funadmentals of Computer


Algorithms,” Galgotia Publication

• [Link]

17

You might also like