One day, Cao Cao told Liu Bei about an underground tunnel connecting nine important cities, in a line, that they could use to pass confidential messages. A single messenger was commanded to deliver messages to all nine cities on a daily basis. To maintain security, the messenger had to fetch the key from another city first before entering the next city. For example, to enter the sixth city, the messenger would need to collect the key from the eighth city first. Cao Cao set the key collection order, and sent the messenger to start his journey from the fifth city, but he didn't know how to come up with the shortest route to conserve the messenger's energy. To gain Cao Cao's trust, Liu Bei proposed to solve this problem for him. He pulled out the magical tablet. So Cao Cao wants Liu Bei to help him delivering messages in a tunnel to all of his defensive pivot points. So he's got a tunnel that runs along underneath all these pivot points, and he needs this message to be delivered, but it's not so simple. He can't just have a runner run all the way along, because there's some other messages that need to be delivered, and we're going to represent these by keys and locks. So the messenger can't just go to point six, because also in their journey of delivering messages, they need to pick up a message from point number eight and deliver it to point number six. So they have to visit point eight before they visit point six. So there's a precedence among the points as well. And so, overall we have this kind of example where the messenger's going to start at point number five. And for example, the red lock and key is going to represent that they have to visit point number four before they visit point number seven. And so they're trying to visit all of these points, and obviously the objective is to do it as quickly as possible, so their defences are ready as soon as possible. So this is, in fact, a form of traveling salesman problem on a line. We're given a set of military pivotal points on a line, a set of precedence amongst them. And we need to visit each pivotal point in turn, starting from in this case the fifth pivotal point, satisfying these precedence requirements and minimising the total distance traveled. That's why it's a traveling salesman problem. So this is a permutation problem. So an important class of these matching problems are permutation problems. So we've got a set of objects and we need to place them in an order. So it's a matching of objects to the numbers 1 to n, where n is the cardinality of the objects. And again, because it's a bijection, it's a matching problem, there's at least two viewpoints. We have the natural one which is for each object, which of the 1 to n positions do we place it in, and indeed, for each position, which object goes in that position? So both the belt problem that we saw in the previous lecture, and this tunnel problem that we're doing now are permutation problems. Here we're trying to decide the order in which we visit these points, these pivotal defence points. In the belt problem we're trying to decide the order in which we put gems in the belt. So let's look at our tunnel model. So we have enumerated type of our pivot points, and we have the first one. Where do we start? That's given to us. And then we've got the positions that we're going to visit them in, which is obviously from one to the size of the pivot points. And so basically we've got a coordinate for each of those pivot points. Where is it? So let's look at the decisions of the tunnel model. Now, remember, this is a permutation problem, so we know that there's two viewpoints of the decisions to be made, and we're going to make use of both of them. So the first viewpoint is we're going to have an array, so for every pivot point, we're going to say which position in the visit is it? So is it the first position that we visit, or is the fifth position that we visit, or the seventh, or the ninth position that we visit? So that's what this array pivot of var position order gives. So every pivot point, in which position does it appear in the order? So that's one viewpoint of the permutation that we're going to build, and the other viewpoint is the other way around. So for every position in the order, which is the pivot point that we visit? So, which is the pivot point we visit first? Which is the pivot point we visit second? Which is the pivot point we visit third that's giving us the route? So these are the two different viewpoints of the permutation that we're going to build up in our tunnel model. And then we can build our constraints and objective using whatever viewpoint is most natural. So obviously the first constraint is we have to start our route at the first position. So that's very natural using this second viewpoint, the route viewpoint, although we could actually also use the first viewpoint. We could also say that the order of the first place is one, which would say the same thing. Now of course we have to make sure these two viewpoints agree, so we have an inverse constraint, saying that the order and the route are inverse functions. So basically the same function, just defined in opposite directions. Now I have to think about the precedence constraint, and the precedence constraint can really only be expressed using the order variables. We're saying that when we visit the pivot point left[i], we have to visit that before we visit the pivot point right[i]. And really that needs these order variables, which are exactly telling us which position in the visit these pivot points are. So we can write that down directly, using that viewpoint of the model. So let's look at the objective now. Now remember the objective is to minimise the total distance that we travel. And the distance is, of course, the distance we go from the position of the coordinate route of i, to the coordinate of route i+1. We keep adding those distances up and that would give us the total distance that we'd travel. And again this is really impossible to write down except using the second viewpoint of the problem. So in this permutation problem we have one constraint, which really requires us to use the first viewpoint and the objective, which requires us to use the second viewpoint. So we can now solve the model and find that the total distance travelled is 58. So in summary, the tunnel problem is actually a simplification of the traveling salesman problem, which is a classic example of computer science problem. But here we have side constraints, we have precedences on the pivot points, so we have to visit some pivot point before we visit others. So the TSP is a very important problem in graph theory, and has many applications in routing and optimisation in general. It's been one of the most studied problems in computer science. But notice in our example of multiple modelling here that some of our requirements were basically impossible to express with one of the viewpoints. So we really needed to have a combined model. We had to have both view points of the problem in order to formulate our complete problem. We needed one viewpoint to express some of the constraints, and another viewpoint to express the optimisation function. So permutation problems always have two viewpoints, because we're always mapping the objects to their position, or we can map a position to the objects that we're permuting. And when we're solving a permutation problem, we should choose the viewpoint that is the easiest or possible to express the constraints and the objective that we want. And otherwise, so we may only need a single viewpoint if it happens that we can express all the constraints and objective with just that single viewpoint. But otherwise, we can choose both viewpoints, add our inverse constraint to make sure that those two viewpoints agree. And then we can use whichever is the best viewpoint for expressing each constraint or the objective. And that will allow us to build a very efficient permutation problem solver.
