Methods of Finding the Most Efficient Circuit

Coming up next:

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

Replay
Your next lesson will play in 10 seconds
• 0:01 The Traveling Salesman Problem
• 1:43 Brute Force
• 2:37 Nearest Neighbor
• 3:58 Repeated Nearest Neighbor
• 4:49 Cheapest Link
• 6:37 Lesson Summary
Save Save

Want to watch this again later?

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

Timeline
Autoplay
Autoplay
Speed

Recommended Lessons and Courses for You

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.

After watching this video lesson, you will understand several ways in which you can solve the famous traveling salesman problem. You'll also learn the drawbacks to each solution method.

The Traveling Salesman Problem

The traveling salesman problem is a big problem in graph theory. Why? Because it has applications in the real world. Real travel salesman working for businesses deal with this problem every day. The problem lies in finding the cheapest route that visits all desired locations just once. Ideally, you end up where you started.

Remember that, in graph theory, we don't deal with our traditional pie charts and such; instead, we deal with what looks like a connect-the-dots game where the lines are edges and the dots are called vertices. In graph theory, this is the same as finding the best Hamilton circuit in a weighted graph where each edge of the graph has a cost to it. In the real world, it is distance or the cost of traveling a certain path. The greater the distance, the higher the cost in gas or other travel fees.

For example, if you start in Los Angeles and your choices of other cities are San Diego and San Francisco, it would be cheaper to travel to San Diego because it is much closer to Los Angeles. The distance is much smaller. If you only have three cities to worry about, such as in this quick example, then it would be an easy task to come up with an ideal cheapest path of travel. But what if you had a longer list of cities to visit? How could you find your best route then? This video lesson deals with this exact question. Let's look at what options we have.

Brute Force Method

The first option is called the brute force method. Using this method, we systematically list each Hamilton circuit and then calculate each to see which one is the best circuit. With this method, we are sure to find the best route because we will have calculated the cost of each and every circuit. But, the drawback of this method is inefficiency. Think about this. If we have a list of just ten cities, the number of Hamilton circuits that we need to calculate are (10 - 1)! = 9! = 362,880. That's a lot of circuits! Just think of the time needed to calculate each one. We can say that this brute force method is not an efficient one, but it is an optimal one.

Nearest Neighbor Method

The next option we have available is called the nearest neighbor method. In this method, we choose the next closest location based on where we currently are. We keep going until we have visited all the cities. For example, say our list of cities includes Los Angeles, San Diego, San Francisco, Eureka, Tucson, and Phoenix. If we start in Phoenix, our next closest city is Tucson. From Tucson, our next closest city is San Diego. We keep working like this until we have visited every city. Now, this method can work to produce a great route if we happen to choose a good starting point. But if we choose a not-so-good starting point, such as San Diego, then we'll end up with a more expensive route. See, starting in San Diego, we would go to Los Angeles, then to San Francisco. But what about Tucson and Phoenix? They would end up being visited last.

Do you see how this route is not an optimal route because of the extra distance needed to backtrack to these two cities? The nearest neighbor method is an efficient method, though, because we can find a route on the first go.

Repeated Nearest Neighbor Method

We could expand our nearest neighbor method to the repeated nearest neighbor method. In this approach, we choose several cities as our starting points and then choose a route based on the nearest neighbor method. For example, we could have starting cities of San Diego, Tucson, and Eureka. We then see which starting city gives us the better route by following the nearest neighbor method from each starting city. Yes, this method provides a more optimal route than the nearest neighbor method, but it still isn't as optimal as we would like. Why? Well, if we picked the wrong cities again, we would still end up with routes that are not optimal. So, this method again is not optimal. But it is efficient because we only have to calculate a few routes.

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.
Back
What teachers are saying about Study.com

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!

Support