The Traveling Salesman Problem: When Good Enough Beats Perfect

Summary

The video explores the complexity of the Traveling Salesman Problem (TSP), a notorious challenge in computer science. It presents the journey from naïve solutions to advanced heuristics and approximations. Key methods include brute force, heuristic algorithms like nearest neighbor and Christofides, and techniques such as simulated annealing and ant colony optimization. These strategies demonstrate the importance of balancing exploration and exploitation in solving complex problems.

Highlights

• TSP challenges the limits of computer science due to its NP-hard classification. ⚙️
• Brute force solutions quickly become impractical as the number of cities increases. 🏙️
• Heuristic approaches like nearest neighbor provide faster, albeit approximate, solutions. Efficiency is key! ⏱️
• Christofides' algorithm offers a systematic way to get closer to the optimal solution using minimum spanning trees. 🌲
• Local search methodologies like simulated annealing accept worse solutions initially to potentially find better ones later. 📈
• Ant colony optimization mimics nature to find solutions, balancing efficiency and quality of paths found. 🐜
• The video emphasizes not just solving TSP, but how these methods apply to broader computational problems. 🌍

Key Takeaways

• The Traveling Salesman Problem (TSP) is a classic and complex problem in computer science, pivotal for understanding algorithm design and optimization. 🧭
• A brute force approach to TSP is impractical for large datasets, highlighting the need for smarter, more efficient algorithms. 💡
• Heuristic methods like nearest neighbor and Christofides provide 'good enough' solutions when optimal solutions are computationally challenging. 🤖
• The concept of local search, including techniques like simulated annealing and ant colony optimization, help in refining solutions by balancing exploration and exploitation. 🔍
• Understanding and solving TSP aids in tackling a wide array of real-world problems, extending the applications of algorithms in various fields. 🌐

Overview

The Traveling Salesman Problem (TSP) is a cornerstone challenge in computer science, illustrating the difficulties in finding the shortest possible route that visits each point once and returns to the origin. Though the problem is simple to state, solving it efficiently is far from it, classified under NP-hard problems, signifying it could take non-polynomial time to compute as the size increases.

To tackle TSP, researchers have developed various approaches, from naive brute force methods to sophisticated heuristic and approximation techniques. The video highlights algorithms like nearest neighbor and Christofides, which, while not perfect, strive to offer 'good enough' solutions when optimal solutions are computationally out of reach. These approaches bring forth the necessity of balancing computational resources with solution accuracy.

Advanced methods such as simulated annealing and ant colony optimization explore the solution space more creatively. By employing principles of exploration versus exploitation, they help refine possible solutions further than traditional methods. TSP serves as a model problem, showcasing how algorithmic strategies can be applied to broader computational challenges, influencing fields beyond mathematics into areas like logistics and network design.

Chapters

