Hello and welcome to the capstone project of the discrete mathematics specialization. In this project, we are going to design and implement efficient programs for solving the so-called delivery problem. So we start by formally stating this problem. It is formally known as the traveling salesman problem, and the name comes from the following natural application. So we imagine N cities and imagine a traveling sales person in one of these cities. And what he or she would like to do, is to visit all the cities, all end cities, return back to the initial city. And of course, he or she would like to minimize the total traveling lengths, okay? So formally, the input to this problem consists of the complete weighted graph. By saying complete, I mean that there is a match between every pair of nodes. And by saying weighted, I mean that there is a number on every edge, and this number we call a weight or just the length of this edge, okay? So a graph may be either directed or not. If it is undirected, then there is just one edge between every pair of nodes. If it is directed, then there is an edge from A to B and an edge from B to A, for every pair of nodes A and B. And in general, the weight of these two edges should not be equal, okay? So what we're looking for is just a cycle that visits every now and exactly once, and has a minimum total weight, or the minimum total length, which is exactly the same. So sometimes, in some applications, we're interested in finding a cycle, in some applications, we're interested in finding it a path. So the difference between a cycle and a path is that a cycle starts and ends in exactly the same node while, when we are talking about a path, we mean a path that starts in some node and ends in some different node. So in a cycle, there are exactly N nodes and exactly N edges, while in a path, there are N nodes and N minus one edges, okay? Now, let's focus on this small example. So in this case, we have an undirected weighted graph, complete undirected weighted graph on five nodes. And we are looking for a cycle that visits every node exactly once. So if you try to find such a cycle in this graph, manually, you will notice quickly that even for this small example it is not so easy, okay? So let's consider a few such cycles. For example, if we just round these graph, we get total length 15. However, if I visit all the nodes in this star shape, now the total length is equal to 11. And it turns out that even 11 is not the best possible in this case. So the best cycle, in this case, has length nine, and that is shown on the slide. In this case, the total length is computed as follows. It is one plus three plus two plus one and then finally plus two. So, it is not difficult to see that indeed, in this case, we visit the total nodes. We visit every node exactly once, and there are exactly five address in this cycle, okay? So there are just a countless number of applications of the traveling salesman problem in practice, and already in this video, we will see several of them. Then the state of the art is that, for this problem, we still do not know a probably efficient algorithm. Mainly, we do not have any algorithm which is guaranteed to find an optimal cycle in time polynomial in them for example. This is just because we still do not know whether the classes P and NP. So, this is a classical optimization problem. So we actually do not expect such algorithm to exist, okay? So and the goal of this project as I mentioned already, is to implement efficient programs that can solve instances consisted of say like 20 or 30 nodes in practice quickly, and that can solve such instances exactly or such graphs exactly, and that can solve much larger instances approximately. By saying approximately, I mean that we're going to output not probably an optimal cycle but a cycle that is guaranteed to be not much worse than an optimal one, okay? As for applications, so first the most obvious application comes from delivery problem, when we need to visit several locations to deliver some goods. So this is a problem that is solved probably millions times per day by delivery companies. So in this case again, we have several points. We know all the distances between them, and we would like to visit all of them, so we're interested in it. And probably we're interested in returning back, right? So we are looking for a cycle, for a traveling salesman person cycle of minimum total lengths. So another natural application, is the case when we are minimizing not the traveling time or not the traveling distance but the traveling price. So imagine that you are going to visit some five cities in the U.S. namely New York City, Miami, Chicago, Seattle and San Francisco. After deciding that you are interested just in these five cities, what you may want to do is the following. You first forget about the math completely, so you now have just these five cities, and then you figure out what are the prices for flight tickets between every pair of these cities. And in particular, what is shown here is that sometimes, the price of traveling from one city to the other one is not equal as it usually happen, to the price of flying back, right? So we have 17 here and 15 here. Of course, these are just random numbers that do not reflect the current prices, okay? So what this example shows is that sometimes we minimize not just the traveling distance or the traveling time, but some different parameter. And in this case, we're actually interested in a complete directed graph, okay? So the next application is drilling a circuit board. So imagine the factory that produces circuit boards. The circuit board is something that looks like shown on the slide. So to produce it in automatic way, they have a machine that drills holes in a circuit board. I'm sorry. And of course, the locations of the holes are pretty fine. So they, for example, look like this. So we would like the machine, for example, a laser to visit all these places and to drill holes in all of them. And of course, again, we would like the ordering of these locations of visiting to be so exact that the total traveling time between them is as small as possible, right? So for example, here on the right we see a potential solution to this problem. So this is probably the shortest surge route. You see, in real life applications of the traveling salesman problem, they may be like hundreds of nodes to be visited, okay? Let me also make a remark. An example that we've have seen is, is an instance of this special case called the Euclidean traveling salesman person problem. In this case, we are not given a graph explicitly. Instead, we are given just end points on the plain specified just by their coordinates. Okay? And the weight on edges between the corresponding points, are given to us implicitly by the well known formula. We have to two points P_i and P_j. Recall, this are just points on the plane, so I assume that this is P_i, this is P_j. The coordinates of P_i is X_i Y_i. The coordinates P_j are Y_i Y_j. The distance between P_i or P_j, so the distance in this case is the same as weight or length. So we know how to compute it, this are just square root of the square of...It should be X_j. I'm sorry. The square of X_i minus X_j and the square of Y_i minus Y_j. So we can get the sum of these squares and we can get the square root. This gives us the distance between the correspondent to points implicitly, so it is not part of the input we can always compute it, right? So and this is an important special case. In many applications, what we are given is essentially endpoints on the plane. And then, let me also state some properties. So when we are given such an instance, we were essentially given an undirected graph because the distance from P_i to P_j is exactly the same as the distance between P_j and P_i. Put it otherwise, the graph in this case is undirected or symmetric. And what is also important about this special case is that the weights in this case satisfy the triangle inequality, namely for every three points P_i, P_j, and Pk, we know that the weight of the electron P_i to P_j, its mass is weighed off the electron P_i to Pk plus the weight of the electron from Pk to P_j. Let me put it otherwise once again. The shortest possible from P_i to P_j is to go directly from P_i to P_j. Each time when we go through some other vertex, P_k, we get probably parts of the same length but not shorter, okay? Finally, let me mention the full renown application which is also quite natural. So again, imagine some complex machine and imagine that there are N mechanical components that needs to be somehow processed or handled by this machine machine. And all these components are of different types, and we know if machine processes some component i and then is going to process some component j, then we need to somehow reconfigure this machine. It should be reconfigured somehow automatically. But in any case, it takes some amount of time to reconfigure a machine before processing component j after processing component i. So in this case again, we are given some graph. We know the time needed to reconfigure a machine after processing the component i and before processing the component j, so what we would like to do is the order of processing all our components which minimizes the total reconfiguration time. So in the next video, we will see one more application and then we will proceed to designing algorithms and programs for these important combinatorial..
