Transcript

It's too bad in a way that we can't paint everything black because this map coloring problem sure would be a lot easier. So, uh I don't know what we're going to do about that. The problem is well, how long is this going to take? Maybe if we should Oh, here's what I we're going to do. We're going to wait till either all the laptops are closed or this program terminates, whichever comes first. So, how long is this going to take? I actually don't know. I I I think it'll take more than the lifetime of the universe, but I'm not sure. So, let's take a little bit Let's take a little look at a slightly easier uh map coloring problem.

We'll stop this one and change the map to something I call Simplicia. There's uh 26 uh states, one for each uh letter in the alphabet. And what we're going to do is we're going to do a depth-first search for a suitable coloring of this map. We're going to go in order, A B C D E. And as I've suggested here, at each level, we're going to rotate the color choices so we don't overuse any one color. So, if we launch this particular search, this depth-first attempt to color this map, there it goes, and maybe we should wait until it terminates, or uh maybe we should just let it run and uh it'll terminate perhaps sometime within the lecture, or maybe we should just run it let it run over the weekend, or how long do you think we'd have to wait if we want to come back and watch it terminate?

At roughly 30 frames a second, I'm calculating it all in my head. I don't want to bet my life on it, but I think about 5,000 years. And if you want to use um as many states as there are in the United States in this demonstration, you get up to numbers like 10 to the 17th years. Se- 17th, 18th, 16. I'm not exactly sure. I did a rough calculation. And of course uh you could do some parallels into that, and it's not bad as chess where you need all the atoms in the universe and you still can't do it and things like that acting as computers, but still it's pretty horrendous. And the problem The problem is Well, the problem is the problem is illustrated uh by this um diagram I put in back of me.

If you do a depth-first search and you have a a problem uh like Texas, if you label if you put assign a color to Arizona, Oklahoma, Arkansas, and Louisiana first and then wait around to do Texas last, then you get yourself into a a bind by your fourth choice that you don't discover until your 48th choice. So, what happens then is that you start developing this tree like this, you get to those states surrounding Texas, Texas is the last state assigned a color and there's nothing left for it. And that problem was there on the fourth choice, you know, discover it till your 50th choice. So, you develop a horrendous, impossible impossible search.

So, you simply can't do it that way. But now, uh not to worry, uh we now have I come equipped with the idea of constraint propagation. So, we could just take a country with four states like this. Each can be labeled red, green, blue, and yellow. So, just like in the case of line drawings, we'll pile up all the possible things that the value can be, red, green, blue, and yellow, red, green, blue, and yellow, red, green, blue, and yellow, and we start up constraint propagation. So, we say for the upper left-hand corner state, uh is there any reason to believe that R is impossible? Well, we look at our neighbors and see what kind of constraint flows in from them.

And sure, this guy could be green and this guy could be blue. Uh they don't have to be red, so there's no nothing that rules out red. And there's nothing that rules out blue, and there's nothing that rules out yellow. And there's nothing that rules out green. So, constraint propagation just sits there uh with its finger up its nose doing nothing. So, it doesn't look like we can use either depth-first search uh or uh constraint propagation. So, we could just give up and cry, but uh maybe there's some other approach that will help. So, let me actually work the Texas problem. So, uh with apologies to uh Houston and uh Tyler, uh here's the map of uh Texas.

There we are. And here's uh roughly speaking, Arizona is over here somewhere. And we've got Oklahoma in there, and uh old Bill Clinton's uh state, Arkansas, and then Louisiana sticks out there a little bit. So, there's our map of uh of that uh particular part of the country. So, we've got Arizona here, Oklahoma here, Arkansas here, and Louisiana here, and Texas here. And we have elected to uh assign colors to these states in that order. So, this is one, two, three, four. And we're going to do that. And we're going to rotate our color choices just so we don't overuse any one color. But we're going to also have a look at Texas as we go around because Texas is a state that borders on the states that we're choosing colors for.