• 00:00 - 00:30: Introduction to Traveling Salesman Problem (TSP) Imagine planning a road trip through the US, and your goal is to find the shortest route that starts in San Francisco, visits every major city exactly once, and returns to San Francisco. This scenario is a variation of the Traveling Salesman Problem (TSP), known as one of the most challenging problems in computer science. The chapter introduces this problem, highlighting its complexity and relevance.
• 00:30 - 01:00: Challenges and Approaches to TSP The chapter titled 'Challenges and Approaches to TSP' discusses the difficulties computers face in solving the Traveling Salesman Problem (TSP). It elaborates on moving away from standard methods of finding exact solutions towards heuristic search and randomized approximation methods. This approach highlights the innovative algorithms used to tackle TSP and explores broader implications on problem-solving techniques in computing.
• 01:00 - 02:30: Graph Theory and Symmetric TSP The chapter discusses how computer scientists have developed distinct algorithmic approaches to tackle problems where finding the optimal solution is nearly impossible. The Traveling Salesman Problem (TSP) is used as a key example. To simplify understanding, the TSP is modeled using graph theory.
• 02:30 - 04:30: Brute Force and Dynamic Programming The chapter discusses concepts related to solving the Traveling Salesman Problem (TSP) using Brute Force and Dynamic Programming. It introduces the notion of representing cities as vertices in a complete graph where there is a direct edge between every pair of vertices. The problem is considered symmetric, meaning the distance from city A to city B is the same as from city B to city A. The chapter also mentions a crucial assumption regarding the direct path between nodes.
• 04:30 - 05:30: Complexity and NP-Hardness of TSP The chapter discusses the significance of the triangle inequality assumption in the Traveling Salesman Problem (TSP), highlighting that it holds true in almost all practical applications. This assumption is crucial for many algorithms used to solve TSP.
• 05:30 - 08:30: Heuristic Solutions to TSP The chapter discusses heuristic solutions to the Traveling Salesman Problem (TSP), specifically focusing on the nature of a 'tour' in graph terms: a path starting from a node, visiting all nodes, and returning to the start. It highlights the brute force method, which entails evaluating all possible tours and selecting the one with the minimal travel distance. However, this method is noted to be impractical for larger instances involving as few as 20 cities.
• 08:30 - 11:30: Greedy Heuristics and MST This chapter delves into greedy heuristics in the context of the traveling salesman problem. It discusses the computational challenges involved when calculating possible tours through multiple cities, highlighting the factorial growth of choices as cities are added. The importance of choosing an appropriate starting city is lessened by the fact that any route must include all cities.
• 11:30 - 16:00: Christofides Algorithm The chapter discusses the Christofides Algorithm, focusing on the calculation of valid tours for the traveling salesman problem. Initially, it's noted that simply using (n-1)! tours for n cities overcounts the possible tours due to reversibility. Therefore, the correct number of tours is (n-1)!/2. It is mentioned that even for n=20, this computation is complex for computers.
• 16:00 - 19:00: Local Search Improvements - 2-opt and k-opt The naive solutions for local search problems often fall short. Although enhancements can be made by leveraging subproblems through a dynamic programming approach, this only marginally improves efficiency. This technique allows for solving moderately larger instances optimally, yet the algorithm remains fundamentally exponential. Travelling Salesman Problem (TSP), for example, is notably difficult as it is categorized under NP problems.
• 19:00 - 24:00: Simulated Annealing In the chapter titled 'Simulated Annealing', the discussion address complex problems, particularly focusing on the Traveling Salesman Problem (TSP). It highlights that despite significant efforts, no polynomial time algorithm exists for this issue, with the best algorithms operating in exponential time. Given current complexity theory, this is unlikely to change. The chapter underscores the significant challenge this presents for real-world applications requiring solutions to such problems. Simulated annealing emerges as a technique used in these complex scenarios to approximate solutions, reflecting on its potential and limitations in practical applications.
• 24:00 - 28:00: Ant Colony Optimization The chapter discusses the challenge of optimizing solutions in systems with thousands or millions of nodes. It suggests a shift in focus from finding the optimal solution, which is practically impossible at such a large scale, to finding a reasonably good solution. It hints at devising an algorithm for this purpose, though it doesn't specify the solution in the provided text.
• 28:00 - 30:00: Conclusion and Generalization in Problem Solving The chapter discusses a strategy in problem-solving known as the 'nearest neighbor' approach. This method involves starting at a specific city and continually picking the closest unvisited city as the next destination. Once all cities have been visited, the journey concludes by returning to the starting city. In this example, implementing this strategy on a particular graph results in a total distance traveled of 28.2 units.

The Traveling Salesman Problem: When Good Enough Beats Perfect Transcription

