Copyright

The Traveling Salesman Problem in Computation

An error occurred trying to load this video.

Try refreshing the page, or contact customer support.

Coming up next: Methods of Finding the Most Efficient Circuit

You're on a roll. Keep up the good work!

Take Quiz Watch Next Lesson
 Replay
Your next lesson will play in 10 seconds
  • 0:01 The Traveling Salesman Problem
  • 0:54 A Hamiltonian Cycle
  • 1:58 How to Solve
  • 3:09 Complications
  • 3:50 Lesson Summary
Save Save Save

Want to watch this again later?

Log in or sign up to add this lesson to a Custom Course.

Log in or Sign up

Timeline
Autoplay
Autoplay
Speed Speed
Lesson Transcript
Instructor: Yuanxin (Amy) Yang Alcocer

Amy has a master's degree in secondary education and has taught math at a public charter high school.

Watch this video lesson to learn about the traveling salesman problem. Learn how to identify these types of problems. This is a problem that even computers have a hard time figuring out. Learn why this is so.

The Traveling Salesman Problem

In this video lesson, we talk about the traveling salesman problem. Just what kind of a problem is this? Well, the name kind of gives it away. Just think about what a typical traveling salesman does. He goes from city to city giving people a chance to purchase his things, such as gold watches. The problem comes in when the salesman is trying to figure out the best route to take to visit all the cities on his list. He wants to visit all the cities on his list just once using the shortest route possible and ending up where he began. This is the traveling salesman problem. It is a problem of finding the best route given a list of specific destinations. We can draw out the problem using points or vertices for the cities and lines or edges for the roads. Doing this, we end up with the kind of graph that we talk about in graph theory.

Traveling Salesman Problem
traveling salesman

A Hamiltonian Cycle

And hey, you know what? We have a specific term for this kind of problem in graph theory, too. See if you remember what the Hamilton circuit is. It is a route that visits each vertex just once taking you back to where you started. With a weighted graph, a graph where each edge has a cost associated with it, the best Hamilton circuit is the one that has the least total cost. If the cost associated with each edge is the distance between cities, then the best Hamilton circuit in a weighted graph is the same as our traveling salesman problem.

Hamilton Circuit
traveling salesman

Take a look at this graph, for example. It is a weighted graph. If the number next to each edge was the distance, then if our starting point is D, then the shortest path to the next city would be to point C. That path only has 12, the smallest cost of all the edges. Going from D to C is the shortest, but does this mean that we should take this path in order to visit all the cities? Will doing this give us the shortest possible total route for visiting all the cities?

To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 200 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create an account
Support