So, the only possible colors that Texas can be are red, green, blue, and yellow. So, as we uh make our choices around here, uh we'll say that um I don't know. We don't have to adhere to any particular style. We can say that uh Arizona is going to get uh colored uh red. R. That's going to rule out R over here for Texas cuz no adjacent states can have the same color. Then uh we go over to Oklahoma and we're rotating our color choices, so we'll say that can be green. And uh that's fine cuz it's consistent with the red here, but it rules out the possibility that Texas can be green. And then we uh go over here to Arkansas, red, green, blue.

That's fine. That's consistent with the green on Oklahoma, but if we look at its neighbors, we know that uh Texas is for- forever forbidden to be blue now. So, now we go over to Louisiana. And remember, we're rotating our color choices cuz we don't want to overuse them. So, this means that the first choice we're going to make here for Louisiana is yellow. And that's fine cuz it's consistent with Arkansas, but it's not so fine because it's now ruled out the last possibility for Texas. So, even though Texas is going to be the 50th 48th 48th uh state that we color, uh we're going to say at this point, there's no need in going on.

We'd better back up because there's nothing left for Texas when we get around to coloring it. So, that means that this yellow is ruled out here. This yellow reappears. We select the next color in line for Louisiana, which happens to be red. And now that's consistent uh uh with this uh yellow that's still left for Texas. And it's also consistent with the blue that's up here for Arkansas. So, that's cool. I wonder if we Maybe we can make an algorithm out of that and solve problems like this. Do you see sort of the intuition of what we're doing? Uh we're actually using the martial arts principle again because the whole problem is that local constraints undiscovered local constraints are causing downstream problems.

So, we're going to use the enemy's powers against them, and we're going to look at those local constraints as we go and make sure they're not going to get us downstream, not going to get us later on. So, now I'm going to get I'm going to get uh I'm going to I'm going to look like I'm getting a little formal, uh but I'm just getting a little bit more formal because I want to have a language have some language that I can use to describe what's going on so it's clear what the choices are. So, to start off with, uh we're going to have to have some vocabulary. So, let's start up our vocabulary here.

We're going to have a notion of a variable, uh V, and that's uh something that can have an assignment. Yeah, just you know, Yeah, there's nothing complicated about that, and a value a value X is uh something that can uh be an assignment. A little bit circular, but we're all computer scientists, you know what I mean. So, uh the uh next thing is a little uh slightly less obvious, and that's a notion of a domain, D, and that's going to be a bag of values. Okay, so one more thing, a constraint. That's a a constraint C is a limit on Oh, in our examples it's mostly going to be pairs of variables, pairs of variable values, but in general it could be variable values.

So, if we go back here to Texas, we can say, "Okay, how does that vocabulary drape itself over that configuration?" And the answer is the states have the role of variables, the colors have the role of uh values, and the domains are the remaining color possibilities that we can still use on a particular state, and the constraint in this case is the simple map coloring constraint that no share states that share a boundary can have the same color. So, states are variables, colors are values, domains are bags of colors, and constraints, there's only one, adjacent states can't have the same color. So, that's how it fits with this vocabulary.

So, now what did I actually do here? Well, what I actually did here I'm going to now formalize a little bit by writing it down uh in a in a in pseudo code. So, here we are. We're going to have a look at what we did here into it with our intuition, and we're going to reduce it to a procedure. And here's the procedure. Remember we're doing depth first search on this stuff. I did a depth first search. We're going to do a depth first search, and for each depth first search assignment, Okay, so here I am. I'm labeling Arizona, and then Oklahoma, and then Arkansas, and then Louisiana. When I lay when I give each one of those a label, a color, I'm going to I'm going to do this procedure every time I make one of those assignments.

The last one was the last one that caused trouble was coloring Louisiana yellow. Each time I put one of those colors down, each time I make an assignment, I'm going to do this procedure. So, for each depth first search assignment, for each variable V considered, Now, I don't know what I mean by you don't know what I mean by considered, but when I put a label when I put a a a a value, I chose something as a color for Louisiana, I thought about Texas. So, I was considering the variable Texas when I made the assignment for Louisiana. I'm going to be a little bit vague about what I mean by considered right now because there are lots of choices about how much stuff you actually consider.