• 00:00 - 00:30 thanks to curiositystream for sponsoring this video imagine you're planning a massive road trip through the us and you want to visit all the major cities your goal is to find the shortest route that starts in san francisco hits every single city exactly once and then returns back to sf a lot of you might have naturally solved some variations of this problem but what you may not know is that this problem is notoriously one of the most difficult problems in computer science today we're going to talk about the traveling salesman problem or tsp
• 00:30 - 01:00 [Music] in this video we'll talk about why this problem is really difficult for computers to solve and how we might get past those complexities we'll go into why the actual best methods of solving this problem go away from a standard approach of trying to find the exact answer this provides a nice avenue into the beautiful algorithms involved in heuristic search as well as randomized approximation even though we'll focus solely on the tsp what this video is really about is
• 01:00 - 01:30 how computer scientists developed entirely different algorithmic ideas to deal with problems where finding the optimal solution is practically impossible [Music] [Music] before we go into the methods of solving the tsp to simplify things we'll make a few assumptions about our problem the tsp can be modeled as a graph theory
• 01:30 - 02:00 problem where every city is a vertex or node of a graph and the graph is assumed to be complete meaning there exists a direct edge between every pair of vertices given any two cities we'll assume that the distance from city a to city b is the same as the distance from b to a this version of the tsp is often called the symmetric tsp we'll also make another crucial assumption it is always the case that a direct path between two nodes of this
• 02:00 - 02:30 graph is the shortest path between the two cities in other words there is no way a better path between the two cities exists by visiting some intermediate city in between this is formerly known as the triangle inequality assumption for the tsp almost all practical applications of the tsp have these assumptions hold true it's essential for many of the algorithms we'll cover [Music] one of the first steps in any complex problem is to try the most direct method
• 02:30 - 03:00 of finding a solution for the tsp what we're looking for is a tour of the graph which is defined as a path that starts in a node visits all the nodes in the graph and then returns back to the starting node the brute force solution involves finding every single possible tour of the cities and then picking the tour that has the minimum total distance traveled this works for small instances of the problem but as soon as you get into even the realm of just 20 cities it already
• 03:00 - 03:30 becomes completely unreasonable for a computer to even try counting the total number of possible tours that go through all possible cities is an interesting problem the starting point of the tour doesn't actually matter since any valid route will touch all the cities once we have a starting city there are n minus one choices for the next city and after that there are n minus two choices and so on so forth until there's only one more choice that involves returning to the original city
• 03:30 - 04:00 so it seems like the number of tours possible is n minus 1 factorial right not quite we're actually over counting for any possible tour from the starting point i can actually get the exact same tour by reversing the order of the other cities so the correct number of valid tours for n cities is n minus one factorial divided by two and if we plug in 20 into this expression we already have a number that computers will really struggle with so
• 04:00 - 04:30 this naive solution is all but useless some slight improvements can be made such as considering sub problems appropriately in a dynamic programming type approach this method is commonly used to solve slightly larger instances optimally but even with these optimizations we still get an algorithm that is fundamentally exponential in fact one of the reasons the tsp is such a challenging problem is that it belongs to a class of problems called np
• 04:30 - 05:00 hard problems without going too much into a rabbit hole of complexity theory what this roughly means is we have a high confidence that there doesn't exist a polynomial time algorithm for this particular problem as of right now the best optimal solution algorithms all run in exponential time and it'll most likely be that way forever based on our current understanding of the field now the unfortunate aspect of the tsp is that real world applications often require finding solutions to
• 05:00 - 05:30 thousands and perhaps even millions of nodes so the big question is how do we overcome the fact that finding optimal solutions is essentially impossible at that scale this completely changes the perspective on how we attack this problem since we can't find the optimal solution practically let's shift our thought process to finding a reasonably good solution to the problem if i asked you to define an algorithm to find one solution that you think might
• 05:30 - 06:00 be good what would you do one of the most natural ideas might be to start at a particular city and just pick the nearest city as the next choice at every step we continually visit the city that is closest among all the remaining unvisited cities once we've hit all the cities we return to the starting city in this particular graph using this method gives us a total distance of 28.2
• 06:00 - 06:30 and the optimal route turns out to be the following tour with distance 27 this method that involves finding the nearest city is called the nearest neighbor heuristic clearly it's not the optimal solution but it does beg the question how do we measure how good a solution from this approach is the question of measurement is actually quite tricky within the context of the tsp in smaller instances such as this graph it's reasonable to compare to the true optimal value
• 06:30 - 07:00 we can evaluate the performance of the ratio of the heuristic cost to the optimal cost which naturally can also be converted to a percentage over the optimal value but when you get to the scale of thousands of nodes what do you even do you don't know the optimal solution and what's even worse for the tsp given a solution you can't even verify that it's optimal like i said the tsp is hard in practice what computer sciences tend
• 07:00 - 07:30 to use to baseline the solutions to the tsp is instead of trying to compare to the optimal solution they instead compare to a lower bound while we can't reliably figure out the optimal solution there are efficient techniques to find a value which is guaranteed to be less than the optimal cost but not too far off there's a parallel concept to the tsp called the minimum spanning tree or mst the mst is defined as a collection of edges of a graph that connect all
• 07:30 - 08:00 vertices introduce no cycles or loops and also has minimum weight this is a similar optimization problem to tsp but it turns out that finding the minimum spanning tree has several polynomial time algorithms the mst is quite a useful concept in the context of the tsp so let's dive a little deeper one efficient algorithm for finding the mst is called prim's algorithm we start with a random vertex at every
• 08:00 - 08:30 step it considers the set of vertices we've processed as part of the tree and a set of vertices we've yet to encounter to determine the best edge to pick as part of the tree we simply take the minimum edge weight between these two sets every time we add an edge we adjust the sets moving the subsequent vertex accordingly by repeatedly applying this step until all vertices have been processed you are guaranteed to find the minimum spanning tree
• 08:30 - 09:00 prim's algorithm is a classic example of a greedy approach that provides the optimal solution and an interesting result is that the minimum spanning tree is always a lower bound for the tsp an easy way to see this is to imagine we have the optimal tsp tour let's take this tour and delete an edge we now have a spanning tree which must be at least the cost of the minimum spanning tree as a result the minimum spanning tree is
• 09:00 - 09:30 guaranteed to be a lower bound in fact we can even improve this lower bound how this is done is we exclude a single vertex v find the minimum spanning tree of the remaining vertices and then connect the two shortest edges from the excluded vertex back into the tree this is called a one tree the one tree has exactly one cycle and it's guaranteed to be a lower bound on the optimal tour of the tsp can you figure out why
• 09:30 - 10:00 well we know that the optimal tsp tour from this vertex v has to leave the vertex and then return back to v whatever edges the optimal tsp uses can be no better than the corresponding two edges from the one tree since these two edges are literally the closest edges to vertex v and the remaining part of the one tree is a minimum spanning tree as a result it must also have less weight than the spanning tree created by the remaining part of the tsp tor excluding edges from vertex v
• 10:00 - 10:30 thus every one tree must be a lower bound of the optimal tsp tour in fact one nice way to get the best lower bound is to go through all possible one trees and then take the maximum weight one tree this maximum weight one tree is going to be the closest to the actual true optimal solution this is often called the one tree lower bound to a tsp and it's a relatively easy approach to compare different
• 10:30 - 11:00 heuristic and approximation algorithms so going back to the nearest neighbor approach in practice on random configurations of nodes where the distances are treated as euclidean distances the ratio of the nearest neighbor's solution to the one tree lower bound is about 1.25 this is the average randomized case so there's of course going to be instances where the nearest neighbor approach ends up doing much worse but overall i find it pretty impressive that such a simple heuristic does that well
• 11:00 - 11:30 we can actually improve upon the nearest neighbor's method by using a stylistically similar approach instead of taking the best choice from a particular vertex we could instead shift our perspective to all edges in the graph at once the idea is to basically repeatedly try to add the lowest weight edges to the optimal tor we reject an edge when it either creates a cycle of length less than n or it creates a vertex with
• 11:30 - 12:00 degree of 3. this method is often called the greedy heuristic for generating a tour of the tsp and on average it performs slightly better than nearest neighbors [Music] these two approaches of the nearest neighbor and greedy heuristics are maybe the most natural ways to get a solution to tsp in fact when it is tough to find an optimal solution to a complex problem a common theme is to go for an easier greedy solution and in this case they
• 12:00 - 12:30 tend to be not too far off from the optimal but maybe we can do better when we were discussing minimum spanning trees some of you may have noticed that a lot of the edges of the optimal tsb tour happen to also align with the minimum spanning tree a natural question then is could we possibly use the minimum spanning tree to come up with a good solution to the tsp
• 12:30 - 13:00 this was the primary motivation of a groundbreaking algorithm in theoretical computer science developed by nicos christopher's the tour of the graph has the property that every node has an entrance and an exit so what this means is every vertex of the tor must have degree 2. if our goal is to transform the mst into a solution to the tsp we'll need to deal with the odd degree vertices of the mst in some manner the rather clever idea that christofides
• 13:00 - 13:30 came up with was to try add edges to the msc to pair up odd degree vertices this is called a perfect matching of the vertices and what christofides wanted is to find a perfect matching that had minimum weight one way to get the minimum weight perfect matching is to iterate through every possible matching and find the one with minimum weight as we do here but there are more clever algorithms that run in polynomial time using the mst and the edges in the
• 13:30 - 14:00 minimum weight perfect matching we can progress towards a solution to the tsp we'll treat the mst and the edges of the minimum weight perfect matching as a unified graph which is formally called a multi-graph one of the quirks of the multi-graph is it's entirely acceptable to have duplicate edges by adding the perfect matching we've now guaranteed that this graph is all even degrees as long as we count duplicate edges separately
• 14:00 - 14:30 the next step of this algorithm is to construct what's called an eulerian tour of the graph which is a path that hits every edge exactly once such a path is always going to exist for graphs that have all even degree vertices since every edge into a vertex will also have a corresponding edge that exits the vertex the last step involves taking this eulerian tour and converting it to a tsp tour which visits every vertex and
• 14:30 - 15:00 returns to the starting vertex we can generate a tsp tour of the vertices by traversing vertices in this eulerian tour one at a time every time we encounter a vertex we've already seen we just skip it and move on to the next vertex of the eulerian tour this guarantees to create a valid tsp tour and this is the result that the christopher's algorithm returns as you can see this particular tour we generated is quite close to the cost of
• 15:00 - 15:30 the optimal of all the solutions to the tsp crystal fetus is one of the most impressive despite the steps involved the algorithm is a rather natural idea of using the minimum spanning tree to cleverly generate a tour that is reasonably close to the optimal tour in practice on random instances it tends to only be about 10 percent away from the one tree lower bound what's even more impressive is that it's been mathematically proven that the worst
• 15:30 - 16:00 case theoretical performance of the christofides algorithm is within 50 percent of the optimal solution the crystal fetus algorithm was discovered in 1976 and to this day almost 50 years later there have not been any significant improvements in the worst case lower bound from a purely heuristic approach the most recent advancement came from a july 2020 paper which you get this improve the bound to 1.5 minus 10 to the
• 16:00 - 16:30 power of negative 36. yeah so it's unlikely that we end up doing much better in the worst case scenario the concept of heuristic and approximation algorithms to generate a reasonably good solution to a hard problem like the tsp is applicable to a variety of fields if you want to learn more about some interesting applications of these algorithms to modern life there's a great documentary on curiosity stream called the secret rules of modern living algorithms
• 16:30 - 17:00 it dives into the many daily uses of the algorithms that we cover on this channel one of the parts of the documentary includes the traveling salesman problem and some of the background history on the struggles of solving it the documentary provides a great story about the history of algorithms and how they became entrenched in our modern society if you're interested in this documentary and want to support the channel you can watch it by signing up for curiosity stream in the link in the description below with the code reducible
• 17:00 - 17:30 for 14.99 you get a full year of access to curiosity streams award-winning documentaries and the ability to stream it on a range of supported devices thanks again to curiositystream for sponsoring this video now that we have a defined method to get a reasonable solution to the tsp a natural question to ask is if there's any method to make modifications and generate a better solution this is where the realm of local search comes into play
• 17:30 - 18:00 once we have a candidate's solution to the tsp there are several simple transformations we can make to see if we can improve upon the solution one such transformation is called random swapping we randomly pick two cities in our current tor order and swap them to create a new tour our goal is to see if these random swaps ever improved the tour another relatively simple tour improvement is called two opt there are some pairs of edges where if we connect them in the only alternative configuration that keeps the tour valid
• 18:00 - 18:30 it ends up improving our tour we can try this for all pairs of edges until we can no longer improve the solution the subsequent graph is now called to opt optimal but your eye can probably tell that there is some more possibility for improvement here we can extend the same principle to three edges and by performing the following switch we actually end up with the optimal dsp solution this is naturally called a three opt
• 18:30 - 19:00 improvement and it falls under the general umbrella of k-opt improvements the larger the k-value is the more likely we are to find an improvement but the trade-off is there is a larger number of candidate solutions that we have to try so it'll generally take longer random swaps two up switches and three up switches are the most common tour improvement methods for the tsp in practice the most reasonable way to generate a solid solution to a tsp is to
• 19:00 - 19:30 use a heuristic search algorithm like nearest neighbor greedy or christofides and then apply some tor improvement post-processing it is important to be aware that even with local search improvements we still have no guarantee of actually finding the optimal solution to understand why let's take a broader perspective on what we're doing in our improvements if we take a tsp problem we essentially are attempting to find an optimal solution among a search space of possible solutions
• 19:30 - 20:00 for example here's the entire search space for a six node tsp problem where the best solutions are mapped to green and the worst solutions are mapped to red let's do an experiment where we rely purely on local search and see what happens our strategy will be to start off with a random solution to the tsp and then continually pick the best two opt switch from all possible 2 opt switches when we reach a tour where no more improvement is possible with the 2 opt switch we're done
• 20:00 - 20:30 in this particular run we actually do end up at the optimal solution but in other starting configurations if we only continuously perform two op switches we can end up with a sub-optimal solution what's going on here is we are essentially stuck at a local minimum in the neighborhood of canada solutions as mentioned before one solution is to maybe expand the neighborhood itself if we include both two opt and three op switches we can go from the local minimum to the global minimum
• 20:30 - 21:00 but this also means we have to evaluate a lot more instances of the tsp so maybe there's another perspective going to the example that didn't quite work one way we might discover the true optimum might be to actually accept a 2-op switch that was worse than our current candidate solution in this example if we accept this particular higher cost solution we can actually discover the true global minimum pretty crazy idea right
• 21:00 - 21:30 but this is indeed a core theme to the next beautiful optimization technique that we can use for the tsp sometimes things have to get worse before they get better what we're going to talk about next is one of my favorite ideas in this space let's talk about simulated annealing the central theme of simulated annealing is at the start of the process will accept solutions that are worse in the hopes of stumbling on a potentially better overall solution how this broad idea is embedded into the
• 21:30 - 22:00 algorithm is incredibly elegant we start with a candidate solution to tsp from one of our algorithms or a random tour we then apply one of the tor improvements either random swap two opt or three opt in our discussions we will just use the two opt improvement technique once we generate a two op transformation we'll check the total cost of the new tour if the cost is less than our candidate solution we'll always accept
• 22:00 - 22:30 it now if the cost is more than our current solution we'll add a little bit of a wrinkle with some probability we will actually accept the higher cost solution if our random number generator decides not to accept the higher cost solution we will reject that transformation and continue exploring as normal how probability is determined is mostly based on a parameter called the temperature at the start of simulated annealing we
• 22:30 - 23:00 will initialize the temperature to a high value a high temperature means that we are more likely to accept solutions that increase the overall tor distance but as we iterate we will reduce the temperature exponentially making it less likely that we will accept worse solutions in later iterations the big idea is that early on in the process we want to explore the search base but later in the process we want to converge on an actual locally optimal solution
• 23:00 - 23:30 the big difference between simulated annealing and a more straightforward two opt or three op search is that we are more likely to explore parts of the search space the other local search methods would have just never even considered now as cool as this concept is theoretically in practice it's often tricky to get the appropriate scheduling of the temperatures finding a way to balance the time it takes to converge and also sufficiently exploring the search space is no easy task
• 23:30 - 24:00 there's a wide variety of findings on the effectiveness of simulated annealing and part of that is a result of all the tuning that is required for the algorithm fun fact the naming of the algorithm is inspired by the physics of crystallization at the start of the crystallization process you have particles that freely move but as time progresses the particles come together in a more regular structure this regularity becomes more and more pronounced until the crystal lattice is entirely defined this is definitely one of the most
• 24:00 - 24:30 creative connections i've encountered between two seemingly unrelated concepts simulated annealing showed one perspective on the balance of exploring the search space versus exploiting good solutions i want to present to you one more method to solving the tsp that may seem radically different but draws on similar ideas let's imagine we have two salesmen that start in a particular city they develop a strategy to pick a tour their goal is to make it more likely to
• 24:30 - 25:00 pick shorter routes but they don't want to simply do a nearest neighbor search so what they do instead is to randomly pick a city based on a distribution that's a function of the distance to the city they want to favor shorter distances so one clever way to define a distribution is to make the probability of traveling to a node the inverse distance divided by the sum of the inverse distances of all unvisited neighbors this will result in the closest nodes
• 25:00 - 25:30 having the highest chance of being visited but it's also randomized they perform the step for every node until they each get a tour these two salesmen then come together and compare results now the core idea behind the next technique to solve the traveling salesman problem is to use this information to affect the likelihood of future salesmen picking and discovering
• 25:30 - 26:00 shorter routes the way we do that is to add the total cost of each tour to a reward system it's often represented by a matrix which will initially all contain equal reward for each edge but when a salesman completes a tour they will add the inverse of the tor cost to each edge they traversed the idea long term here is that edges that are part of better tours will get proportionally larger rewards
• 26:00 - 26:30 at the beginning we only use distances to determine probabilities of transitioning to edges but now we can use this reward matrix in combination with the distance of each edge to impact the probabilities of picking an edge as part of a tour a salesman continuously find tours of the graph edges that are picked as part of the best tours will have higher reward causing it to have a higher likelihood of being picked by a future salesman
• 26:30 - 27:00 at the start of this process we will be exploring a lot of the search space but the big idea is that since rewards for finding shorter tours are proportionally higher the hope is that over time we'll eventually find better and better solutions [Music] in practice this method of finding a tour is called ant colony optimization our salesmen that we use to explore the search space are similar to ants in an ant colony the reward system we use is similar to
• 27:00 - 27:30 how ants deposit pheromones on routes that lead to food sources to attract other ants and the reward matrix is often formerly known as a pheromone matrix [Music] when scaling this method up to larger tsb instances it's common to have a large number of ants repeatedly find tours probabilistically initially with all edges having equal reward and then globally updating the pheromone matrix there are quite a few parameters that you can tune to control how ants explore
• 27:30 - 28:00 the search space for example it's common to use two parameters alpha and beta to control how much we want the distance and pheromone matrix to be weighted in the probability calculations and over time it's even pretty common to decay the previous values of the pheromone matrix to encourage more exploration rather than just exploiting edges that have shown to have good rewards in practice it can be a little tricky to find the right parameters for the search
• 28:00 - 28:30 space in general though ant colony optimization has shown to consistently outperform simulated annealing but again there's a wide variety of performance findings as a result of the various parameters that are involved in this approach regardless of the performance though the ingenuity of this method really stands out and this video just doesn't feel complete without at least mentioning this particular approach so in this video we talked about a variety of methods for solving the tsp
• 28:30 - 29:00 but what i really want to emphasize is these approaches generalize to any difficult problem in computer science the real question we answered in this video is when you're faced with a problem where an exact solution is too difficult to compute what are your options we started with a natural approach of just finding a reasonable solution based on short-term benefits which is the approach of the nearest neighbors and greedy heuristics and more often than not they will end up being reasonably close to the true solution but one of the most powerful
• 29:00 - 29:30 approaches to tsp was the crystal fetus algorithm and the core idea there was that we actually used a simpler version of the tsp problem finding a minimum spending tree to help us come up with a good solution to the harder problem that's a theme that shows up all the time in problem solving another big concept was to not just stop at this initial solution the world of local search showed us techniques to take a solution and iteratively improve it as much as we can
• 29:30 - 30:00 and finally we also touched upon creatively exploring the search space [Music] with simulated annealing we saw that sometimes it can be a good idea to initially accept worse solutions in the hope that it leads us to an area of the search space that has better overall solutions balancing this concept of exploration of the search space but also exploiting solutions that are already good is an incredibly vital concept to and colony optimization it turns out that this notion of exploration versus exploitation also
• 30:00 - 30:30 shows up in many other areas of computer science the tsp in many ways opened the door to the field of combinatorial optimization and it is through the study of the tsp that computer scientists today can apply these techniques to all sorts of applications thanks for watching and i'll see you all in the next one you