Video 1-3: Backtracking algorithm for the Turnpike Problem

0:05 Uh let's spend a few minutes on how we could systematically solve this. And maybe you already get the feeling that this is not going to be an efficient algorithm. Uh the name already suggests this. Uh and to not kill the exercise, let me explain the intuition maybe in more detail next time. and first show the algorithm. Um the the key idea is as follows.

0:37 You know that in the difference multi set you're going to have the contribution for the entire string summing everything up. And because the numbers are all positive that's got to be the maximum. So this 18 here will be the sum of all the weights. Can't be in any other way. And it also has to be a unique maximum otherwise we can immediately say it's not possible. So we can always say there's a starting point at zero and there's an end point at the maximum in our difference multi set. So far so good. So the 18 we've already dealt with. That was easy enough. Now how to continue? And the the key idea to have is that from the remaining difference there's again going to be some maximal value and that's going to have to be the next longest substring that we sum up or apart from this 18 which is the sum of all the beads uh the next maximum must come from one that has one less beats. We don't exactly know which and how it looks like. That's all complicated. But there must be some other distance between two points of length 17.

1:57 Yep. >> Maybe I got the the definition wrong, but the leftmost number must most certainly be one of the beats. Um so basically we can subract that from the rightmost and we have >> at least one of the of another uh that will certainly be a sum of multiple beats. I mean, of course, those this number can be there twice, but one of those will be a sum. >> The the tricky bit about your suggestion is I don't know exactly which of these numbers are single beats. This but there's one where I do know namely the smallest. The one has to is that what you meant? >> Okay. >> Ah, okay. Hey, the left was number yeah >> must be one beat. >> So these two together are kind of the next step we can make. The one is a single beat. 17 is all the rest. So there's only really one option. Um but how to place them? The beat one could be at any position. So the beat one corresponds to some distance here where the uh the difference between the end points is of length one. And where exactly that belongs on this line is a bit unclear.

3:22 The 17 helps us in that there's some point between a start point and an end point that has to have length 17 and that's the longest. So the 17 can either start here and go all the way to here or it can be the other way around. But it cannot be anywhere in the middle otherwise you'd get an even longer one. So there's just two options that we have to check. And then the algorithm says, well, I don't know which one. Let's try both and see if we fail or not. And um you can work this through on this example where it does get to a solution. Uh but let me show the code first because that's what the exercises um pick up on. This is exactly that idea formulated in pseudo code. there's nothing else going on. Uh but I want to make sure that the code is clear. Um so it's uh an algorithm that gets the difference multis set as an input.

4:26 It starts by picking out the largest entry there. That's the total distance and then it starts guessing a position. Um this should be rather called S. I think it it plays the role of these uh cumulative sums. So the the collection of ticks locations where I have make made a a position and these are essentially the cumulative sums because I start at zero. Uh so the the naming is a bit uh unfortunate. We know initially we start at zero we end at this total distance but we know nothing else. And then we have a recursive function that in each case um maybe we're already done. We've covered all the distances then we're happy. Otherwise, we find the next largest that we haven't covered. So, we take the total difference multi- set and we subtract everything all the distances that we get implied by the current points that we've already chosen. And among those remaining ones, we pick the largest. And by the same argument, it has to be either flush left or flush right. And so, you try these two options. And flush left means you add this largest as another point that corresponds to picking this one. Then we had a tick here at position 17.

5:53 And so we add this D to our point set. But we don't add it right yet because we don't know whether it works. What we do is uh we check if it already gives a contradiction. Namely, if it implies some the current point set implies a distance multis set that's not contained in what we have, then we're doomed and we cannot continue. Otherwise, we have to keep trying. And then we do a recursive call with this slightly larger point set. We might still at the end come back. Um, yeah, there's a check missing. Uh, if it's not not this no difference multi set, you only return if it succeeds. If it fails, then you keep trying the other option.

6:46 Um, and that looks symmetrically. You take the distance between the largest and this D and try again if that works. And if neither of the two options work then it cannot work. Yeah.

7:23 I guess that's right. It's just not clear immediately what to make of that second piece of knowledge. So, you're right. The um what we do implicitly use is that the smallest number has to be the weight of some bead. And it's also correct that the second smallest weight also has to be the weight of some bead. But we don't know what to make of that. Um, all we can use is placing beads somewhere. And the second smallest could I guess could be almost anywhere. I'm not sure if there's an easy argument to improve upon this, but keep thinking. Yeah.

8:13 >> Do you know where to place it? Uh maybe we can discuss offline. >> Okay, good to see that uh people are hooked by the puzzle. Um this algorithm um the last thing uh to say we discussed the correctness um on the example the bad thing about the algorithm is that it's an exponential time in the worst case because you try two things and uh what you want what what I what I would like you to uh puzzle out in the tutorials is that you can indeed make this go really bad. It tries things for a long time and still fails. And the overall problem, this turn turnpike problem is unclear whether it's NP hard or not. It has all the flavor, all the feeling, the smell of a hard problem, but we don't have a reduction, so we don't know.