So, let me just say consider, and then we'll open that up and talk about the options in a moment. So, for each variable V considered, for let's call that variable V sub I, for each X sub I, for each value in the domain of that variable, I consider each of the things that's still surviving. For each of those, for each constraint C that's between X sub I and some X sub J, where X sub J is an element of the domain of J. Oh, that's sounds awfully fancy, but that just says in the case of Texas up there, whenever I consider one of the values that's still remaining as a choice for Texas, I I want to consider all of the constraints between that variable and and and the adjacent value and the adjacent states, and I want to be sure that anything I leave in the domain is okay for some selection in the other states, some remaining choices in the other states.

So, that's why we're getting pretty nested here, but we're doing depth first search. We are considering the variables in a certain collection of uh uh a a certain collection of variables. For each one of those, we're considering all of the values that still remain in those domains of those variables, and then for each of those values, we're checking to see if it satisfies the some constraint, satisfies the constraint that that are placed upon it. So, for each of these constraints, if there does not exist an X sub J such that the constraint between X sub I and X sub J is satisfied, Well, if in that adjacent place there's no nothing that is consistent with a value, then we got to get rid of it.

If if that's true, if there does not exist some some value in an adjacent variable such that constraint is satisfied, we we're hosed. We got to get We got to get rid of that value. So, we're going to remove X sub I from D sub I. Okay, now that that's fine. Uh that's sort of what I did with Texas. I I as soon as I plop down a value for Louisiana, I said, "Well, what are what what are the possible values in Texas? Red, green, blue, and yellow. Let's consider red. Let's consider the constraints between Texas and all the adjacent states. One of those constraints says it can't be the same color as Arizona.

The only color I've got available for Arizona since I've already made the assignment is red. Red is not consistent with red, so I've got to get rid of it. So, it looks complicated, but it's just intuition. So, what do we do if we get to a situation where the domain is empty? That means whenever we get around to making assignment to it, there won't be anything left. So, if that ever happens, if the domain ever becomes empty, then what do we do? We got to back up. All right. So, the intuition is clear. This is the algorithm. The algorithm when you work through it, think about it, whether it makes sense and whatnot, how it fits with Texas.

Yeah, it sure does. All we're doing is we're making these depth first assignments, and in the neighborhood of those depth first assignments, we're looking around to see if the values that are possible include something, and if they don't include anything, we know we made an irrevocable blunder, and we have to back up. So, that's the essence of the idea. Now, uh how how well does it work? Well, it depends on a little bit depends on uh what we choose for considered. There are lots of choices for what we consider. So, let me enumerate some of those choices, and then we'll work it out on the we'll have a look and see what they do.

Oh, I I guess one possibility is to consider nothing. Let's try it out. So, our type of search is going to be no checks. What do you think's going to happen? We're not even checking the assignment. Well, that's pretty fast. Unfortunately, since we haven't even checked the most recent assignment, we get lots of places where there states that are adjacent to each other that have the same color. Well, that's no good. So, another thing we can do is uh consider every everything. That's no good because that would say as soon as we color our first state, we check to make sure that every other you know, all 47 other states can be colored.

That seems like a overdoing it a little bit. But in any case, at least we want to check the assignment. So, if we go back here and check the assignment, let's see what happens. Uh let's see. Type of assignments assignments only. Boom. Oh, that jeez, that's what that's what I where I got in trouble before. This is the thing that's going to run for a 17 billion years at nanosecond something like that. Oh, it's only a billion years if you run it at nanosecond speed, so I guess maybe you could do that. Have a fast computer. Well, this isn't going to work because of our unfortunate choice of Texas as the as the last state to be considered and the unfortunate coloring of the four surrounding states right up front and our unfortunate decision to rotate the colors so as to avoid overdoing any one color.

So, this doesn't work, but you know, we we went to the trouble of working out the the business with um with Texas by hand using the domain reduction algorithm that are make a note that this is the domain reduction algorithm. And what we're going to do is we're going to check the neighbors of the assignments. Just like we did here. We checked Texas each time we made one of those four choices because it's a neighbor of all of the choices of the states that we made. So, one thing to do is check neighbors. So, this is 1 2 3. Now, let's see what happens. Check neighbors only. Go. Shoot, I don't know.

It's a it's okay with Texas, right? Because it didn't color the states around Texas uh with all of the four color choices. But it's uh still getting in trouble in other places. Uh like all like the states like Missouri, Kentucky, Virginia, Tennessee, states with lots of lots of boundaries. So, I don't know whether this is going to Oh, there it finally worked. Phew, did a lot of went through a lot of effort though. I don't know. For the sake of comparison, we might make a note that it ran into a 9,139 dead ends. So, um but it did do some good. It didn't take uh a length of time longer than the remaining part of the universe.

But if it's a good idea to check the neighbors if we make a change to the neighbors what might that suggest that we do in addition? Well, it might suggest that we make a change to a neighbor that we check its neighbors, too. Make sure they're all right. So, a another choice is to propagate. So, propagate through variables with reduced domains. Let's see how that works. Well, wait a minute. Um must have made a mistake. Let's try that again. Oh. Maybe we better slow it down. All right, gray stuff is showing the limit of the of the propagation. Man, it's a See it 4 second uh 40 is about 10 seconds.

Boom. Not bad. Zero dead ends. And it was a lot faster. I didn't happen to notice how many constraints were checked in the other thing. I think it was around 20,000 or so. This is a lot less. So, this looks like a good idea. But why did they why did they label it number five? Well, because there's something between this and number three. So, number four is through V with D reduced to one value. So, we're not going to propagate through all of the variables who have their which have their domains shrunk a little bit. We're only going to propagate through those that have the greater uh shrinkage all the way down to a single value.

All right. So, let's see how that might work. Anybody want to place any bets on this one? Uh let's see. We checked 2,623 constraints last time. Let's see what happens this time. You you can see that the extent of the gray is less because it's not propagating so far. And as we breathlessly await the answer I see we found our winner. This is does couple of dead ends, but the number of constraint checked is less than 1,000. So, in general with problems like this, you have all of these choices for what you consider. You don't want to consider nothing because then you're not honoring your constraints.

You'll certainly want to consider the things you've just made assignments for because otherwise you'll create a give it you'll construct a solution that violates a constraint. You do want don't want to do everything because that's excessive work. And so, these two Oh, sorry. Checking the neighbors is a good idea, but it's always better in practice blah In practice, inevitably it's the case that it's better to do some propagation through the things that you've changed. How much propagation? It doesn't seem to do much good to propagate through things that are just changed, but it does seem to do some good to propagate through things that have changed and been reduced to a single value.

So, as soon as you get a neighbor of some assignment you just made that has its domain reduced to a single value, then you check its neighbors, too. So, you check the neighbors of the neighbors of the neighbors of the neighbors on and on and on as long as you found a domain being reduced and not only being reduced, but reduced to a single value. All right. So, that's the domain reduction algorithm. I guarantee we're going to give you a problem like that. I know that you don't know how to work those problems yet because this is a little bit abstract and to work these problems in the exam setting, you need to know a little bit about how to keep track of the variable values in remain in the domains and and that sort of thing and and and you'll learn more about that in your recitations and in this mega recitation and So, we could go home except that there are a few little flourishes to deal with here.

Uh and those flourishes um uh those um flourishes include some dirty filthy little secrets. For example, I've chosen as my classroom example to pick on Texas and arrange for this situation to be especially ugly. So, I I could arrange the states in a different way. Uh we have highly constrained states that have a lot of bordering states around them. And we have other states like Maine up there that has only one has only borders on one other state. So. I don't know. Will What do you think? Should we um Should we arrange the states in for our depth-first search in the order of least constrained to most constrained or most constrained to least constrained?

In other words, should we start with Missouri or Tennessee or Kentucky or something like that or should we start with Maine? What do you think? You have a 50% chance of getting it right just by flipping a coin. He thinks we should start with the most constrained first. Do we have a volunteer who wants to suggest that we start with the least constrained first? That's the way I always That's the way I always work on stuff. You know, I work on a book or something, I have uh 500 things to fix. I'll always choose to work on the easiest stuff first so that I can feel like I'm making the list a lot smaller.

Leave the hardest things till last. But we don't have any volunteers who want to want to bet on on that idea, at least constraint first. Okay. Jason wants to suggest that we should work on least constraint first. Well, we have ground truth cuz we can just try it out. I guess we'll stick with our shrinking to one value thing here. But we will reorder things so that we have the um least constraint first. So that we right away we got a color for Maine. Maybe we ought to speed this up a little bit. Okay. Well, that's a good idea. Jason suggested this and we only checked 1,732 constraints and we had 59 dead ends.

So let's try the other way around. And we'll go back to four frames a second. So we're working kind of from the middle of the country out with this one. We're going to deal with Maine, I guess, last. Yeah. Which is better? Too bad. I think it looks like this is better. In fact, let's not be so aggressive with the use of constraint propagation. Let's just check the assignments only. If we go back to an arrangement where we have least constraint first and we'll crank up the speed. Well, actually, we'd have to crank it up pretty big because uh the state states like Missouri, Tennessee, Kentucky, they're going to they're going to be like Texas.

And so we're kind of back to the length of the universe type problem here with the least constraint first and no constraint and and no use of constraints other than to check the the current assignment. So let's uh stop that though and uh check the most constraint first assignments only. I don't know how long is this going to take. That's the dirty little secret. If we had arranged our states from most constraint to least constraint, ordinary depth-first search with none of this stuff we talked about today would work just fine. All right. So, uh it's a little bit like uh like games. Do you use progressive deepening or do you use alpha-beta?

And the answer is both. You use everything you got uh to to to to to deal with the with the problems and uh depending on the problem one or another of the things you incorporate into your approach will work just great, if you're lucky. So now, uh I promised that this is not useful not only for people who want to color maps. God, who wants to do that? We know it can be done with four colors, but it's also uh useful for doing all kinds of resource uh planning problems. So what I want to show you a resource planning problem and I want you to think about while I'm doing it, think about whether it's actually analogous to the map coloring problem.

All right? So here's the deal. You have just landed a summer job with uh JetGreen, a new airline. And JetGreen um is a is a low-cost um no-frills hardly any maintenance type of airline. And they want to fly mostly between Boston and New York. Uh occasionally they want to fly to Los Angeles and they're trying to get by with the smallest number of airplanes. So that's why we have a kind of resource allocation problem. JetGreen. So I'm I'm going to write down what what their schedule looks like. They have one flight, F1, that goes from Boston to Los Ange- to JFK. Like so. It's early in the day flight.

Then they want to have another one, F2, that flies from JFK to Boston. And then they want to have another flight a little later in the day that flies from Boston to JFK. And a little later than that, they want to have another flight that goes from JFK to Boston. They're they're going to start off mostly as a shuttle airline in the beginning. So that's F1, F2, F3, and F4, and they have a fifth flight, F5, that goes from Boston to Los Angeles. That takes a long time. So it looks like this on the on the schedule. Of course, we have time going that way. So that's Boston to LAX. Now your job is to determine if they can fly this schedule with four aircraft.

And naturally, you don't want to over use any one aircraft cuz you'd like to have kind of even even wear on them, right? So as you make your choices, you'll rotate the aircraft. So you'll assign this one to A1, aircraft number one. This one will be A2. This one will be A3. And this one will be A4. And oops, there's no aircraft left for the flight to Los Angeles cuz they only have four. So it's obvious, right? This is 100% exactly the map coloring problem, even down to the four choices. Because you have the constraint that you no single physical aircraft can fly on fly two flights at the same time, just like no two adjacent states can be colored the same.

So there's a no same no same time constraint like so. So if you were assigning flight aircraft to these flights, you get down to F4, the fourth flight, and you'd say, "Well, let's see. This guy down here can be A1, A2, A3, or A4, but if I choose A4 for that fourth flight, then there'd be nothing left in its domain." So you've thus set the problem up to be identical to the to the map coloring problem. And of course, you you can enrich it with other kinds of constraints. So for example, you might have This is a not same time constraint. And these I mean, this is at JFK. It flies out of JFK, so maybe you can use those.

Maybe you can use the same aircraft for those, but not if they're right up against each other because you have a minimum ground time rule. So there's a minimum ground time constraint here. And there's a minimum ground time constraint here. And there's a minimum ground time constraint here. And if these are the same city, then you've got to allow enough time for them to fly between the two cities that are involved. So the constraints can get a little bit more complicated, but the idea is the same. So you say to me, "I don't trust you. Show me." Okay. So let me show you. Oh, by the way, there's one more way to make this map coloring problem easier, right?

Let's see. Uh the arrangement is going to be alphabetical. The type is going to be assignments only. And we know that's a loser, but not if we use a whole lot of colors. So it's the use of four colors that got us into trouble. Oh, that's an aside, but it will be coming back in a moment or two. Scheduling. Here's that problem. Boom. Yep. You can you can almost see it working just like the map coloring thing. But that's maybe too easy. Let's do this one. See, this is just like this is like Simplicia. We we've kind of got a a goofy arrangement here that's guaranteed to lose at the bottom because of choices made at the top.

But that's okay. We can we can stop this and we can do um we can change to a check neighbors only and boom, there it goes. All right. Or alternatively, let me see if I can do it this way. Most constraint first. Type will be assignments only. Boom. That worked fine, too. So you might choose to have a a slightly harder problem, I don't know, like this. And we can uh search away. Actually, I don't know if this will complete or not. This is a randomly generated example. But you you know, you're going to lose your summer job if you can't figure out whether you can do this or not. So, what what are you going to do?

Elliot, you got any thoughts about how you're going to save your job? So, here's the question you've been asked. How many airplanes does JetGreen need? And you decide, well, four seemed to work before, so we'll try four here. And you're not sure if it's going to terminate or not. I mean, in your in your in your lifetime, let alone in your summer job. Elliot, let me give you a hint. Look at the outline. The outline up here on the board. The last item. Yeah, what's that mean? How many What's the maximum number of airplanes we're going to need? Uh suppose we've got five flights. What's the maximum number of airplanes we'd ever need?

Five. What's the minimum number of airplanes we'll need? One. So, let's try let's try it with a small number of airplanes and a large number of airplanes. So, that showed us very fast that we can't do it with one airplane. That showed us very fast we could do it with 10 airplanes. Volunteer? What are we going to do to find the actual number as fast as possible? And at least give our boss a reasonable answer, even if not necessarily the exact number very fast. But this it's easy, right? We're going to start up here with one computer, and we're going to start down here with another computer, and see what happens.

So, let's see if we can do it with nine. Let's see if we can do it with eight. Let's see if we can do it with seven. These take almost zero time, right? Because they're under constrained. Oh, that's good, seven. Let's try six. Actually, let's try two. It loses fast. Let's try three. I don't know, maybe if you let it run long enough, three will work. I doubt it. While we're at it though, we might as well go back here and try with six. Remember seven worked real fast. Oh, jeez. Six That was six, right? Yeah, so let's try it with five. Okay, so it runs real fast with five. It terminates real quick with two.

So, we've got three and four left. So, we can tell our boss a la anytime algorithm that you're not real sure, but you know it's going to be either three or four. And then you got two computers, you can let both run and see if either one terminate. So, you three and four. My guess is that three will eventually give up. But of course, there's another little problem here. We haven't used the most constrained first. If we did that, we might be able to even do it even faster. Actually, I don't think I can make that switch without getting another random assignment, but let's see what happens. Maybe so.

Oh, I already had most constrained first. Okay. So, it didn't it didn't help to actually switch. I got a I got to think I've got a new schedule to work here. So, that's the that's the that's the end of the story. You can do good resource allocation if you do several things all at once. Number one, you always want to use most constrained first. Number two, you want to propagate through domains reduced to a single algorithm. And number three, if you're really trying to figure out what the minimum number of resources needed is, you do this under over business, and you can quickly converge on a narrow range where the search is taking a long time, and be sure that it lies within that narrow narrow range, because when you over resource, it's fast and fast to complete, and when you under resource, it's fast to terminate.

And so, you can kind of just squeeze it right down into a very small range. And that is the end of the story. Enjoy your holiday on Monday. We'll have two classes next week on Wednesday and Friday, as advertised.