WEBVTT X-TIMESTAMP-MAP=LOCAL:00:00:00.000,MPEGTS:900000 00:00:00.000 --> 00:00:04.920 [MUSIC PLAYING] 00:00:18.010 --> 00:00:20.260 BRIAN YU: OK, welcome back everyone to an Introduction 00:00:20.260 --> 00:00:22.290 to Artificial Intelligence with Python. 00:00:22.290 --> 00:00:25.800 And now, so far, we've taken a look at a couple of different types of problems. 00:00:25.800 --> 00:00:27.550 We've seen classical search problems where 00:00:27.550 --> 00:00:29.890 we're trying to get from an initial state to a goal 00:00:29.890 --> 00:00:31.687 by figuring out some optimal path. 00:00:31.687 --> 00:00:35.020 We've taken a look at adversarial search where we have a game-playing agent that 00:00:35.020 --> 00:00:36.462 is trying to make the best move. 00:00:36.462 --> 00:00:38.170 We've seen knowledge-based problems where 00:00:38.170 --> 00:00:41.560 we're trying to use logic and inference to be able to figure out and draw 00:00:41.560 --> 00:00:42.848 some additional conclusions. 00:00:42.848 --> 00:00:45.640 And we've seen some probabilistic models as well where we might not 00:00:45.640 --> 00:00:47.630 have certain information about the world, 00:00:47.630 --> 00:00:50.740 but we want to use the knowledge about probabilities that we do have 00:00:50.740 --> 00:00:52.702 to be able to draw some conclusions. 00:00:52.702 --> 00:00:55.660 Today we're going to turn our attention to another category of problems 00:00:55.660 --> 00:00:58.110 generally known as "optimization problems" 00:00:58.110 --> 00:01:01.060 where optimization is really all about choosing the best 00:01:01.060 --> 00:01:03.610 option from a set of possible options. 00:01:03.610 --> 00:01:05.890 And we've already seen optimization in some contexts, 00:01:05.890 --> 00:01:09.140 like game playing where we're trying to create an AI that chooses the best 00:01:09.140 --> 00:01:10.960 move out of a set of possible moves. 00:01:10.960 --> 00:01:13.270 But what we'll take a look at today is a category 00:01:13.270 --> 00:01:15.910 of types of problems and algorithms to solve them 00:01:15.910 --> 00:01:19.900 that can be used in order to deal with a broader range of potential optimization 00:01:19.900 --> 00:01:20.855 problems. 00:01:20.855 --> 00:01:23.230 And the first of the algorithms that we'll take a look at 00:01:23.230 --> 00:01:25.480 is known as a "local search." 00:01:25.480 --> 00:01:28.345 And local search differs from search algorithms we've seen before 00:01:28.345 --> 00:01:30.970 in the sense that the search algorithms we've looked at so far, 00:01:30.970 --> 00:01:34.640 which are things like breadth-first search or A* search, for example, 00:01:34.640 --> 00:01:37.120 generally maintain a whole bunch of different paths that 00:01:37.120 --> 00:01:40.240 we're simultaneously exploring, and we're looking at a bunch of different 00:01:40.240 --> 00:01:43.090 paths at once trying to find our way to the solution. 00:01:43.090 --> 00:01:44.920 On the other hand, in local search, this is 00:01:44.920 --> 00:01:46.753 going to be a search algorithm that's really 00:01:46.753 --> 00:01:50.440 just going to maintain a single node and looking at a single state, 00:01:50.440 --> 00:01:54.070 and we'll generally run this algorithm by maintaining that single node 00:01:54.070 --> 00:01:56.260 and then moving ourselves to one of the neighboring 00:01:56.260 --> 00:01:58.690 nodes throughout this search process. 00:01:58.690 --> 00:02:01.880 And this is generally useful in contexts not like these problems, 00:02:01.880 --> 00:02:04.630 which we've seen before, like a maze-solving situation where we're 00:02:04.630 --> 00:02:07.240 trying to find our way from the initial state to the goal 00:02:07.240 --> 00:02:08.860 by following some path. 00:02:08.860 --> 00:02:12.490 But local search is most applicable when we really don't care about the path 00:02:12.490 --> 00:02:15.765 at all, and all we care about is what the solution is. 00:02:15.765 --> 00:02:18.640 And in the case of a solving a maze, the solution was always obvious. 00:02:18.640 --> 00:02:20.020 You could point to the solution. 00:02:20.020 --> 00:02:21.610 You know exactly what the goal is. 00:02:21.610 --> 00:02:24.340 And the real question is, what is the path to get there? 00:02:24.340 --> 00:02:26.350 But local search is going to come up in cases 00:02:26.350 --> 00:02:28.660 where figuring out exactly what the solution is, 00:02:28.660 --> 00:02:32.975 exactly what the goal looks like is actually the heart of the challenge. 00:02:32.975 --> 00:02:35.350 And to give an example of one of these kinds of problems, 00:02:35.350 --> 00:02:38.517 we'll consider a scenario where we have two types of buildings, for example, 00:02:38.517 --> 00:02:40.720 and we have houses and hospitals. 00:02:40.720 --> 00:02:43.770 And our goal might be, in a world that's formatted as this grid where 00:02:43.770 --> 00:02:46.270 we have a whole bunch of houses, a house here, a house here, 00:02:46.270 --> 00:02:48.940 two houses over there, maybe we want to try and find 00:02:48.940 --> 00:02:53.800 a way to place two hospitals on this map, so maybe a hospital here 00:02:53.800 --> 00:02:55.330 and a hospital there. 00:02:55.330 --> 00:02:58.330 And the problem now is we want to place two hospitals on the map, 00:02:58.330 --> 00:03:01.150 but we want to do so with some sort of objective. 00:03:01.150 --> 00:03:04.060 And our objective in this case is to try and minimize 00:03:04.060 --> 00:03:07.267 the distance of any of the houses from a hospital. 00:03:07.267 --> 00:03:09.850 So you might imagine, all right, what's the distance from each 00:03:09.850 --> 00:03:11.650 of the houses to their nearest hospital? 00:03:11.650 --> 00:03:14.230 There are a number of ways we could calculate that distance, 00:03:14.230 --> 00:03:16.760 but one way is using a heuristic we've looked at before, 00:03:16.760 --> 00:03:20.290 which is the Manhattan distance, this idea of how many rows and columns would 00:03:20.290 --> 00:03:24.430 you have to move inside of this grid layout in order to get to a hospital, 00:03:24.430 --> 00:03:25.690 for example. 00:03:25.690 --> 00:03:28.000 And it turns out if you take each of these four houses 00:03:28.000 --> 00:03:31.000 and figure out, all right, how close are they to their nearest hospital, 00:03:31.000 --> 00:03:34.250 you get something like this where this house is three away from a hospital. 00:03:34.250 --> 00:03:37.340 This house is six away, and these two houses are each four away. 00:03:37.340 --> 00:03:41.950 And if you add all those numbers up together, you get a total cost of 17, 00:03:41.950 --> 00:03:43.070 for example. 00:03:43.070 --> 00:03:46.570 So for this particular configuration of hospitals, a hospital here 00:03:46.570 --> 00:03:51.100 and a hospital there, that state, we might say, has a cost of 17. 00:03:51.100 --> 00:03:53.050 And the goal of this problem now that we would 00:03:53.050 --> 00:03:55.360 like to apply a search algorithm to figure out 00:03:55.360 --> 00:03:59.650 is, can you solve this problem to find a way to minimize that cost, 00:03:59.650 --> 00:04:03.430 minimize the total amount if you sum up all of the distances from all 00:04:03.430 --> 00:04:05.230 the houses to the nearest hospital? 00:04:05.230 --> 00:04:07.803 How can we minimize that final value? 00:04:07.803 --> 00:04:09.970 And if we think about this problem a little bit more 00:04:09.970 --> 00:04:12.610 abstractly, and abstracting away from this specific problem, 00:04:12.610 --> 00:04:15.070 and thinking more generally about problems like it, 00:04:15.070 --> 00:04:17.980 you can often formulate these problems by thinking about them 00:04:17.980 --> 00:04:20.890 as a state-space landscape, as we'll soon call it. 00:04:20.890 --> 00:04:24.730 Here in this diagram of a state-space landscape, each of these vertical bars 00:04:24.730 --> 00:04:28.310 represents a particular state that our world could be in. 00:04:28.310 --> 00:04:30.520 So for example, each of these vertical bars 00:04:30.520 --> 00:04:34.390 represents a particular configuration of two hospitals. 00:04:34.390 --> 00:04:36.880 And the height of this vertical bar is generally 00:04:36.880 --> 00:04:41.450 going to represent some function of that state, some value of that state. 00:04:41.450 --> 00:04:43.750 So maybe, in this case, the height of the vertical bar 00:04:43.750 --> 00:04:48.280 represents what is the cost of this particular configuration of hospitals 00:04:48.280 --> 00:04:50.090 in terms of, what is the sum total of all 00:04:50.090 --> 00:04:54.520 of the distances from all of the houses to their nearest hospital? 00:04:54.520 --> 00:04:57.550 And generally speaking, when we have a state-space landscape, 00:04:57.550 --> 00:04:59.840 we want to do one of two things. 00:04:59.840 --> 00:05:03.380 We might be trying to maximize the value of this function, 00:05:03.380 --> 00:05:07.480 trying to find a global maximum, so to speak, of this state-space landscape, 00:05:07.480 --> 00:05:11.590 a single state whose value is higher than all of the other states 00:05:11.590 --> 00:05:13.240 that we could possibly choose from. 00:05:13.240 --> 00:05:16.270 And generally, in this case, when we're trying to find a global maximum, 00:05:16.270 --> 00:05:17.978 we'll call the function that we're trying 00:05:17.978 --> 00:05:20.540 to optimize them some "objective function," 00:05:20.540 --> 00:05:23.510 some function that measures for any given state 00:05:23.510 --> 00:05:26.480 how good is that state such that we can take any state, 00:05:26.480 --> 00:05:30.830 pass it into the objective function, and get a value for how good that state is. 00:05:30.830 --> 00:05:32.810 And ultimately, what our goal is is to find 00:05:32.810 --> 00:05:35.960 one of these states that has the highest-possible value 00:05:35.960 --> 00:05:37.870 for that objective function. 00:05:37.870 --> 00:05:40.490 An equivalent but reverse problem is the problem 00:05:40.490 --> 00:05:44.240 of finding a global minimum, some state that has a value after you passed it 00:05:44.240 --> 00:05:47.960 into this function that is lower than all of the other possible values 00:05:47.960 --> 00:05:49.160 that we might choose from. 00:05:49.160 --> 00:05:51.952 And generally speaking, when we're trying to find a global minimum, 00:05:51.952 --> 00:05:54.920 we call the function that we're calculating a "cost function." 00:05:54.920 --> 00:05:57.170 Generally, each state has some sort of cost, 00:05:57.170 --> 00:06:00.248 whether that cost is a monetary cost, or a time cost, 00:06:00.248 --> 00:06:02.040 or, in the case of the houses and hospitals 00:06:02.040 --> 00:06:03.890 we've been looking at just now, a distance 00:06:03.890 --> 00:06:08.180 cost in terms of how far away each of the houses is from a hospital. 00:06:08.180 --> 00:06:11.360 And we're trying to minimize the cost, find the state that has 00:06:11.360 --> 00:06:14.742 the lowest possible value of that cost. 00:06:14.742 --> 00:06:16.700 So these are the general types of ideas that we 00:06:16.700 --> 00:06:19.340 might be trying to go for within a state-space landscape, 00:06:19.340 --> 00:06:23.420 trying to find a global maximum or trying to find a global minimum. 00:06:23.420 --> 00:06:25.250 And how exactly do we do that? 00:06:25.250 --> 00:06:27.350 We'll recall that in local search, we generally 00:06:27.350 --> 00:06:30.320 operate this algorithm by maintaining just a single state, 00:06:30.320 --> 00:06:33.133 just some current state represented inside of some node, 00:06:33.133 --> 00:06:35.300 maybe inside of a data structure where we're keeping 00:06:35.300 --> 00:06:37.487 track of where we are currently. 00:06:37.487 --> 00:06:39.320 And then, ultimately, what we're going to do 00:06:39.320 --> 00:06:42.830 is, from that state, move to one of its neighbor states, 00:06:42.830 --> 00:06:45.320 so in this case represented in this one-dimensional space 00:06:45.320 --> 00:06:48.162 by just the state immediately to the left or to the right of it. 00:06:48.162 --> 00:06:50.120 But for any different problem, you might define 00:06:50.120 --> 00:06:53.293 what it means for there to be a neighbor of a particular state. 00:06:53.293 --> 00:06:56.210 In the case of a hospitals, for example, that we were just looking at, 00:06:56.210 --> 00:07:00.470 a neighbor might be moving one hospital one space to the left, or to the right, 00:07:00.470 --> 00:07:04.610 or up, or down, some state that is close to our current state 00:07:04.610 --> 00:07:06.770 but slightly different and, as a result, might 00:07:06.770 --> 00:07:10.160 have a slightly different value in terms of its objective function 00:07:10.160 --> 00:07:12.900 or in terms of its cost function. 00:07:12.900 --> 00:07:15.410 So this is going to be our general strategy in local search, 00:07:15.410 --> 00:07:18.470 to be able to take a state, maintaining some current node, 00:07:18.470 --> 00:07:21.470 and move where we're looking at in this state-space landscape in order 00:07:21.470 --> 00:07:25.010 to try to find a global maximum or a global minimum somehow. 00:07:25.010 --> 00:07:26.960 And perhaps the simplest of algorithms that we 00:07:26.960 --> 00:07:29.930 could use to implement this idea of local search 00:07:29.930 --> 00:07:32.330 is an algorithm known as "hill climbing." 00:07:32.330 --> 00:07:34.490 And the basic idea of hill climbing is, let's say, 00:07:34.490 --> 00:07:37.732 I'm trying to maximize the value of my state. 00:07:37.732 --> 00:07:39.940 I'm trying to figure out where the global maximum is. 00:07:39.940 --> 00:07:41.900 I'm going to start in the state. 00:07:41.900 --> 00:07:44.300 And generally, what hill climbing is going to do 00:07:44.300 --> 00:07:48.350 is it's going to consider the neighbors of that state, that from this state 00:07:48.350 --> 00:07:49.940 I could go left, or I could go right. 00:07:49.940 --> 00:07:53.190 And this neighbor happens to be higher, and this neighbor happens to be lower. 00:07:53.190 --> 00:07:56.080 And in hill climbing, if I'm trying to maximize the value, 00:07:56.080 --> 00:07:58.280 I'll generally pick the highest one I can. 00:07:58.280 --> 00:08:01.380 Between the state to the left and right of me, this one is higher. 00:08:01.380 --> 00:08:04.913 So I'll go ahead and move myself to consider that state instead. 00:08:04.913 --> 00:08:06.830 And then I'll repeat this process, continually 00:08:06.830 --> 00:08:09.800 looking at all of my neighbors and picking the highest neighbor, 00:08:09.800 --> 00:08:11.717 doing the same thing, looking at my neighbors, 00:08:11.717 --> 00:08:15.200 picking the highest of my neighbors until I get to a point like right here 00:08:15.200 --> 00:08:18.110 where I consider both of my neighbors, and both of my neighbors 00:08:18.110 --> 00:08:20.240 have a lower value than I do. 00:08:20.240 --> 00:08:24.017 This current state has a value that is higher than any of its neighbors. 00:08:24.017 --> 00:08:25.850 And at that point, the algorithm terminates. 00:08:25.850 --> 00:08:29.360 And I can say, all right, here I have now found the solution. 00:08:29.360 --> 00:08:31.730 And the same thing works in exactly the opposite way 00:08:31.730 --> 00:08:33.980 for trying to find a global minimum, but the algorithm 00:08:33.980 --> 00:08:35.289 is fundamentally the same. 00:08:35.289 --> 00:08:38.539 If I'm trying to find a global minimum and, say, my current state starts here, 00:08:38.539 --> 00:08:41.419 I'll continually look at my neighbors, pick the lowest value 00:08:41.419 --> 00:08:44.330 that I possibly can until I eventually, hopefully, 00:08:44.330 --> 00:08:46.880 find that global minimum, a point at which, when 00:08:46.880 --> 00:08:49.760 I look at both of my neighbors, they each have a higher value, 00:08:49.760 --> 00:08:52.910 and I'm trying to minimize the total score, or cost, 00:08:52.910 --> 00:08:58.110 or value that I get as a result of calculating some sort of cost function. 00:08:58.110 --> 00:09:01.363 So we can formulate this graphical idea in terms of pseudocode. 00:09:01.363 --> 00:09:03.780 And the pseudocode for hill climbing might look like this. 00:09:03.780 --> 00:09:07.040 We define some function called "hill climb" that takes as input 00:09:07.040 --> 00:09:08.990 the problem that we're trying to solve. 00:09:08.990 --> 00:09:12.410 And generally, we're going to start in some sort of initial state. 00:09:12.410 --> 00:09:14.360 So I'll start with a variable called "current" 00:09:14.360 --> 00:09:16.370 that is keeping track of my initial state, 00:09:16.370 --> 00:09:19.150 like an initial configuration of hospitals. 00:09:19.150 --> 00:09:21.650 And maybe some problems lend themselves to an initial state, 00:09:21.650 --> 00:09:23.130 some place where you begin. 00:09:23.130 --> 00:09:26.660 In other cases, maybe not, in which case we might just randomly generate 00:09:26.660 --> 00:09:30.320 some initial state just by choosing two locations for hospitals at random, 00:09:30.320 --> 00:09:34.080 for example, and figuring out from there how we might be able to improve. 00:09:34.080 --> 00:09:37.460 But that initial state, we're going to store inside of "current." 00:09:37.460 --> 00:09:40.040 And now here comes our loop, some repetitive process 00:09:40.040 --> 00:09:43.250 we're going to do again and again until the algorithm terminates. 00:09:43.250 --> 00:09:47.150 And what we're going to do is first say, let's figure out all 00:09:47.150 --> 00:09:49.100 of the neighbors of the current state. 00:09:49.100 --> 00:09:52.370 From my state, what are all of the neighboring states for some definition 00:09:52.370 --> 00:09:54.020 of what it means to be a neighbor? 00:09:54.020 --> 00:09:57.770 And I'll go ahead and choose the highest valued of all of those neighbors 00:09:57.770 --> 00:10:00.650 and save it inside of this variable called "neighbor," so keep 00:10:00.650 --> 00:10:02.360 track of the highest-valued neighbor. 00:10:02.360 --> 00:10:05.028 This is in the case where I'm trying to maximize the value. 00:10:05.028 --> 00:10:07.070 In a case where I'm trying to minimize the value, 00:10:07.070 --> 00:10:09.140 you might imagine here you'll pick the neighbor with the lowest 00:10:09.140 --> 00:10:10.070 possible value. 00:10:10.070 --> 00:10:12.830 But these ideas are really fundamentally interchangeable. 00:10:12.830 --> 00:10:15.920 And it's possible, in some cases, there might be multiple neighbors 00:10:15.920 --> 00:10:19.390 that each have an equally high value or an equally low value 00:10:19.390 --> 00:10:20.780 in the minimizing case. 00:10:20.780 --> 00:10:23.363 And in that case, we can just choose randomly from among them. 00:10:23.363 --> 00:10:26.650 Just choose one of them, and save it inside of this variable "neighbor." 00:10:26.650 --> 00:10:29.980 And then the key question to ask is, is this neighbor 00:10:29.980 --> 00:10:32.870 better than my current state? 00:10:32.870 --> 00:10:36.010 And if the neighbor, the best neighbor that I was able to find 00:10:36.010 --> 00:10:39.543 is not better than my current state, well, then the algorithm is over, 00:10:39.543 --> 00:10:41.710 and I'll just go ahead and return the current state. 00:10:41.710 --> 00:10:44.980 If none of my neighbors are better, then I may as well stay where I am 00:10:44.980 --> 00:10:47.710 is the general logic of the hill-climbing algorithm. 00:10:47.710 --> 00:10:49.720 But otherwise, if the neighbor is better, 00:10:49.720 --> 00:10:51.620 then I may as well move to that neighbor. 00:10:51.620 --> 00:10:54.370 So you might imagine setting "current" equal to "neighbor" 00:10:54.370 --> 00:10:56.500 where the general idea is if I'm at a current state 00:10:56.500 --> 00:10:59.792 and I see a neighbor that is better than me, then I'll go ahead and move there. 00:10:59.792 --> 00:11:03.070 And then I'll repeat the process, continually moving to a better neighbor 00:11:03.070 --> 00:11:06.970 until I reach a point at which none of my neighbors are better than I am. 00:11:06.970 --> 00:11:10.810 And at that point, we'd say the algorithm can just terminate there. 00:11:10.810 --> 00:11:12.850 So let's take a look at a real example of this 00:11:12.850 --> 00:11:14.540 with these houses and hospitals. 00:11:14.540 --> 00:11:17.680 So we've seen now that if we put the hospitals in these two locations, 00:11:17.680 --> 00:11:19.540 that has a total cost of 17. 00:11:19.540 --> 00:11:21.250 And now we need to define, if we're going 00:11:21.250 --> 00:11:23.510 to implement this hill-climbing algorithm, 00:11:23.510 --> 00:11:26.920 what it means to take this particular configuration of hospitals, 00:11:26.920 --> 00:11:30.860 this particular state and get a neighbor of that state. 00:11:30.860 --> 00:11:33.520 And a simple definition of "neighbor" might be just let's 00:11:33.520 --> 00:11:37.870 pick one of the hospitals and move it by one square to the left, or right, 00:11:37.870 --> 00:11:39.640 or up, or down, for example. 00:11:39.640 --> 00:11:41.723 And that would mean we have six possible neighbors 00:11:41.723 --> 00:11:43.182 from this particular configuration. 00:11:43.182 --> 00:11:45.310 And we could take this hospital and move it 00:11:45.310 --> 00:11:48.850 to any of these three possible squares, or we take this hospital 00:11:48.850 --> 00:11:51.190 and move it to any of those three possible squares. 00:11:51.190 --> 00:11:53.860 And each of those would generate a neighbor. 00:11:53.860 --> 00:11:55.720 And what I might do is say, all right, here 00:11:55.720 --> 00:11:58.000 is the locations and the distances between each 00:11:58.000 --> 00:12:00.460 of the houses and their nearest hospital. 00:12:00.460 --> 00:12:03.460 Let me consider all of the neighbors and see if any of them 00:12:03.460 --> 00:12:05.690 can do better than a cost of 17. 00:12:05.690 --> 00:12:08.440 And it turns out there are a couple of ways that we could do that, 00:12:08.440 --> 00:12:11.023 and it doesn't matter if we randomly choose among all the ways 00:12:11.023 --> 00:12:11.920 that are the best. 00:12:11.920 --> 00:12:15.280 But one such possible way is by taking a look at this hospital 00:12:15.280 --> 00:12:17.830 here and considering the directions in which it might 00:12:17.830 --> 00:12:20.470 move if we hold this hospital constant. 00:12:20.470 --> 00:12:23.713 If we take this hospital and move it one square up, for example, 00:12:23.713 --> 00:12:24.880 that doesn't really help us. 00:12:24.880 --> 00:12:28.090 It gets closer to the house up here, but it gets further away from the house 00:12:28.090 --> 00:12:30.160 down here, and it doesn't really change anything 00:12:30.160 --> 00:12:32.980 for the two houses along the left-hand side. 00:12:32.980 --> 00:12:36.727 But if we take this hospital on the right and move it one square down, 00:12:36.727 --> 00:12:37.810 it's the opposite problem. 00:12:37.810 --> 00:12:41.320 It gets further away from the house up above, and it gets closer to the house 00:12:41.320 --> 00:12:42.370 down below. 00:12:42.370 --> 00:12:45.850 The real idea, the goal should be to be able to take this hospital 00:12:45.850 --> 00:12:47.950 and move it one square to the left. 00:12:47.950 --> 00:12:49.810 By moving it one square to the left, we move 00:12:49.810 --> 00:12:52.228 it closer to both of these houses on the right 00:12:52.228 --> 00:12:54.520 without changing anything about the houses on the left. 00:12:54.520 --> 00:12:57.940 For them, this hospital is still the closer one, so they aren't affected. 00:12:57.940 --> 00:13:02.020 So we're able to improve the situation by picking a neighbor that results 00:13:02.020 --> 00:13:04.310 in a decrease in our total cost. 00:13:04.310 --> 00:13:07.800 And so we might do that, move ourselves from this current state to a neighbor 00:13:07.800 --> 00:13:10.472 by just taking that hospital and moving it. 00:13:10.472 --> 00:13:12.430 And at this point, there's not a whole lot that 00:13:12.430 --> 00:13:14.472 can be done with this hospital, but there's still 00:13:14.472 --> 00:13:17.620 other optimizations we can make, other neighbors we can move to that 00:13:17.620 --> 00:13:19.090 are going to have a better value. 00:13:19.090 --> 00:13:21.260 If we consider this hospital, for example, 00:13:21.260 --> 00:13:24.910 we might imagine that right now it's a bit far up, that both of these houses 00:13:24.910 --> 00:13:27.340 are a little bit lower, so we might be able to do better 00:13:27.340 --> 00:13:30.280 by taking this hospital and moving it one square down, 00:13:30.280 --> 00:13:34.780 moving it down so that now, instead of a cost of 15, we're down to a cost of 13 00:13:34.780 --> 00:13:36.520 for this particular configuration. 00:13:36.520 --> 00:13:38.860 And we can do even better by taking the hospital 00:13:38.860 --> 00:13:40.790 and moving it one square to the left. 00:13:40.790 --> 00:13:43.510 Now, instead of a cost of 13, we have a cost of 11 00:13:43.510 --> 00:13:46.060 because this house is one away from the hospital. 00:13:46.060 --> 00:13:47.590 This one is four away. 00:13:47.590 --> 00:13:50.650 This one is three away, and this one is also three away. 00:13:50.650 --> 00:13:53.370 So we've been able to do much better than that initial cost 00:13:53.370 --> 00:13:56.050 that we had using the initial configuration just 00:13:56.050 --> 00:13:58.900 by taking every state and asking ourselves the question, 00:13:58.900 --> 00:14:02.097 can we do better by just making small, incremental changes, 00:14:02.097 --> 00:14:04.930 moving to a neighbor, moving to a neighbor, and moving to a neighbor 00:14:04.930 --> 00:14:06.550 after that? 00:14:06.550 --> 00:14:09.970 And now, at this point, we can potentially see that, at this point, 00:14:09.970 --> 00:14:11.470 the algorithm is going to terminate. 00:14:11.470 --> 00:14:14.080 There's actually no neighbor we can move to that is 00:14:14.080 --> 00:14:17.973 going to improve the situation, get us a cost that is less than 11. 00:14:17.973 --> 00:14:20.890 Because if we take this hospital and move it up or to the right, well, 00:14:20.890 --> 00:14:22.480 that's going to make it further away. 00:14:22.480 --> 00:14:25.660 If we take it and move it down, that doesn't really change the situation. 00:14:25.660 --> 00:14:28.570 It gets further away from this house but closer to that house. 00:14:28.570 --> 00:14:31.270 And likewise, the same story was true for this hospital. 00:14:31.270 --> 00:14:34.060 Any neighbor we move it to, up, left, down, or right, 00:14:34.060 --> 00:14:38.110 is either going to make it further away from the houses and increase the cost, 00:14:38.110 --> 00:14:42.280 or it's going to have no effect on the cost whatsoever. 00:14:42.280 --> 00:14:45.550 And so the question we might now ask is, is this the best we could do? 00:14:45.550 --> 00:14:48.970 Is this the best placement of the hospitals we could possibly have? 00:14:48.970 --> 00:14:51.970 And it turns out the answer is "no" because there's a better way that we 00:14:51.970 --> 00:14:53.503 could place these hospitals. 00:14:53.503 --> 00:14:56.170 And in particular, there are a number of ways you could do this. 00:14:56.170 --> 00:14:59.470 But one of the ways is by taking this hospital here and moving it 00:14:59.470 --> 00:15:02.595 to this square, for example, moving it diagonally by one square, 00:15:02.595 --> 00:15:04.720 which was not part of our definition of "neighbor." 00:15:04.720 --> 00:15:06.910 We could only move left, right, up, or down. 00:15:06.910 --> 00:15:08.410 But this is, in fact, better. 00:15:08.410 --> 00:15:09.970 It has a total cost of 9. 00:15:09.970 --> 00:15:12.220 It is now closer to both of these houses. 00:15:12.220 --> 00:15:15.430 And as a result, the total cost is less. 00:15:15.430 --> 00:15:17.370 But we weren't able to find it. 00:15:17.370 --> 00:15:19.280 Because in order to get there, we had to go 00:15:19.280 --> 00:15:23.060 through a state that actually wasn't any better than the current state 00:15:23.060 --> 00:15:24.890 that we had been on previously. 00:15:24.890 --> 00:15:27.590 And so this appears to be a limitation or a concern 00:15:27.590 --> 00:15:29.780 you might have as you go about trying to implement 00:15:29.780 --> 00:15:32.180 a hill-climbing algorithm is that it might not always 00:15:32.180 --> 00:15:34.520 give you the optimal solution. 00:15:34.520 --> 00:15:37.580 If we're trying to maximize the value of any particular state, 00:15:37.580 --> 00:15:40.220 we're trying to find the global maximum, a concern 00:15:40.220 --> 00:15:44.210 might be that we could get stuck at one of the local maxima, 00:15:44.210 --> 00:15:49.070 highlighted here in blue, where a local maxima is any state whose value is 00:15:49.070 --> 00:15:50.570 higher than any of its neighbors. 00:15:50.570 --> 00:15:53.240 If we ever find ourselves at one of these two states 00:15:53.240 --> 00:15:55.620 when we're trying to maximize the value of the state, 00:15:55.620 --> 00:15:57.120 we're not going to make any changes. 00:15:57.120 --> 00:15:58.703 We're not going to move left or right. 00:15:58.703 --> 00:16:01.940 We're not going to move left here because those states are worse. 00:16:01.940 --> 00:16:04.490 But yet we haven't found the global optimum. 00:16:04.490 --> 00:16:06.582 We haven't done as best as we could do. 00:16:06.582 --> 00:16:09.290 And likewise, in the case of the hospitals, what we're ultimately 00:16:09.290 --> 00:16:12.050 trying to do is find a global minimum, find a value 00:16:12.050 --> 00:16:13.930 that is lower than all of the others. 00:16:13.930 --> 00:16:18.050 But we have the potential to get stuck at one of the local minimum, any 00:16:18.050 --> 00:16:21.380 of these states whose value is lower than all of its neighbors 00:16:21.380 --> 00:16:24.890 but still not as low as the local minimum. 00:16:24.890 --> 00:16:28.010 And so the takeaway here is that it's not always 00:16:28.010 --> 00:16:30.290 going to be the case that when we run this naive, 00:16:30.290 --> 00:16:32.012 hill-climbing algorithm that we're always 00:16:32.012 --> 00:16:33.470 going to find the optimal solution. 00:16:33.470 --> 00:16:35.150 There are things that could go wrong. 00:16:35.150 --> 00:16:37.340 If we started here, for example, and tried 00:16:37.340 --> 00:16:39.770 to maximize our value as much as possible, 00:16:39.770 --> 00:16:41.980 we might move to the highest possible neighbor, 00:16:41.980 --> 00:16:45.188 move to the highest possible neighbor, move to the highest possible neighbor, 00:16:45.188 --> 00:16:47.420 and stop, and never realize that there is actually 00:16:47.420 --> 00:16:51.412 a better state way over there that we could have gone to instead. 00:16:51.412 --> 00:16:53.120 And other problems you might imagine just 00:16:53.120 --> 00:16:55.520 by taking a look at this state-space landscape 00:16:55.520 --> 00:16:58.310 are these various different types of plateaus, something 00:16:58.310 --> 00:17:02.210 like this flat local maximum here where all six of these states each 00:17:02.210 --> 00:17:04.140 have the exact same value. 00:17:04.140 --> 00:17:07.849 And so, in the case of the algorithm we showed before, none of the neighbors 00:17:07.849 --> 00:17:10.842 are better, so we might just get stuck at this flat local maximum. 00:17:10.842 --> 00:17:13.550 And even if you allowed yourself to move to one of the neighbors, 00:17:13.550 --> 00:17:16.310 it wouldn't be clear which neighbor you would ultimately move to, 00:17:16.310 --> 00:17:18.402 and you could get stuck here as well. 00:17:18.402 --> 00:17:19.819 And there's another one over here. 00:17:19.819 --> 00:17:21.200 This one is called a "shoulder." 00:17:21.200 --> 00:17:23.150 It's not really a local maximum because there's still 00:17:23.150 --> 00:17:24.560 places where we can go higher-- 00:17:24.560 --> 00:17:26.520 not a local minimum because we can go lower. 00:17:26.520 --> 00:17:28.670 So we can still make progress, but it's still 00:17:28.670 --> 00:17:31.850 this flat area where if you have a local search algorithm, 00:17:31.850 --> 00:17:34.530 there is potential to get lost here, unable to make 00:17:34.530 --> 00:17:37.280 some upward or downward progress depending on whether we're trying 00:17:37.280 --> 00:17:41.240 to maximize or minimize and, therefore, another potential for us 00:17:41.240 --> 00:17:46.210 to be able to find a solution that might not actually be the optimal solution. 00:17:46.210 --> 00:17:48.470 And so because of this potential, the potential 00:17:48.470 --> 00:17:51.710 that hill climbing has to not always find us the optimal result, 00:17:51.710 --> 00:17:54.740 it turns out there are a number of different varieties and variations 00:17:54.740 --> 00:17:58.550 on the hill-climbing algorithm that help to solve the problem better 00:17:58.550 --> 00:17:59.725 depending on the context. 00:17:59.725 --> 00:18:02.600 And depending on the specific type of problem, some of these variants 00:18:02.600 --> 00:18:04.410 might be more applicable than others. 00:18:04.410 --> 00:18:07.670 What we've taken a look at so far is a version of hill climbing generally 00:18:07.670 --> 00:18:12.050 called "steepest-ascent hill climbing" where the idea of steepest-ascent hill 00:18:12.050 --> 00:18:15.885 climbing is we are going to choose the highest-valued neighbor in the case 00:18:15.885 --> 00:18:19.010 where we're trying to maximize or the lowest-valued neighbor in cases where 00:18:19.010 --> 00:18:20.052 we're trying to minimize. 00:18:20.052 --> 00:18:22.340 But generally speaking, if I have five neighbors 00:18:22.340 --> 00:18:24.440 and they're all better than my current state, 00:18:24.440 --> 00:18:26.837 I will pick the best one of those five. 00:18:26.837 --> 00:18:28.670 Now, sometimes, that might work pretty well. 00:18:28.670 --> 00:18:31.045 It's sort of a greedy approach of trying to take the best 00:18:31.045 --> 00:18:33.440 operation at any particular time step. 00:18:33.440 --> 00:18:34.680 But it might not always work. 00:18:34.680 --> 00:18:36.430 There might be cases where actually I want 00:18:36.430 --> 00:18:38.610 to choose an option that is slightly better than me 00:18:38.610 --> 00:18:41.450 but maybe not the best one because that, later on, might 00:18:41.450 --> 00:18:43.250 lead to a better outcome ultimately. 00:18:43.250 --> 00:18:45.530 So there are other variants that we might consider 00:18:45.530 --> 00:18:47.720 of this basic hill-climbing algorithm. 00:18:47.720 --> 00:18:49.760 One is known as "stochastic hill climbing." 00:18:49.760 --> 00:18:52.130 And in this case, we choose randomly from all 00:18:52.130 --> 00:18:53.490 of our higher-valued neighbors. 00:18:53.490 --> 00:18:56.115 So if I'm at my current state and there are five neighbors that 00:18:56.115 --> 00:18:58.460 are all better than I am, rather than choosing the best 00:18:58.460 --> 00:19:02.090 one as steepest ascent would do, stochastic will just choose randomly 00:19:02.090 --> 00:19:05.060 from one of them, thinking that if it's better, then it's better, 00:19:05.060 --> 00:19:07.310 and maybe there's a potential to make forward progress 00:19:07.310 --> 00:19:11.870 even if it is not locally the best option I could possibly choose. 00:19:11.870 --> 00:19:14.150 First-choice hill climbing ends up just choosing 00:19:14.150 --> 00:19:16.320 the very first highest-valued neighbor, but it 00:19:16.320 --> 00:19:18.230 follows behaving on a similar idea. 00:19:18.230 --> 00:19:20.167 Rather than consider all of the neighbors, 00:19:20.167 --> 00:19:23.000 as soon as we find a neighbor that is better than our current state, 00:19:23.000 --> 00:19:25.833 we'll go ahead and move there, so maybe some efficiency improvements 00:19:25.833 --> 00:19:27.560 there and maybe has the potential to find 00:19:27.560 --> 00:19:31.130 a solution that the other strategies weren't able to find. 00:19:31.130 --> 00:19:33.770 And with all of these variants, we still suffer 00:19:33.770 --> 00:19:36.650 from the same potential risk, this risk that we might end up 00:19:36.650 --> 00:19:39.320 at a local minimum or a local maximum. 00:19:39.320 --> 00:19:43.380 And we can reduce that risk by repeating the process multiple times. 00:19:43.380 --> 00:19:46.490 So one variant of hill climbing is random-restart hill 00:19:46.490 --> 00:19:51.150 climbing where the general idea is we'll conduct hill climbing multiple times. 00:19:51.150 --> 00:19:53.900 If we apply a steepest-ascent hill climbing, for example, 00:19:53.900 --> 00:19:56.220 we'll start at some random state, try and figure out 00:19:56.220 --> 00:19:58.970 how to solve the problem, and figure out what is the local maximum 00:19:58.970 --> 00:20:00.620 or local minimum we get to. 00:20:00.620 --> 00:20:02.930 And then we'll just randomly restart and try again, 00:20:02.930 --> 00:20:05.720 choose a new starting configuration, try and figure out 00:20:05.720 --> 00:20:09.067 what the local maximum or minimum is, and do this some number of times. 00:20:09.067 --> 00:20:11.150 And then after we've done it some number of times, 00:20:11.150 --> 00:20:14.680 we can pick the best one out of all of the ones that we've taken a look at. 00:20:14.680 --> 00:20:17.800 So there's another option we have access to as well. 00:20:17.800 --> 00:20:20.590 And then, although I said the generally local search will usually 00:20:20.590 --> 00:20:24.480 just keep track of a single node and then move to one of its neighbors, 00:20:24.480 --> 00:20:27.190 there are variants of hill climbing that are known as "local beam 00:20:27.190 --> 00:20:31.120 searches" where, rather than keep track of just one current best state, 00:20:31.120 --> 00:20:34.570 we're keeping track of k highest-valued neighbors, such 00:20:34.570 --> 00:20:37.540 that rather than starting at one random initial configuration, 00:20:37.540 --> 00:20:39.815 I might start with three, or four, or five, 00:20:39.815 --> 00:20:42.940 randomly generate all the neighbors, and then pick like the three, or four, 00:20:42.940 --> 00:20:46.360 or five best of all of the neighbors that I find and continually 00:20:46.360 --> 00:20:49.330 repeat this process with the idea being that now I 00:20:49.330 --> 00:20:51.850 have more options that I'm considering and more ways 00:20:51.850 --> 00:20:55.510 that I could potentially navigate myself to the optimal solution that 00:20:55.510 --> 00:20:58.370 might exist for a particular problem. 00:20:58.370 --> 00:21:00.550 So let's now take a look at some actual code 00:21:00.550 --> 00:21:03.010 that can implement some of these kinds of ideas, something 00:21:03.010 --> 00:21:06.040 like steepest-ascent hill climbing, for example, for trying 00:21:06.040 --> 00:21:08.460 to solve this hospital problem. 00:21:08.460 --> 00:21:11.320 So I'm going to go ahead and go into my hospital's directory 00:21:11.320 --> 00:21:14.350 where I've actually set up the basic framework for solving 00:21:14.350 --> 00:21:15.408 this type of problem. 00:21:15.408 --> 00:21:17.950 I'll go ahead and go into hospitals.py, and we'll take a look 00:21:17.950 --> 00:21:19.390 at the code we've created here. 00:21:19.390 --> 00:21:23.830 I've defined a class that is going to represent the state space. 00:21:23.830 --> 00:21:27.950 So the space has a height, and a width, and also some number of hospitals. 00:21:27.950 --> 00:21:29.950 So you can configure, how big is your map? 00:21:29.950 --> 00:21:32.230 How many hospitals should go here? 00:21:32.230 --> 00:21:35.813 We have a function for adding a new house to the state space and then 00:21:35.813 --> 00:21:38.980 some functions that are going to get me all of the available spaces for if I 00:21:38.980 --> 00:21:42.070 want to randomly place hospitals in particular locations. 00:21:42.070 --> 00:21:45.430 And here now is the hill-climbing algorithm. 00:21:45.430 --> 00:21:47.980 So what are we going to do in the hill-climbing algorithm? 00:21:47.980 --> 00:21:51.040 Well, we're going to start by randomly initializing 00:21:51.040 --> 00:21:52.540 where the hospitals are going to go. 00:21:52.540 --> 00:21:54.748 We don't know where the hospitals should actually be, 00:21:54.748 --> 00:21:56.560 so let's just randomly place them. 00:21:56.560 --> 00:21:59.980 So here, I'm running a loop for each of the hospitals that I have. 00:21:59.980 --> 00:22:04.630 I'm going to go ahead and add a new hospital at some random location. 00:22:04.630 --> 00:22:06.990 So I basically get all of the available spaces, 00:22:06.990 --> 00:22:09.400 and I randomly choose one of them as where I would 00:22:09.400 --> 00:22:11.910 like to add this particular hospital. 00:22:11.910 --> 00:22:14.660 I have some logging output and generating some images, which we'll 00:22:14.660 --> 00:22:16.430 take a look at a little bit later. 00:22:16.430 --> 00:22:18.470 But here is the key idea. 00:22:18.470 --> 00:22:21.460 So I'm going to just keep repeating this algorithm. 00:22:21.460 --> 00:22:24.460 I could specify a maximum of how many times I want it to run, 00:22:24.460 --> 00:22:28.420 or I could just run it up until it hits a local maximum or a local minimum. 00:22:28.420 --> 00:22:32.140 And now, we'll basically consider all of the hospitals that could potentially 00:22:32.140 --> 00:22:35.170 move, so consider each of the two hospitals or more hospitals 00:22:35.170 --> 00:22:38.590 if there are more than that, and consider all of the places 00:22:38.590 --> 00:22:41.080 where that hospital could move to, some neighbor 00:22:41.080 --> 00:22:45.880 of that hospital that we can move the neighbor to and then see, 00:22:45.880 --> 00:22:49.670 is this going to be better than where we were currently? 00:22:49.670 --> 00:22:51.640 So if it is going to be better, then we'll 00:22:51.640 --> 00:22:55.240 go ahead and update our best neighbor and keep track of this new best 00:22:55.240 --> 00:22:56.742 neighbor that we found. 00:22:56.742 --> 00:22:58.450 And then afterwards, we can ask ourselves 00:22:58.450 --> 00:23:01.150 the question, if best neighbor cost is greater 00:23:01.150 --> 00:23:05.050 than or equal to the cost of the current set of hospitals, meaning 00:23:05.050 --> 00:23:09.410 if the cost of our best neighbor is greater than the current cost, 00:23:09.410 --> 00:23:12.550 meaning our best neighbor is worse than our current state, 00:23:12.550 --> 00:23:14.900 well, then we shouldn't make any changes at all. 00:23:14.900 --> 00:23:18.370 And we should just go ahead and return the current set of hospitals. 00:23:18.370 --> 00:23:20.980 But otherwise, we can update our hospitals 00:23:20.980 --> 00:23:23.447 in order to change them to one of the best neighbors. 00:23:23.447 --> 00:23:25.530 And if there are multiple that are all equivalent, 00:23:25.530 --> 00:23:29.500 I'm here using random.choice to say, go ahead and choose one randomly. 00:23:29.500 --> 00:23:31.827 So this is really just a Python implementation 00:23:31.827 --> 00:23:33.910 of that same idea that we were just talking about, 00:23:33.910 --> 00:23:37.900 this idea of taking a current state, some current set of hospitals, 00:23:37.900 --> 00:23:39.950 generating all of the neighbors, looking at all 00:23:39.950 --> 00:23:43.090 of the ways we could take one hospital and move it one square to the left, 00:23:43.090 --> 00:23:45.280 or right, or up, or down, and then figuring out, 00:23:45.280 --> 00:23:48.130 based on all of that information, which is the best 00:23:48.130 --> 00:23:51.940 neighbor or the set of all the best neighbors, and then choosing from one 00:23:51.940 --> 00:23:53.200 of those. 00:23:53.200 --> 00:23:56.970 And each time, we go ahead and generate an image in order to do that. 00:23:56.970 --> 00:24:00.100 And so now what we're doing is if we look down in the bottom, 00:24:00.100 --> 00:24:04.030 I'm going to randomly generate a space with height 10 and width 20. 00:24:04.030 --> 00:24:07.200 And I'll say, go ahead and put three hospital somewhere in the space. 00:24:07.200 --> 00:24:09.910 I'll randomly generate 15 houses that I just go ahead 00:24:09.910 --> 00:24:11.620 and add in random locations. 00:24:11.620 --> 00:24:14.860 And now I'm going to run this hill-climbing algorithm in order 00:24:14.860 --> 00:24:18.770 to try and figure out where we should place those hospitals. 00:24:18.770 --> 00:24:22.610 So we go ahead and run this program by running "python hospitals." 00:24:22.610 --> 00:24:26.300 And we see that we started-- our initial state had a cost of 72, 00:24:26.300 --> 00:24:28.220 but we were able to continually find neighbors 00:24:28.220 --> 00:24:32.090 that were able to decrease that cost, decrease to 69, 66, 63, 00:24:32.090 --> 00:24:35.330 so on and so forth, all the way down to 53 as the best neighbor 00:24:35.330 --> 00:24:36.940 we were able to ultimately find. 00:24:36.940 --> 00:24:38.690 And we can take a look at what that looked 00:24:38.690 --> 00:24:41.330 like by just opening up these files. 00:24:41.330 --> 00:24:44.450 So here, for example, was the initial configuration. 00:24:44.450 --> 00:24:48.470 We randomly selected a location for each of these 15 different houses 00:24:48.470 --> 00:24:51.110 and then randomly selected locations for 1, 00:24:51.110 --> 00:24:56.060 2, 3 hospitals that were just located somewhere inside of the state space. 00:24:56.060 --> 00:24:58.880 And if you add up all the distances from each of the houses 00:24:58.880 --> 00:25:02.540 to their nearest hospital, you get a total cost of about 72. 00:25:02.540 --> 00:25:04.730 And so now the question is, what neighbors can we 00:25:04.730 --> 00:25:07.310 move to that improve the situation? 00:25:07.310 --> 00:25:09.560 And it looks like the first one the algorithm found 00:25:09.560 --> 00:25:12.990 was by taking this house that was over there on the right 00:25:12.990 --> 00:25:15.070 and just moving it to the left. 00:25:15.070 --> 00:25:16.400 And that probably makes sense. 00:25:16.400 --> 00:25:19.310 Because if you look at the houses in that general area, 00:25:19.310 --> 00:25:21.410 really these five houses look they're probably 00:25:21.410 --> 00:25:24.440 the ones that are going to be closest to this hospital over here. 00:25:24.440 --> 00:25:27.870 Moving it to the left decreases the total distance at least 00:25:27.870 --> 00:25:31.740 to most of these houses, though it does increase that distance for one of them. 00:25:31.740 --> 00:25:34.370 And so we're able to make these improvements to the situation 00:25:34.370 --> 00:25:38.480 by continually finding ways that we can move these hospitals around 00:25:38.480 --> 00:25:43.400 until we eventually settle at this particular state that has a cost of 53. 00:25:43.400 --> 00:25:46.610 Or we figured out a position for each of the hospitals, and now none 00:25:46.610 --> 00:25:48.890 of the neighbors that we can move to are actually 00:25:48.890 --> 00:25:50.810 going to improve the situation. 00:25:50.810 --> 00:25:53.480 We can take this hospital, and this hospital, and that hospital 00:25:53.480 --> 00:25:55.670 and look at each of the neighbors, and none of those 00:25:55.670 --> 00:25:58.595 are going to be better than this particular configuration. 00:25:58.595 --> 00:26:01.220 And again, that's not to say that this is the best we could do. 00:26:01.220 --> 00:26:05.420 There might be some other configuration of hospitals that is a global minimum. 00:26:05.420 --> 00:26:07.520 And this might just be a local minimum, that 00:26:07.520 --> 00:26:10.250 is, the best of all of its neighbors but maybe not 00:26:10.250 --> 00:26:13.075 the best in the entire possible state space. 00:26:13.075 --> 00:26:15.200 And you could search through the entire state space 00:26:15.200 --> 00:26:18.438 by considering all of the possible configurations for hospitals. 00:26:18.438 --> 00:26:20.730 But ultimately, that's going to be very time intensive, 00:26:20.730 --> 00:26:22.700 especially as our state space gets bigger 00:26:22.700 --> 00:26:24.770 and there might be more and more possible states. 00:26:24.770 --> 00:26:27.478 It's going to take quite a long time to look through all of them. 00:26:27.478 --> 00:26:30.320 And so being able to use these sort of local search algorithms 00:26:30.320 --> 00:26:33.800 can often be quite good for trying to find the best solution we can do. 00:26:33.800 --> 00:26:36.650 And especially if we don't care about doing the best possible 00:26:36.650 --> 00:26:38.990 and we just care about doing pretty good and finding 00:26:38.990 --> 00:26:41.360 a pretty good placement of those hospitals, 00:26:41.360 --> 00:26:44.420 then these methods can be particularly powerful. 00:26:44.420 --> 00:26:47.810 But of course, we can try and mitigate some of this concern by instead 00:26:47.810 --> 00:26:51.230 of using hill climbing to use random restart, this idea of 00:26:51.230 --> 00:26:54.950 rather than just hill climb one time, we can hill climb multiple times 00:26:54.950 --> 00:26:58.490 and, say, try hill climbing a whole bunch of times on the exact same map 00:26:58.490 --> 00:27:01.620 and figure out, what is the best one that we've been able to find? 00:27:01.620 --> 00:27:05.630 And so I've here implemented a function for random restart 00:27:05.630 --> 00:27:08.700 that restarts some maximum number of times. 00:27:08.700 --> 00:27:13.090 And what we're going to do is repeat that number of times this process 00:27:13.090 --> 00:27:15.590 of just go ahead and run the hill-climbing algorithm, 00:27:15.590 --> 00:27:19.220 figure out what the cost is of getting from all the houses to the hospitals, 00:27:19.220 --> 00:27:22.860 and then figure out, is this better than we've done so far? 00:27:22.860 --> 00:27:26.330 So I can try this exact same idea where instead of running hill climbing, 00:27:26.330 --> 00:27:28.580 I'll go ahead and run random_restart. 00:27:28.580 --> 00:27:32.550 And I'll randomly restart maybe 20 times, for example. 00:27:32.550 --> 00:27:35.420 And we'll go ahead, and now I'll remove all the images 00:27:35.420 --> 00:27:37.590 and then rerun the program. 00:27:37.590 --> 00:27:40.400 And now we started by finding a original state. 00:27:40.400 --> 00:27:44.180 When we initially ran hill climbing, the best cost we were able to find was 56. 00:27:44.180 --> 00:27:47.238 Each of these iterations is a different iteration 00:27:47.238 --> 00:27:48.530 of the hill-climbing algorithm. 00:27:48.530 --> 00:27:51.560 We're running hill climbing not one time but 20 times here, 00:27:51.560 --> 00:27:55.610 each time going until we find a local minimum, in this case. 00:27:55.610 --> 00:27:58.310 And we look and see each time, did we do better than we 00:27:58.310 --> 00:28:00.320 did the best time we've done so far? 00:28:00.320 --> 00:28:02.295 So we went from 56 to 46. 00:28:02.295 --> 00:28:03.920 This one was greater, so we ignored it. 00:28:03.920 --> 00:28:07.640 This one was 41, which was less, so we went ahead and kept that one. 00:28:07.640 --> 00:28:10.010 And for all of the remaining 16 times that we 00:28:10.010 --> 00:28:12.260 tried to implement hill climbing and we tried 00:28:12.260 --> 00:28:16.310 to run the hill-climbing algorithm, we couldn't do any better than that 41. 00:28:16.310 --> 00:28:19.190 Again, maybe there is a way to do better that we just didn't find, 00:28:19.190 --> 00:28:21.620 but it looks like that way ended up being 00:28:21.620 --> 00:28:23.630 a pretty good solution to the problem. 00:28:23.630 --> 00:28:28.070 That was attempt number 3 starting from counting at zero. 00:28:28.070 --> 00:28:30.920 So we can take a look at that, open up number 3, 00:28:30.920 --> 00:28:34.070 and this was the state that happened to have a cost of 41, 00:28:34.070 --> 00:28:36.590 that after running the hill-climbing algorithm 00:28:36.590 --> 00:28:40.020 on some particular, random initial configuration of hospitals, 00:28:40.020 --> 00:28:42.800 this is what we found was the local minimum in terms 00:28:42.800 --> 00:28:44.240 of trying to minimize the cost. 00:28:44.240 --> 00:28:46.760 And it looks like we did pretty well, that this hospital is 00:28:46.760 --> 00:28:48.143 pretty close to this region. 00:28:48.143 --> 00:28:50.060 This one is pretty close to these houses here. 00:28:50.060 --> 00:28:51.852 This hospital looks about as good as we can 00:28:51.852 --> 00:28:55.020 do for trying to capture those houses over on that side. 00:28:55.020 --> 00:28:58.010 And so these sorts of algorithms can be quite useful for trying 00:28:58.010 --> 00:29:00.380 to solve these problems. 00:29:00.380 --> 00:29:02.990 But the real problem with many of these different types 00:29:02.990 --> 00:29:06.380 of hill climbing, steepest ascents, stochastic, first choice, and so forth 00:29:06.380 --> 00:29:10.060 is that they never make a move that makes our situation worse. 00:29:10.060 --> 00:29:12.560 They're always going to take ourselves in our current state, 00:29:12.560 --> 00:29:15.800 look at the neighbors, and consider, can we do better than our current state, 00:29:15.800 --> 00:29:17.370 and move to one of those neighbors. 00:29:17.370 --> 00:29:19.310 Which of those neighbors we choose might vary 00:29:19.310 --> 00:29:21.440 among these various different types of algorithms, 00:29:21.440 --> 00:29:24.620 but we never go from a current position to a position that 00:29:24.620 --> 00:29:26.382 is worse than our current position. 00:29:26.382 --> 00:29:28.340 And ultimately, that's what we're going to need 00:29:28.340 --> 00:29:32.150 to do if we want to be able to find a global maximum or a global minimum. 00:29:32.150 --> 00:29:34.010 Because sometimes if we get stuck, we want 00:29:34.010 --> 00:29:38.150 to find some way of dislodging ourselves from our local maximum or local minimum 00:29:38.150 --> 00:29:41.210 in order to find the global maximum or the global minimum 00:29:41.210 --> 00:29:43.997 or increase the probability that we do find it. 00:29:43.997 --> 00:29:45.830 And so the most popular technique for trying 00:29:45.830 --> 00:29:48.350 to approach the problem from that angle is a technique 00:29:48.350 --> 00:29:50.530 known as "simulated annealing," simulated 00:29:50.530 --> 00:29:54.320 because it's modeling after a real physical process of annealing where you 00:29:54.320 --> 00:29:57.560 can think about this in terms of physics, a physical situation 00:29:57.560 --> 00:29:59.540 where you have some system of particles. 00:29:59.540 --> 00:30:02.700 And you might imagine that when you heat up a particular physical system, 00:30:02.700 --> 00:30:03.950 there's a lot of energy there. 00:30:03.950 --> 00:30:05.870 Things are moving around quite randomly. 00:30:05.870 --> 00:30:08.840 But over time, as the system cools down, it eventually 00:30:08.840 --> 00:30:11.480 settles into some final position. 00:30:11.480 --> 00:30:14.420 And that's going to be the general idea of simulated annealing. 00:30:14.420 --> 00:30:18.350 We're going to simulate that process of some high-temperature system 00:30:18.350 --> 00:30:21.560 where things are moving around randomly quite frequently but, over time, 00:30:21.560 --> 00:30:24.110 decreasing that temperature until we eventually 00:30:24.110 --> 00:30:26.240 settle at our ultimate solution. 00:30:26.240 --> 00:30:29.480 And the idea is going to be if we have some state-space landscape that 00:30:29.480 --> 00:30:32.830 looks like this and we begin at its initial state 00:30:32.830 --> 00:30:35.720 here, if we're looking for a global maximum 00:30:35.720 --> 00:30:38.150 and we're trying to maximize the value of the state, 00:30:38.150 --> 00:30:41.390 our traditional hill-climbing algorithms would just take the state, 00:30:41.390 --> 00:30:43.550 and look at the two neighbor ones, and always pick 00:30:43.550 --> 00:30:47.180 the one that is going to increase the value of the state. 00:30:47.180 --> 00:30:50.060 But if we want some chance of being able to find the global maximum, 00:30:50.060 --> 00:30:52.730 we can't always make good moves. 00:30:52.730 --> 00:30:55.940 We have to sometimes make bad moves and allow ourselves 00:30:55.940 --> 00:30:59.780 to make a move in a direction that actually seems, for now, to make 00:30:59.780 --> 00:31:03.230 our situation worse such that later we can find our way up 00:31:03.230 --> 00:31:07.368 to that global maximum in terms of trying to solve that problem. 00:31:07.368 --> 00:31:09.410 Of course, once we get up to this global maximum, 00:31:09.410 --> 00:31:11.285 once we've done a whole lot of the searching, 00:31:11.285 --> 00:31:13.550 then we probably don't want to be moving to states 00:31:13.550 --> 00:31:15.290 that are worse than our current state. 00:31:15.290 --> 00:31:17.390 And so this is where this metaphor for annealing 00:31:17.390 --> 00:31:21.240 starts to come in where we want to start making more random moves 00:31:21.240 --> 00:31:24.290 and, over time, start to make fewer of those random moves 00:31:24.290 --> 00:31:27.380 based on a particular temperature schedule. 00:31:27.380 --> 00:31:29.450 So the basic outline looks something like this. 00:31:29.450 --> 00:31:33.710 Early on in simulated annealing, we have a higher temperature state. 00:31:33.710 --> 00:31:36.110 And what we mean by a "higher temperature state" 00:31:36.110 --> 00:31:38.550 is that we are more likely to accept neighbors 00:31:38.550 --> 00:31:41.710 that are worse than our current state, that we might look at our neighbors, 00:31:41.710 --> 00:31:44.210 and if one of our neighbors is worse than the current state, 00:31:44.210 --> 00:31:46.130 especially if it's not all that much worse, 00:31:46.130 --> 00:31:48.380 if it's pretty close but just slightly worse, 00:31:48.380 --> 00:31:51.470 then we might be more likely to accept that and go ahead and move 00:31:51.470 --> 00:31:53.330 to that neighbor anyways. 00:31:53.330 --> 00:31:55.760 But later on as we run simulated annealing, 00:31:55.760 --> 00:31:57.650 we're going to decrease that temperature. 00:31:57.650 --> 00:32:01.460 And at a lower temperature, we're going to be less likely to accept neighbors 00:32:01.460 --> 00:32:03.823 that are worse than our current state. 00:32:03.823 --> 00:32:06.490 Now, to formalize this and put a little bit of pseudocode to it, 00:32:06.490 --> 00:32:08.300 here is what that algorithm might look like. 00:32:08.300 --> 00:32:10.633 And we have a function called "simulated annealing" that 00:32:10.633 --> 00:32:12.730 takes as input the problem we're trying to solve 00:32:12.730 --> 00:32:15.530 and also potentially some maximum number of times 00:32:15.530 --> 00:32:17.583 we might want to run the simulated annealing 00:32:17.583 --> 00:32:20.500 process, how many different neighbors we're going to try and look for. 00:32:20.500 --> 00:32:24.372 And that value is going to vary based on the problem you're trying to solve. 00:32:24.372 --> 00:32:26.080 We'll again start with some current state 00:32:26.080 --> 00:32:28.520 that will be equal to the initial state of the problem. 00:32:28.520 --> 00:32:33.790 But now, we need to repeat this process over and over for max number of times, 00:32:33.790 --> 00:32:37.090 repeat some process some number of times where we're first 00:32:37.090 --> 00:32:39.310 going to calculate a temperature. 00:32:39.310 --> 00:32:42.340 And this temperature function takes the current time t, 00:32:42.340 --> 00:32:44.650 starting at 1 going all the way up to max, 00:32:44.650 --> 00:32:48.580 and then gives us some temperature that we can use in our computation 00:32:48.580 --> 00:32:52.300 where the idea is that this temperature is going to be higher early on, 00:32:52.300 --> 00:32:54.140 and it's going to be lower later on. 00:32:54.140 --> 00:32:57.182 So there are a number of ways this temperature function could often work. 00:32:57.182 --> 00:33:00.670 One of the simplest ways is just to say it is like the proportion of time 00:33:00.670 --> 00:33:01.960 that we still have remaining. 00:33:01.960 --> 00:33:05.260 Out of max units of time, how much time do we have remaining? 00:33:05.260 --> 00:33:07.285 You start off with a lot of that time remaining. 00:33:07.285 --> 00:33:09.160 And as time goes on, the temperature is going 00:33:09.160 --> 00:33:12.130 to decrease because you have less and less of that remaining time still 00:33:12.130 --> 00:33:13.660 available to you. 00:33:13.660 --> 00:33:16.490 So we calculate a temperature for the current time. 00:33:16.490 --> 00:33:19.445 And then we pick a random neighbor of the current state. 00:33:19.445 --> 00:33:22.570 No longer are we going to be picking the best neighbor that we possibly can 00:33:22.570 --> 00:33:24.640 or just one of the better neighbors that we can. 00:33:24.640 --> 00:33:26.050 We're going to pick a random neighbor. 00:33:26.050 --> 00:33:26.710 It might be better. 00:33:26.710 --> 00:33:27.490 It might be worse. 00:33:27.490 --> 00:33:28.907 But we're going to calculate that. 00:33:28.907 --> 00:33:32.200 We're going to calculate delta E, "E" for "energy" in this case, which 00:33:32.200 --> 00:33:36.500 is just, how much better is the neighbor than the current state? 00:33:36.500 --> 00:33:39.040 So if delta E is positive, that means the neighbor 00:33:39.040 --> 00:33:40.570 is better than our current state. 00:33:40.570 --> 00:33:42.970 If delta E is negative, that means the neighbor 00:33:42.970 --> 00:33:45.045 is worse than our current state. 00:33:45.045 --> 00:33:47.420 And so we can then have a condition that looks like this. 00:33:47.420 --> 00:33:50.920 If delta E is greater than 0, that means the neighbor state 00:33:50.920 --> 00:33:53.110 is better than our current state. 00:33:53.110 --> 00:33:55.300 And if ever that situation arises, we'll just 00:33:55.300 --> 00:33:57.730 go ahead and update "current" to be that neighbor. 00:33:57.730 --> 00:33:59.798 Same as before, move where we are currently 00:33:59.798 --> 00:34:02.840 to be the neighbor because the neighbor is better than our current state. 00:34:02.840 --> 00:34:04.420 We'll go ahead and accept that. 00:34:04.420 --> 00:34:07.520 But now the difference is that whereas before we never, 00:34:07.520 --> 00:34:10.360 ever wanted to take a move that made our situation worse, 00:34:10.360 --> 00:34:12.429 now we sometimes want to move, [? go ?] make 00:34:12.429 --> 00:34:15.100 a move that is actually going to make our situation worse. 00:34:15.100 --> 00:34:17.558 Because sometimes we're going to need to dislodge ourselves 00:34:17.558 --> 00:34:20.860 from a local minimum or a local maximum to increase the probability that we're 00:34:20.860 --> 00:34:25.197 able to find the global minimum or the global maximum a little bit later. 00:34:25.197 --> 00:34:26.239 And so how do we do that? 00:34:26.239 --> 00:34:29.409 How do we decide to sometimes accept some state that 00:34:29.409 --> 00:34:30.730 might actually be worse? 00:34:30.730 --> 00:34:34.360 Well, we're going to accept a worse state with some probability. 00:34:34.360 --> 00:34:37.280 And that probability needs to be based on a couple of factors. 00:34:37.280 --> 00:34:41.230 It needs to be based, in part, on the temperature where if the temperature is 00:34:41.230 --> 00:34:44.139 higher, we're more likely to move to a worse neighbor, 00:34:44.139 --> 00:34:45.940 and if the temperature is lower, we're less 00:34:45.940 --> 00:34:47.889 likely to move to a worse neighbor. 00:34:47.889 --> 00:34:50.920 But it also, to some degree, should be based on delta 00:34:50.920 --> 00:34:54.670 E. If the neighbor is much worse than the current state, 00:34:54.670 --> 00:34:57.050 we probably want to be less likely to choose that 00:34:57.050 --> 00:35:00.767 than if the neighbor is just a little bit worse than the current state. 00:35:00.767 --> 00:35:03.350 So again, there are a couple of ways you could calculate this. 00:35:03.350 --> 00:35:05.530 But it turns out one of the most popular is just 00:35:05.530 --> 00:35:10.570 to calculate E to the power of delta E over t where E is just a constant. 00:35:10.570 --> 00:35:14.170 Delta E over t are based on delta E and t here. 00:35:14.170 --> 00:35:17.950 We calculate that value, and that'll be some value between 0 and 1, 00:35:17.950 --> 00:35:21.050 and that is the probability with which we should just say, all right, 00:35:21.050 --> 00:35:22.758 let's go ahead and move to that neighbor. 00:35:22.758 --> 00:35:26.230 And it turns out that if you do the math for this value when delta E is such 00:35:26.230 --> 00:35:29.188 that the neighbor is not that much worse than the current state, that's 00:35:29.188 --> 00:35:32.355 going to be more likely that we're going to go ahead and move to that state. 00:35:32.355 --> 00:35:34.240 And likewise, when the temperature is lower, 00:35:34.240 --> 00:35:38.230 we're going to be less likely to move to that neighboring state as well. 00:35:38.230 --> 00:35:41.070 So now this is the big picture for simulated annealing, 00:35:41.070 --> 00:35:44.230 this process of taking the problem and going ahead and generating 00:35:44.230 --> 00:35:45.100 random neighbors. 00:35:45.100 --> 00:35:48.160 We'll always move to a neighbor if it's better than our current state. 00:35:48.160 --> 00:35:50.740 But even if the neighbor is worse than our current state, 00:35:50.740 --> 00:35:54.850 we'll sometimes move there depending on how much worse it is and also based 00:35:54.850 --> 00:35:56.000 on the temperature. 00:35:56.000 --> 00:35:58.810 And as a result, the hope, the goal of this whole process 00:35:58.810 --> 00:36:02.830 is that as we begin to try and find our way to the local-- the global maximum 00:36:02.830 --> 00:36:05.350 or the global minimum, we can dislodge ourselves 00:36:05.350 --> 00:36:08.230 if we ever get stuck at a local maximum or a local minimum 00:36:08.230 --> 00:36:11.830 in order to eventually make our way to exploring the part of the state space 00:36:11.830 --> 00:36:13.370 that is going to be the best. 00:36:13.370 --> 00:36:15.880 And then as the temperature decreases, eventually we 00:36:15.880 --> 00:36:18.160 settle there without moving around too much 00:36:18.160 --> 00:36:22.730 from what we've found to be the globally best thing that we can do thus far. 00:36:22.730 --> 00:36:24.970 So at the very end, we just return whatever 00:36:24.970 --> 00:36:26.590 the current state happens to be. 00:36:26.590 --> 00:36:28.465 And that is the conclusion of this algorithm. 00:36:28.465 --> 00:36:31.800 And we've been able to figure out what the solution is. 00:36:31.800 --> 00:36:35.200 And these types of algorithms have a lot of different applications. 00:36:35.200 --> 00:36:38.440 Anytime you can take a problem and formulate it as something 00:36:38.440 --> 00:36:41.713 where you can explore a particular configuration and then ask, 00:36:41.713 --> 00:36:44.380 are any of the neighbors better than this current configuration, 00:36:44.380 --> 00:36:46.470 and have some way of measuring that, then there 00:36:46.470 --> 00:36:49.630 is an applicable case for these hill-climbing, simulated-annealing 00:36:49.630 --> 00:36:51.080 types of algorithms. 00:36:51.080 --> 00:36:54.010 So sometimes it can be for facility location-type problems, 00:36:54.010 --> 00:36:55.795 like for when you're trying to plan a city 00:36:55.795 --> 00:36:57.670 and figure out where the hospitals should be. 00:36:57.670 --> 00:37:00.020 But there are definitely other applications as well. 00:37:00.020 --> 00:37:02.410 And one of the most famous problems in computer science 00:37:02.410 --> 00:37:04.440 is the traveling salesman problem. 00:37:04.440 --> 00:37:07.440 Traveling salesman problem generally is formulated like this. 00:37:07.440 --> 00:37:10.560 I have a whole bunch of cities here indicated by these dots. 00:37:10.560 --> 00:37:13.080 And what I'd like to do is find some route 00:37:13.080 --> 00:37:16.800 that takes me through all of the cities and ends up back where I started, 00:37:16.800 --> 00:37:20.160 so some route that starts here, goes through all these cities, 00:37:20.160 --> 00:37:23.280 and ends up back where I originally started. 00:37:23.280 --> 00:37:26.970 And what I might like to do is minimize the total distance 00:37:26.970 --> 00:37:30.180 that I have to travel in order to-- or the total cost of taking 00:37:30.180 --> 00:37:30.987 this entire path. 00:37:30.987 --> 00:37:32.820 And you can imagine this is a problem that's 00:37:32.820 --> 00:37:37.050 very applicable in situations like when delivery companies are 00:37:37.050 --> 00:37:39.660 trying to deliver things to a whole bunch of different houses. 00:37:39.660 --> 00:37:42.240 They want to figure out, how do I get from the warehouse 00:37:42.240 --> 00:37:44.460 to all these various different houses and get back 00:37:44.460 --> 00:37:49.020 again all using as minimal time, and distance, and energy as possible? 00:37:49.020 --> 00:37:52.120 So you might want to try to solve these sorts of problems. 00:37:52.120 --> 00:37:54.990 But it turns out that solving this particular kind of problem 00:37:54.990 --> 00:37:59.343 is very computationally difficult and is a very computationally expensive task 00:37:59.343 --> 00:38:00.510 to be able to figure it out. 00:38:00.510 --> 00:38:03.600 And this falls under the category of what are known as "NP-complete 00:38:03.600 --> 00:38:07.290 problems," problems that there is no known efficient way to try and solve 00:38:07.290 --> 00:38:08.740 these sorts of problems. 00:38:08.740 --> 00:38:11.070 And so what we ultimately have to do is come up 00:38:11.070 --> 00:38:15.840 with some approximation, some ways of trying to find a good solution even 00:38:15.840 --> 00:38:19.170 if we're not going to find the globally best solution that we possibly can, 00:38:19.170 --> 00:38:22.610 at least not in a feasible or tractable amount of time. 00:38:22.610 --> 00:38:25.260 And so what we could do is take the traveling salesman problem, 00:38:25.260 --> 00:38:27.690 and try to formulate it using local search, 00:38:27.690 --> 00:38:29.700 and ask a question like, all right, I can 00:38:29.700 --> 00:38:34.020 pick some state, some configuration, some route between all of these nodes. 00:38:34.020 --> 00:38:37.260 And I can measure the cost of that state, figure out what the distance is. 00:38:37.260 --> 00:38:41.152 And I might now want to try to minimize that cost as much as possible. 00:38:41.152 --> 00:38:43.110 And then the only question now is, what does it 00:38:43.110 --> 00:38:45.172 mean to have a neighbor of this state? 00:38:45.172 --> 00:38:47.130 What does it mean to take this particular route 00:38:47.130 --> 00:38:50.240 and have some neighboring route that is close to it but slightly different 00:38:50.240 --> 00:38:52.672 in such that it might have a different total distance? 00:38:52.672 --> 00:38:54.630 And there are a number of different definitions 00:38:54.630 --> 00:38:58.270 for what a neighbor of a traveling salesman configuration might look like. 00:38:58.270 --> 00:39:00.480 But one way is just to say, a neighbor is 00:39:00.480 --> 00:39:06.420 what happens if we pick two of these edges between nodes and switch them, 00:39:06.420 --> 00:39:07.840 effectively. 00:39:07.840 --> 00:39:10.320 So for example, I might pick these two edges here, 00:39:10.320 --> 00:39:12.690 these two that just happen across-- this node goes here. 00:39:12.690 --> 00:39:14.360 This node goes there-- 00:39:14.360 --> 00:39:15.842 and go ahead and switch them. 00:39:15.842 --> 00:39:17.550 And what that process will generally look 00:39:17.550 --> 00:39:22.290 like is removing both of these edges from the graph, taking this node, 00:39:22.290 --> 00:39:24.870 and connecting it to the node it wasn't connected to, 00:39:24.870 --> 00:39:26.758 so connecting it up here instead. 00:39:26.758 --> 00:39:29.550 We'll need to take these arrows that were originally going this way 00:39:29.550 --> 00:39:32.663 and reverse them, so move them going the other way, and then just fill 00:39:32.663 --> 00:39:35.580 in that last remaining blank, add an arrow that goes in that direction 00:39:35.580 --> 00:39:36.450 instead. 00:39:36.450 --> 00:39:39.590 So by taking two edges and just switching them, 00:39:39.590 --> 00:39:42.690 I have been able to consider one possible neighbor 00:39:42.690 --> 00:39:44.280 of this particular configuration. 00:39:44.280 --> 00:39:46.405 And it looks like this neighbor is actually better. 00:39:46.405 --> 00:39:49.140 It looks like this probably travels a shorter distance in order 00:39:49.140 --> 00:39:53.280 to get through all the cities through this route than the current state did. 00:39:53.280 --> 00:39:55.800 And so you could imagine implementing this idea 00:39:55.800 --> 00:39:58.650 inside of a hill-climbing or simulated-annealing algorithm 00:39:58.650 --> 00:40:02.280 where we repeat this process to try and take a state of this traveling salesman 00:40:02.280 --> 00:40:05.250 problem, look at all of the neighbors, and then move to the neighbors 00:40:05.250 --> 00:40:07.500 if they're better, or maybe even move to the neighbors 00:40:07.500 --> 00:40:11.310 if they're worse until we eventually settle upon some best solution 00:40:11.310 --> 00:40:12.897 that we've been able to find. 00:40:12.897 --> 00:40:15.480 And it turns out that these types of approximation algorithms, 00:40:15.480 --> 00:40:18.030 even if they don't always find the very best solution, 00:40:18.030 --> 00:40:23.340 can often do pretty well at trying to find solutions that are helpful too. 00:40:23.340 --> 00:40:27.345 So that then was a look at local search, a particular category of algorithms 00:40:27.345 --> 00:40:29.970 that can be used for solving a particular type of problem where 00:40:29.970 --> 00:40:32.470 we don't really care about the path to the solution. 00:40:32.470 --> 00:40:35.940 I didn't care about the steps I took to decide where the hospitals should go. 00:40:35.940 --> 00:40:37.800 I just cared about the solution itself. 00:40:37.800 --> 00:40:40.230 I just care about where the hospitals should be 00:40:40.230 --> 00:40:44.730 or what the route through the traveling salesman journey really ought to be. 00:40:44.730 --> 00:40:46.920 Another type of algorithm that might come up 00:40:46.920 --> 00:40:50.310 are known as these categories of linear-programming types of problems. 00:40:50.310 --> 00:40:52.830 And linear programming often comes up in the context 00:40:52.830 --> 00:40:56.130 where we're trying to optimize for some mathematical function. 00:40:56.130 --> 00:40:58.830 But oftentimes, linear programming will come up 00:40:58.830 --> 00:41:01.590 when we might have real real numbered values so that it's not 00:41:01.590 --> 00:41:04.270 just like discrete, fixed values that we might have 00:41:04.270 --> 00:41:07.330 but any decimal values that we might want to be able to calculate. 00:41:07.330 --> 00:41:09.870 And so linear programming is a family of types 00:41:09.870 --> 00:41:12.510 of problems where we might have a situation that 00:41:12.510 --> 00:41:15.360 looks like this where the goal of linear programming 00:41:15.360 --> 00:41:17.708 is to minimize a cost function. 00:41:17.708 --> 00:41:20.250 And you can invert the numbers and, say, try and maximize it, 00:41:20.250 --> 00:41:23.730 but often we'll frame it as trying to minimize the cost function that 00:41:23.730 --> 00:41:26.970 has some number of variables, x1, x2, x3, 00:41:26.970 --> 00:41:30.000 all the way up to xn, just some number of variables that are involved, 00:41:30.000 --> 00:41:32.490 things that I want to know the values to. 00:41:32.490 --> 00:41:34.710 And this cost function might have coefficients 00:41:34.710 --> 00:41:36.180 in front of those variables. 00:41:36.180 --> 00:41:39.090 And this is what we would call a "linear equation" where we just 00:41:39.090 --> 00:41:42.150 have all of these variables that might be multiplied by a coefficient 00:41:42.150 --> 00:41:43.200 and then added together. 00:41:43.200 --> 00:41:45.060 We're not going to square anything or cube anything 00:41:45.060 --> 00:41:47.268 because that'll give us different types of equations. 00:41:47.268 --> 00:41:49.200 With linear programming, we're just dealing 00:41:49.200 --> 00:41:53.670 with linear equations in addition to linear constraints where 00:41:53.670 --> 00:41:57.000 a constraint is going to look something like if we sum up 00:41:57.000 --> 00:42:00.390 this particular equation that is just some linear combination of all 00:42:00.390 --> 00:42:04.662 of these variables, it is less than or equal to some bound b. 00:42:04.662 --> 00:42:07.620 And we might have a whole number of these various different constraints 00:42:07.620 --> 00:42:12.285 that we might place onto our linear programming exercise. 00:42:12.285 --> 00:42:14.160 And likewise, just as we can have constraints 00:42:14.160 --> 00:42:18.360 that are saying this linear equation is less than or equal to some bound b, 00:42:18.360 --> 00:42:19.990 it might also be equal to something. 00:42:19.990 --> 00:42:22.590 But if you want some sum of some combination of variables 00:42:22.590 --> 00:42:25.290 to be equal to a value, you can specify that. 00:42:25.290 --> 00:42:28.925 And we can also maybe specify that each variable has lower and upper balance, 00:42:28.925 --> 00:42:31.050 that it needs to be a positive number, for example, 00:42:31.050 --> 00:42:33.892 or it needs to be a number that is less than 50, for example. 00:42:33.892 --> 00:42:35.850 And there are a number of other choices that we 00:42:35.850 --> 00:42:39.120 can make there for defining what the bounds of a variable are. 00:42:39.120 --> 00:42:41.400 But it turns out that if you can take a problem 00:42:41.400 --> 00:42:44.610 and formulate it in these terms, formulate the problem 00:42:44.610 --> 00:42:47.760 as your goal is to minimize a cost function, 00:42:47.760 --> 00:42:51.660 and you're minimizing that cost function subject to particular constraints, 00:42:51.660 --> 00:42:54.180 subjects to equations that are of the form like this, 00:42:54.180 --> 00:42:57.030 of some sequence of variables is less than a bound 00:42:57.030 --> 00:42:59.670 or is equal to some particular value, then 00:42:59.670 --> 00:43:02.220 there are a number of algorithms that already exist 00:43:02.220 --> 00:43:05.260 for solving these sorts of problems. 00:43:05.260 --> 00:43:07.558 So let's go ahead and take a look at an example. 00:43:07.558 --> 00:43:09.600 Here's an example of a problem that might come up 00:43:09.600 --> 00:43:11.070 in the world of linear programming. 00:43:11.070 --> 00:43:14.602 Often, this is going to come up when we're trying to optimize for something, 00:43:14.602 --> 00:43:16.560 and we want to be able to do some calculations, 00:43:16.560 --> 00:43:19.050 and we have constraints on what we're trying to optimize. 00:43:19.050 --> 00:43:20.970 And so it might be something like this. 00:43:20.970 --> 00:43:25.130 In the context of a factory, we have 2 machines, x1 and x2. 00:43:25.130 --> 00:43:27.650 x1 costs $50 an hour to run. 00:43:27.650 --> 00:43:30.060 x2 costs $80 an hour to run. 00:43:30.060 --> 00:43:33.150 And our goal, what we're trying to do, our objective 00:43:33.150 --> 00:43:36.062 is to minimize the total cost. 00:43:36.062 --> 00:43:37.870 So that's what we'd like to do. 00:43:37.870 --> 00:43:40.770 But we need to do so subject to certain constraints. 00:43:40.770 --> 00:43:42.840 So there might be a labor constraint that X1 00:43:42.840 --> 00:43:45.190 requires 5 units of labor per hour. 00:43:45.190 --> 00:43:48.150 x2 requires 2 units of labor per hour, and we 00:43:48.150 --> 00:43:51.180 have a total of 20 units of labor that we have to spend. 00:43:51.180 --> 00:43:52.230 So this is a constraint. 00:43:52.230 --> 00:43:56.010 We have no more than 20 units of labor that we can spend, 00:43:56.010 --> 00:43:59.340 and we have to [INAUDIBLE] spend it across x1 and x2, each of which 00:43:59.340 --> 00:44:02.070 requires a different amount of labor. 00:44:02.070 --> 00:44:04.320 And we might also have a constraint like this 00:44:04.320 --> 00:44:07.980 that tells us x1 is going to produce 10 units of output per hour. 00:44:07.980 --> 00:44:11.010 x2 is going to produce 12 units of output per hour. 00:44:11.010 --> 00:44:13.835 And the company needs 90 units of output. 00:44:13.835 --> 00:44:15.960 So we have some goal, something we need to achieve. 00:44:15.960 --> 00:44:19.440 We need to achieve 90 units of output, but there are some constraints 00:44:19.440 --> 00:44:22.260 that x1 can only produce 10 units of output per hour. 00:44:22.260 --> 00:44:25.230 x2 produces 12 units of output per hour. 00:44:25.230 --> 00:44:27.850 These types of problems come up quite frequently. 00:44:27.850 --> 00:44:31.560 And you can start to notice patterns in these types of problems, problems where 00:44:31.560 --> 00:44:35.130 I am trying to optimize for some goal, minimizing cost, maximizing 00:44:35.130 --> 00:44:38.080 output, maximizing profits, or something like that. 00:44:38.080 --> 00:44:41.350 And there are constraints that are placed on that process. 00:44:41.350 --> 00:44:43.740 And so now we just need to formulate this problem 00:44:43.740 --> 00:44:45.887 in terms of linear equations. 00:44:45.887 --> 00:44:47.595 And so let's start with this first point. 00:44:47.595 --> 00:44:52.950 Two machines, x1 and x2, x costs $50 an hour. x2 costs $80 an hour. 00:44:52.950 --> 00:44:56.490 Here we can come up with an objective function that might look like this. 00:44:56.490 --> 00:44:58.460 This is our cost function, rather-- 00:44:58.460 --> 00:45:02.370 50 times x1 plus 80 times x2 where x1 is going 00:45:02.370 --> 00:45:06.750 to be a variable representing how many hours we run machine x1 for. 00:45:06.750 --> 00:45:09.550 x2 is going to be a variable representing how many hours 00:45:09.550 --> 00:45:11.490 are we running machine x2 for. 00:45:11.490 --> 00:45:14.890 And what we're trying to minimize is this cost function, 00:45:14.890 --> 00:45:18.120 which is just how much it costs to run each of these machines per hour 00:45:18.120 --> 00:45:18.940 summed up. 00:45:18.940 --> 00:45:22.290 This is an example of a linear equation, just some combination 00:45:22.290 --> 00:45:25.560 of these variables plus coefficients that are placed in front of them. 00:45:25.560 --> 00:45:28.220 And I would like to minimize that total value, 00:45:28.220 --> 00:45:31.600 but I need to do so subject to these constraints-- 00:45:31.600 --> 00:45:35.390 x1 requires 50 units of labor per hour, x2 requires two, 00:45:35.390 --> 00:45:38.090 and we have a total of 20 units of labor to spend. 00:45:38.090 --> 00:45:41.380 And so that gives us a constraint of this form-- 00:45:41.380 --> 00:45:45.785 5 times x1 plus 2 times x2 is less than or equal to 20. 00:45:45.785 --> 00:45:48.960 20 is the total number of units of labor we have to spend. 00:45:48.960 --> 00:45:51.800 And that's spent across x1 and x2, each of which 00:45:51.800 --> 00:45:56.400 requires a different number of units of labor per hour, for example. 00:45:56.400 --> 00:45:58.400 And finally, we have this constraint here. 00:45:58.400 --> 00:46:02.030 x1 produces 10 units of output per hour, and x2 produces 12, 00:46:02.030 --> 00:46:04.730 and we need 90 units of output. 00:46:04.730 --> 00:46:09.215 And so this might look something like this, that 10x 1 plus 12x 2, 00:46:09.215 --> 00:46:11.270 this is amount of output per hour. 00:46:11.270 --> 00:46:13.130 It needs to be at least 90. 00:46:13.130 --> 00:46:16.430 If we can do better, great, but it needs to be at least 90. 00:46:16.430 --> 00:46:18.620 And if you recall from my formulation before, I 00:46:18.620 --> 00:46:20.930 said that generally speaking in linear programming, 00:46:20.930 --> 00:46:24.710 we deal with equals constraints or less-than or equal-to constraints. 00:46:24.710 --> 00:46:26.720 So we have a greater-than or equal-to sign here. 00:46:26.720 --> 00:46:27.500 That's not a problem. 00:46:27.500 --> 00:46:29.420 Whenever we have a greater-than or equal-to sign, 00:46:29.420 --> 00:46:31.420 we can just multiply the equation by negative 1, 00:46:31.420 --> 00:46:35.240 and that will flip it around to a less than or equals negative 90, 00:46:35.240 --> 00:46:38.528 for example, instead of a greater than or equal to 90. 00:46:38.528 --> 00:46:40.820 And that's going to be an equivalent expression that we 00:46:40.820 --> 00:46:43.110 can use to represent this problem. 00:46:43.110 --> 00:46:47.000 So now that we have this cost function and these constraints 00:46:47.000 --> 00:46:48.950 that it's subject to, it turns out there are 00:46:48.950 --> 00:46:52.280 a number of algorithms that can be used in order to solve 00:46:52.280 --> 00:46:53.340 these types of problems. 00:46:53.340 --> 00:46:56.510 And these problems go a little bit more into geometry and linear algebra 00:46:56.510 --> 00:46:58.010 than we're really going to get into. 00:46:58.010 --> 00:47:00.860 But the most com-- popular of these types of algorithms 00:47:00.860 --> 00:47:03.830 are simplex, which was one of the first algorithms discovered 00:47:03.830 --> 00:47:05.930 for trying to solve linear programs. 00:47:05.930 --> 00:47:08.870 And later on, a class of interior-point algorithms 00:47:08.870 --> 00:47:11.420 can be used to solve this type of problem as well. 00:47:11.420 --> 00:47:14.300 The key is not to understand exactly how these algorithms work 00:47:14.300 --> 00:47:18.260 but to realize that these algorithms exist for efficiently finding solutions 00:47:18.260 --> 00:47:21.690 anytime we have a problem of this particular form. 00:47:21.690 --> 00:47:28.790 And so we can take a look, for example, at the production directory 00:47:28.790 --> 00:47:34.140 here where here we have a file called production.py 00:47:34.140 --> 00:47:36.500 where here I'm using scipy, which is just 00:47:36.500 --> 00:47:40.200 a library for a lot of science-related functions within Python. 00:47:40.200 --> 00:47:43.950 And I can go ahead and just run this optimization function 00:47:43.950 --> 00:47:45.860 in order to run a linear program. 00:47:45.860 --> 00:47:49.590 .linprog here is going to try and solve this linear program for me where I 00:47:49.590 --> 00:47:54.150 provide to this expression, to this function call all of the data about 00:47:54.150 --> 00:47:55.020 my linear program. 00:47:55.020 --> 00:47:56.978 So it needs to be in a particular format, which 00:47:56.978 --> 00:47:59.610 might be a little confusing at first, but this first argument 00:47:59.610 --> 00:48:04.120 to scipy.optimize.linprog is the cost function, 00:48:04.120 --> 00:48:06.090 which is, in this case, just an array or a list 00:48:06.090 --> 00:48:09.450 that has 50 and 80 because my original cost function was 00:48:09.450 --> 00:48:12.480 50 times x1 plus 80 times x2. 00:48:12.480 --> 00:48:16.230 So I just tell Python, 50 and 80, those are the coefficients 00:48:16.230 --> 00:48:19.140 that I am now trying to optimize for. 00:48:19.140 --> 00:48:22.140 And then I provide all of the constraints. 00:48:22.140 --> 00:48:24.780 So the constraints-- and I wrote them up above in comments-- 00:48:24.780 --> 00:48:30.440 is the constraint 1 is 5x_1 plus 2x_2 is less than or equal to 20. 00:48:30.440 --> 00:48:36.330 And constraint 2 is negative 10x_1 plus negative 12x_2 is less than 00:48:36.330 --> 00:48:38.310 or equal to negative 90. 00:48:38.310 --> 00:48:42.630 And so scipy expects these constraints to be in a particular format. 00:48:42.630 --> 00:48:45.870 It first expects me to provide all of the coefficients 00:48:45.870 --> 00:48:49.650 for the upper-bound equations. "ub" is just for "upper bound" 00:48:49.650 --> 00:48:52.610 where the coefficients of the first equation are 5 and 2 00:48:52.610 --> 00:48:55.170 because we have 5x_1 and 2x_2. 00:48:55.170 --> 00:48:57.330 And the coefficients for the second equation 00:48:57.330 --> 00:49:00.060 are negative 10 and negative 12 because I have 00:49:00.060 --> 00:49:03.750 negative 10x_1 plus negative 12x_2. 00:49:03.750 --> 00:49:06.060 And then here we provide it as a separate argument 00:49:06.060 --> 00:49:08.730 just to keep things separate what the actual bound is. 00:49:08.730 --> 00:49:11.370 What is the upper bound for each of these constraints? 00:49:11.370 --> 00:49:13.750 Well, for the first constraint, the upper bound is 20. 00:49:13.750 --> 00:49:15.430 That was constraint number 1. 00:49:15.430 --> 00:49:19.510 And then for constraint number 2, the upper bound is 90. 00:49:19.510 --> 00:49:21.450 So a bit of a cryptic way of representing it. 00:49:21.450 --> 00:49:24.870 It's not quite as simple as just writing the mathematical equations. 00:49:24.870 --> 00:49:27.990 What really is being expected here are all of the coefficients 00:49:27.990 --> 00:49:30.210 and all of the numbers that are in these equations 00:49:30.210 --> 00:49:33.330 by first providing the coefficients for the cost function, 00:49:33.330 --> 00:49:37.080 then providing all the coefficients for the inequality constraints, 00:49:37.080 --> 00:49:40.620 and then providing all of the upper bounds for those inequality 00:49:40.620 --> 00:49:41.760 constraints. 00:49:41.760 --> 00:49:44.170 And once all of that information is there, 00:49:44.170 --> 00:49:46.870 then we can run any of these interior-point algorithms 00:49:46.870 --> 00:49:48.270 or the simplex algorithm. 00:49:48.270 --> 00:49:52.050 Even if you don't understand how it works, you can just run the function 00:49:52.050 --> 00:49:53.850 and figure out what the result should be. 00:49:53.850 --> 00:49:55.740 And here, I said, if the result is a success, 00:49:55.740 --> 00:49:59.640 we were able to solve this problem, go ahead and print out 00:49:59.640 --> 00:50:01.830 what the value of x1 and x2 should be. 00:50:01.830 --> 00:50:04.550 Otherwise, go ahead and print out no solution. 00:50:04.550 --> 00:50:10.980 And so if I run this program by running python production.py, 00:50:10.980 --> 00:50:12.630 it takes a second to calculate. 00:50:12.630 --> 00:50:15.700 But then we see here is what the optimal solution should be. 00:50:15.700 --> 00:50:18.150 x1 should run for 1.5 hours. 00:50:18.150 --> 00:50:21.270 x2 should run for 6.25 hours. 00:50:21.270 --> 00:50:23.430 And we were able to do this by just formulating 00:50:23.430 --> 00:50:26.580 the problem as a linear equation that we were 00:50:26.580 --> 00:50:29.400 trying to optimize, some cost that we were trying to minimize, 00:50:29.400 --> 00:50:31.610 and then some constraints that were placed on that. 00:50:31.610 --> 00:50:34.770 And many, many problems fall into this category of problems 00:50:34.770 --> 00:50:36.990 that you can solve if you can just figure out 00:50:36.990 --> 00:50:41.280 how to use equations and use these constraints to represent 00:50:41.280 --> 00:50:42.030 that general idea. 00:50:42.030 --> 00:50:44.530 And that's a theme that's going to come up a couple of times 00:50:44.530 --> 00:50:46.800 today where we want to be able to take some problem, 00:50:46.800 --> 00:50:50.250 and reduce it down to some problem we know how to solve in order 00:50:50.250 --> 00:50:54.450 to begin to find a solution, and to use existing methods that we 00:50:54.450 --> 00:50:59.440 can use in order to find the solution more effectively or more efficiently. 00:50:59.440 --> 00:51:02.580 And it turns out that these types of problems where we have constraints 00:51:02.580 --> 00:51:04.072 show up in other ways too. 00:51:04.072 --> 00:51:06.030 And there is an entire class of problems that's 00:51:06.030 --> 00:51:09.697 more generally just known as "constraint satisfaction" problems. 00:51:09.697 --> 00:51:12.780 And we're going to now take a look at how you might formulate a constraint 00:51:12.780 --> 00:51:15.810 satisfaction problem and how you might go about solving a constraint 00:51:15.810 --> 00:51:17.190 satisfaction problem. 00:51:17.190 --> 00:51:20.100 But the basic idea of a constraint satisfaction problem 00:51:20.100 --> 00:51:23.702 is we have some number of variables that need to take on some values. 00:51:23.702 --> 00:51:26.910 And we need to figure out what values each of those variables should take on. 00:51:26.910 --> 00:51:30.450 But those variables are subject to particular constraints 00:51:30.450 --> 00:51:34.650 that are going to limit what values those variables can actually take on. 00:51:34.650 --> 00:51:37.710 So let's take a look at a real-world example, for example. 00:51:37.710 --> 00:51:40.590 Let's look at exam scheduling, that I have four students here, 00:51:40.590 --> 00:51:42.660 students 1, 2, 3, and 4. 00:51:42.660 --> 00:51:45.150 Each of them is taking some number of different classes. 00:51:45.150 --> 00:51:47.640 Classes here are going to be represented by letters. 00:51:47.640 --> 00:51:50.580 So student 1 is enrolled in courses A, B, 00:51:50.580 --> 00:51:55.560 and C. Student 2 is enrolled in courses B, D, and E, so on and so forth. 00:51:55.560 --> 00:51:59.550 And now, say, university, for example, is trying to schedule exams 00:51:59.550 --> 00:52:01.260 for all of these courses. 00:52:01.260 --> 00:52:05.160 But there are only three exam slots on Monday, Tuesday and Wednesday. 00:52:05.160 --> 00:52:08.460 And we have to schedule an exam for each of these courses. 00:52:08.460 --> 00:52:12.180 But the constraint now, the constraint we have to deal with the scheduling 00:52:12.180 --> 00:52:16.350 is that we don't want anyone to have to take two exams on the same day. 00:52:16.350 --> 00:52:20.740 We would like to try and minimize that or eliminate it if at all possible. 00:52:20.740 --> 00:52:22.920 So how do we begin to represent this idea? 00:52:22.920 --> 00:52:27.120 How do we structure this in a way that a computer with an AI algorithm 00:52:27.120 --> 00:52:28.980 can begin to try and solve the problem? 00:52:28.980 --> 00:52:31.520 Well, let's in particular just look at these classes 00:52:31.520 --> 00:52:34.450 that we might take and represent each of the courses 00:52:34.450 --> 00:52:37.200 as some node inside of a graph. 00:52:37.200 --> 00:52:40.760 And what we'll do is we'll create an edge between two nodes in this graph 00:52:40.760 --> 00:52:45.550 if there is a constraint between those two nodes. 00:52:45.550 --> 00:52:46.590 So what does this mean? 00:52:46.590 --> 00:52:48.590 Well, we can start with student 1 who's enrolled 00:52:48.590 --> 00:52:53.420 in courses A, B, and C. What that means is that A and B can't 00:52:53.420 --> 00:52:54.740 have an exam at the same time. 00:52:54.740 --> 00:52:57.470 A and C can't have an exam at the same time. 00:52:57.470 --> 00:53:00.320 And B and C also can't have an exam at the same time. 00:53:00.320 --> 00:53:03.380 And I can represent that in this graph by just drawing edges, 00:53:03.380 --> 00:53:08.000 one edge between A and B, one between B and C, and then one between C and A. 00:53:08.000 --> 00:53:11.330 And that encodes now the idea that between those nodes 00:53:11.330 --> 00:53:12.682 there is a constraint. 00:53:12.682 --> 00:53:14.390 And in particular, the constraint happens 00:53:14.390 --> 00:53:16.637 to be that these two can't be equal to each other. 00:53:16.637 --> 00:53:18.470 So there are other types of constraints that 00:53:18.470 --> 00:53:22.182 are possible depending on the type of problem you're trying to solve. 00:53:22.182 --> 00:53:24.890 And then we can do the same thing for each of the other students, 00:53:24.890 --> 00:53:28.250 that for student 2 who's enrolled in courses B, D, and E, well, 00:53:28.250 --> 00:53:30.560 that means B, D, and E, those all need to have 00:53:30.560 --> 00:53:32.420 edges that connect each other as well. 00:53:32.420 --> 00:53:35.180 Student 3 is enrolled in courses C, E, and F. 00:53:35.180 --> 00:53:37.830 So we'll go ahead and take C, E, and F and connect those 00:53:37.830 --> 00:53:39.830 by drawing edges between them too. 00:53:39.830 --> 00:53:43.430 And then, finally, student 4 is enrolled in courses E, F, and G. 00:53:43.430 --> 00:53:46.537 And we can represent that by drawing edges between E, F, and G 00:53:46.537 --> 00:53:48.620 although E and F already had an edge between them. 00:53:48.620 --> 00:53:52.250 We don't need another one because this constraint is just encoding the idea 00:53:52.250 --> 00:53:56.840 that course E and course F cannot have an exam on the same day. 00:53:56.840 --> 00:54:00.560 So this then is what we might call the "constraint graph." 00:54:00.560 --> 00:54:05.180 There's some graphical representation of all of my variables, so to speak, 00:54:05.180 --> 00:54:08.330 and the constraints between those possible variables where, 00:54:08.330 --> 00:54:12.380 in this particular case, each of the constraints represents an inequality 00:54:12.380 --> 00:54:16.310 constraint, that an edge between B and D means whatever value the variable B 00:54:16.310 --> 00:54:21.530 takes on cannot be the value that the variable D takes on as well. 00:54:21.530 --> 00:54:24.950 So what then, actually, is a constraint satisfaction problem? 00:54:24.950 --> 00:54:28.650 Well, a constraint satisfaction problem is just some set of variables, 00:54:28.650 --> 00:54:33.600 x1 all the way through xn, some set of domains for each of those variables. 00:54:33.600 --> 00:54:36.320 So every variable needs to take on some values. 00:54:36.320 --> 00:54:38.240 Maybe every variable has the same domain, 00:54:38.240 --> 00:54:40.767 but maybe each variable has a slightly different domain. 00:54:40.767 --> 00:54:42.350 And then there's a set of constraints. 00:54:42.350 --> 00:54:45.230 So we'll just call a set C that has some constraints that 00:54:45.230 --> 00:54:49.190 are placed upon these variables, like x1 is not equal to x2, 00:54:49.190 --> 00:54:53.600 but there could be other forms too, like maybe x1 equals x2 plus 1 if you-- 00:54:53.600 --> 00:54:57.030 if these variables are taking on numerical values in their domain, 00:54:57.030 --> 00:54:57.690 for example. 00:54:57.690 --> 00:55:01.940 The types of constraints are going to vary based on the types of problems. 00:55:01.940 --> 00:55:04.880 And constraint satisfaction shows up all over the place 00:55:04.880 --> 00:55:07.610 as well in any situation where we have variables that 00:55:07.610 --> 00:55:10.370 are subject to particular constraints. 00:55:10.370 --> 00:55:13.250 So one popular game is Sudoku, for example, 00:55:13.250 --> 00:55:16.333 this 9-by-9 grid where you need to fill in numbers in each of these cells, 00:55:16.333 --> 00:55:18.042 but you don't want to make sure there's-- 00:55:18.042 --> 00:55:21.050 you want to make sure there is never a duplicate number in any row, 00:55:21.050 --> 00:55:25.410 or in any column, or in any grid of 3-by-3 cells, for example. 00:55:25.410 --> 00:55:29.030 So what might this look like as a constraint satisfaction problem? 00:55:29.030 --> 00:55:33.080 Well, my variables are all of the empty squares in the puzzle, 00:55:33.080 --> 00:55:36.740 so represented here is just like an x, y-coordinate, for example, 00:55:36.740 --> 00:55:39.310 as all of the squares where I need to plug in a value 00:55:39.310 --> 00:55:41.780 where I don't know what value it should take on. 00:55:41.780 --> 00:55:46.520 The domain is just going to be all of the numbers from 1 through 9, any value 00:55:46.520 --> 00:55:48.580 that I could fill in to one of these cells. 00:55:48.580 --> 00:55:51.510 So that is going to be the domain for each of these variables. 00:55:51.510 --> 00:55:54.637 And then the constraints are going to be of the form like this cell can't 00:55:54.637 --> 00:55:57.220 be equal to this cell, can't be equal to this cell, can't be-- 00:55:57.220 --> 00:55:59.510 and all of these need to be different, for example, 00:55:59.510 --> 00:56:03.140 and same for all of the rows, and the columns, and the 3-by-3 squares 00:56:03.140 --> 00:56:03.960 as well. 00:56:03.960 --> 00:56:06.110 So those constraints are going to enforce 00:56:06.110 --> 00:56:09.130 what values are actually allowed. 00:56:09.130 --> 00:56:12.440 And we can formulate the same idea in the case of this exam scheduling 00:56:12.440 --> 00:56:16.790 problem where the variables we have are the different courses, A up through G. 00:56:16.790 --> 00:56:19.760 The domain for each of these variables is going 00:56:19.760 --> 00:56:21.320 to be Monday, Tuesday, and Wednesday. 00:56:21.320 --> 00:56:23.780 Those are the possible values that each of the variables 00:56:23.780 --> 00:56:26.210 can take on that, in this case, just represent, 00:56:26.210 --> 00:56:29.300 when is the exam for that class? 00:56:29.300 --> 00:56:31.700 And then the constraints are of this form-- 00:56:31.700 --> 00:56:34.100 A is not equal to B. A is not equal to C, 00:56:34.100 --> 00:56:36.830 meaning A and B can't have an exam on the same day. 00:56:36.830 --> 00:56:39.410 A and C can't have an exam on the same day. 00:56:39.410 --> 00:56:44.570 Or more formally, these two variables cannot take on the same value within 00:56:44.570 --> 00:56:47.380 their domain. 00:56:47.380 --> 00:56:51.240 So that then is this formulation of a constraint satisfaction problem 00:56:51.240 --> 00:56:54.317 that we can begin to use to try and solve this problem. 00:56:54.317 --> 00:56:56.650 And constraints can come in a number of different forms. 00:56:56.650 --> 00:56:59.520 There are hard constraints, which are constraints that must 00:56:59.520 --> 00:57:01.430 be satisfied for a correct solution. 00:57:01.430 --> 00:57:05.910 So something like in the Sudoku puzzle, you cannot have this cell and this cell 00:57:05.910 --> 00:57:08.520 that are in the same row take on the same value. 00:57:08.520 --> 00:57:10.110 That is a hard constraint. 00:57:10.110 --> 00:57:12.240 But problems can also have soft constraints 00:57:12.240 --> 00:57:15.210 where these are constraints that express some notion of preference, 00:57:15.210 --> 00:57:19.020 that maybe A and B can't have an exam on the same day, 00:57:19.020 --> 00:57:23.370 but maybe someone has a preference that A's exam is earlier than B's exam. 00:57:23.370 --> 00:57:25.700 It doesn't need to be the case, but some expression 00:57:25.700 --> 00:57:28.770 that some solution is better than another solution. 00:57:28.770 --> 00:57:30.870 And in that case, you might formulate the problem 00:57:30.870 --> 00:57:34.200 as trying to optimize for maximizing people's preferences. 00:57:34.200 --> 00:57:38.200 You want people's preferences to be satisfied as much as possible. 00:57:38.200 --> 00:57:41.040 In this case though, we'll mostly just deal with hard constraints, 00:57:41.040 --> 00:57:45.265 constraints that must be met in order to have a correct solution to the problem. 00:57:45.265 --> 00:57:48.810 So we want to figure out some assignment of these variables 00:57:48.810 --> 00:57:51.270 to their particular values that is ultimately 00:57:51.270 --> 00:57:53.560 going to give us a solution to the problem 00:57:53.560 --> 00:57:56.970 by allowing us to assign some day to each of the classes 00:57:56.970 --> 00:58:00.430 such that we don't have any conflicts between classes. 00:58:00.430 --> 00:58:03.810 So it turns out that we can classify the constraints in a constraint 00:58:03.810 --> 00:58:07.352 satisfaction problem into a number of different categories. 00:58:07.352 --> 00:58:09.060 The first of those categories are perhaps 00:58:09.060 --> 00:58:11.040 the simplest of the types of constraints, 00:58:11.040 --> 00:58:13.200 which are known as "unary constraints" where 00:58:13.200 --> 00:58:17.430 a unary constraint is a constraint that just involves a single variable. 00:58:17.430 --> 00:58:19.890 For example, a unary constraint might be something like, 00:58:19.890 --> 00:58:24.550 A does not equal Monday, meaning course A cannot have its exam on Monday. 00:58:24.550 --> 00:58:27.780 If for some reason the instructor for the course isn't available on Monday, 00:58:27.780 --> 00:58:29.640 you might have a constraint in your problem 00:58:29.640 --> 00:58:32.850 that looks like this, something that just has a single variable A in it, 00:58:32.850 --> 00:58:35.770 and maybe says, A is not equal to Monday, or A is equal to something, 00:58:35.770 --> 00:58:38.460 or, in the case of numbers, greater than or less than something. 00:58:38.460 --> 00:58:43.140 A constraint that just has one variable we consider to be a unary constraint. 00:58:43.140 --> 00:58:46.470 And this is in contrast to something like a binary constraint, which 00:58:46.470 --> 00:58:49.510 is a constraint that involves two variables, for example. 00:58:49.510 --> 00:58:52.620 So this would be a constraint like the ones we were looking at before. 00:58:52.620 --> 00:58:57.870 Something like A does not equal B is an example of a binary constraint 00:58:57.870 --> 00:59:01.740 because it is a constraint that has two variables involved in it, A and B. 00:59:01.740 --> 00:59:06.030 And we represented that using some arc or some edge that 00:59:06.030 --> 00:59:09.052 connects variable A to variable B. 00:59:09.052 --> 00:59:11.760 And using this knowledge of, OK, what is a unary constraint, what 00:59:11.760 --> 00:59:14.220 is a binary constraint, there are different types 00:59:14.220 --> 00:59:18.180 of things we can say about a particular constraint satisfaction problem. 00:59:18.180 --> 00:59:22.770 And one thing we can say is we can try and make the problem node consistent. 00:59:22.770 --> 00:59:24.570 So what does "node consistency" mean? 00:59:24.570 --> 00:59:28.710 Node consistency means that we have all of the vari-- values in a variable's 00:59:28.710 --> 00:59:32.770 domain satisfying that variable's unary constraints. 00:59:32.770 --> 00:59:36.300 So for each of the variables inside of our constraint satisfaction problem, 00:59:36.300 --> 00:59:40.020 if all of the values satisfy the unary constraints 00:59:40.020 --> 00:59:44.220 for that particular variable, we can say that the entire problem is node 00:59:44.220 --> 00:59:47.220 consistent, or we can even say that a particular variable is 00:59:47.220 --> 00:59:51.900 node consistent if we just want to make one node consistent within itself. 00:59:51.900 --> 00:59:53.520 So what does that actually look like? 00:59:53.520 --> 00:59:55.522 Let's look at now a simplified example where 00:59:55.522 --> 00:59:57.730 instead of having a whole bunch of different classes, 00:59:57.730 --> 01:00:00.840 we just have two classes, A and B, each of which 01:00:00.840 --> 01:00:03.450 has an exam on either Monday, or Tuesday, or Wednesday. 01:00:03.450 --> 01:00:05.480 So this is the domain for the variable A. 01:00:05.480 --> 01:00:08.370 And this is the domain for the variable B. 01:00:08.370 --> 01:00:11.190 And now let's imagine we have these constraints-- 01:00:11.190 --> 01:00:13.440 A not equal to Monday, B not equal to Tuesday, 01:00:13.440 --> 01:00:16.500 B not equal to Monday, A not equal to B. So those 01:00:16.500 --> 01:00:19.790 are the constraints that we have on this particular problem. 01:00:19.790 --> 01:00:23.760 And what we can now try to do is enforce node consistency. 01:00:23.760 --> 01:00:26.670 And node consistency just means we make sure 01:00:26.670 --> 01:00:29.520 that all of the values for any variable's domain 01:00:29.520 --> 01:00:32.490 satisfy its unary constraints. 01:00:32.490 --> 01:00:36.583 And so we can start by trying to make node A node consistent, 01:00:36.583 --> 01:00:37.500 like is it consistent? 01:00:37.500 --> 01:00:42.360 And does every value inside of A's domain satisfy it's unary constraints? 01:00:42.360 --> 01:00:47.040 Well, initially, we'll see that Monday does not satisfy A's unary constraints. 01:00:47.040 --> 01:00:49.770 Because we have a constraint, a unary constraint here 01:00:49.770 --> 01:00:51.870 that A is not equal to Monday. 01:00:51.870 --> 01:00:54.580 But Monday is still in A's domain. 01:00:54.580 --> 01:00:57.710 And so this is something that is not node consistent because we 01:00:57.710 --> 01:00:59.460 have Monday in the domain, but this is not 01:00:59.460 --> 01:01:02.400 a valid value for this particular node. 01:01:02.400 --> 01:01:04.572 And so how do we make this node consistent? 01:01:04.572 --> 01:01:06.780 Well, to make the node node-consistent, what we'll do 01:01:06.780 --> 01:01:10.050 is we'll just go ahead and remove Monday from A's domain. 01:01:10.050 --> 01:01:12.480 Now A can only be on Tuesday or Wednesday 01:01:12.480 --> 01:01:16.630 because we had this constraint that said A is not equal to Monday. 01:01:16.630 --> 01:01:19.740 And at this point now, A is node consistent. 01:01:19.740 --> 01:01:22.890 For each of the values that A can take on, Tuesday and Wednesday, 01:01:22.890 --> 01:01:26.828 there is no constraint that is a unary constraint that 01:01:26.828 --> 01:01:27.870 conflicts with that idea. 01:01:27.870 --> 01:01:30.350 There is no constraint that says that A can't be Tuesday. 01:01:30.350 --> 01:01:34.280 There is no unary constraint that says that A cannot be on Wednesday. 01:01:34.280 --> 01:01:37.570 And so now we can turn our attention to B. B also has the domain Monday, 01:01:37.570 --> 01:01:38.760 Tuesday, and Wednesday. 01:01:38.760 --> 01:01:42.660 And we can begin to see whether those variables satisfy 01:01:42.660 --> 01:01:44.400 the unary constraints as well. 01:01:44.400 --> 01:01:45.840 Well, here is a unary constraint-- 01:01:45.840 --> 01:01:47.815 B is not equal to Tuesday. 01:01:47.815 --> 01:01:50.940 And that does not appear to be satisfied by this domain of Monday, Tuesday, 01:01:50.940 --> 01:01:51.750 and Wednesday. 01:01:51.750 --> 01:01:56.220 Because Tuesday, this possible value that the variable B could take on, 01:01:56.220 --> 01:01:58.900 is not consistent with this unary constraint 01:01:58.900 --> 01:02:00.780 that B is not equal to Tuesday. 01:02:00.780 --> 01:02:04.800 So to solve that problem, we'll go ahead and remove Tuesday from B's domain. 01:02:04.800 --> 01:02:07.560 Now B's domain only contains Monday and Wednesday. 01:02:07.560 --> 01:02:10.140 But as it turns out, there's yet another unary constraint 01:02:10.140 --> 01:02:15.130 that we placed on the variable B, which is here, B is not equal to Monday. 01:02:15.130 --> 01:02:18.480 That means that this value, Monday inside of B's domain, 01:02:18.480 --> 01:02:21.750 is not consistent with B's unary constraints because we have 01:02:21.750 --> 01:02:24.330 a constraint that says that B cannot be Monday. 01:02:24.330 --> 01:02:26.580 And so we can remove Monday from B's domain. 01:02:26.580 --> 01:02:29.692 And now we've made it through all of the unary constraints. 01:02:29.692 --> 01:02:31.650 We've not yet considered this constraint, which 01:02:31.650 --> 01:02:33.840 is a binary constraint, but we've considered 01:02:33.840 --> 01:02:36.210 all of the unary constraints, all of the constraints 01:02:36.210 --> 01:02:38.550 that involve just a single variable. 01:02:38.550 --> 01:02:41.932 And we've made sure that every node is consistent 01:02:41.932 --> 01:02:43.140 with those unary constraints. 01:02:43.140 --> 01:02:46.830 So we can say that now we have enforced node consistency, 01:02:46.830 --> 01:02:49.170 that for each of these possible nodes, we 01:02:49.170 --> 01:02:51.360 can pick any of these values in the domain, 01:02:51.360 --> 01:02:56.760 and there won't be a unary constraint that is violated as a result of it. 01:02:56.760 --> 01:02:59.080 So node consistency is fairly easy to enforce. 01:02:59.080 --> 01:03:01.740 We just take each node, make sure the values in the domain 01:03:01.740 --> 01:03:03.330 satisfy the unary constraints. 01:03:03.330 --> 01:03:05.730 And where things get a little bit more interesting 01:03:05.730 --> 01:03:09.030 is what we consider different types of consistency, something 01:03:09.030 --> 01:03:11.970 like arc consistency, for example. 01:03:11.970 --> 01:03:16.500 And arc consistency refers to when all of the values in a variable's domain 01:03:16.500 --> 01:03:19.600 satisfy the variable's binary constraints. 01:03:19.600 --> 01:03:22.830 So when we're looking at trying to make A arc-consistent, 01:03:22.830 --> 01:03:25.200 we're no longer just considering the unary constraints 01:03:25.200 --> 01:03:29.610 that involve A. We're trying to consider all of the binary constraints that 01:03:29.610 --> 01:03:33.210 involve A as well, so any edge that connects A 01:03:33.210 --> 01:03:36.630 to another variable inside of that constraint graph 01:03:36.630 --> 01:03:38.820 that we were taking a look at before. 01:03:38.820 --> 01:03:42.060 Put a little bit more formally, arc consistency-- and "arc" 01:03:42.060 --> 01:03:45.450 really is just another word for like an edge that connects two of these nodes 01:03:45.450 --> 01:03:47.130 inside of our constraint graph-- 01:03:47.130 --> 01:03:50.340 we can define "arc consistency" a little more precisely like this. 01:03:50.340 --> 01:03:54.750 In order to make some variable x arc-consistent with respect 01:03:54.750 --> 01:04:01.200 to some other variable y, we need to remove any element from x's domain 01:04:01.200 --> 01:04:05.280 to make sure that every choice for x, every choice in x's domain 01:04:05.280 --> 01:04:08.660 has a possible choice for y. 01:04:08.660 --> 01:04:10.410 So put another way, if I have a variable x 01:04:10.410 --> 01:04:13.170 and I want to make x an arc-consistent, then 01:04:13.170 --> 01:04:15.390 I'm going to look at all of the possible values 01:04:15.390 --> 01:04:19.440 that x can take on and make sure that, for all of those possible values, 01:04:19.440 --> 01:04:22.650 there is still some choice that I can make for y, 01:04:22.650 --> 01:04:26.010 if there's some arc between x and y to make sure 01:04:26.010 --> 01:04:30.580 that y has a possible option that I can choose as well. 01:04:30.580 --> 01:04:34.050 So let's look at an example of that going back to this example from before. 01:04:34.050 --> 01:04:36.960 We enforced node consistency already by saying 01:04:36.960 --> 01:04:38.880 that A can only be on Tuesday or Wednesday 01:04:38.880 --> 01:04:40.890 because we knew that A could not be on Monday. 01:04:40.890 --> 01:04:43.230 And we also said that B's only domain only 01:04:43.230 --> 01:04:46.710 consists of Wednesday because we know the B does not equal Tuesday, 01:04:46.710 --> 01:04:49.560 and also B does not equal Monday. 01:04:49.560 --> 01:04:52.710 So now let's begin to consider arc consistency. 01:04:52.710 --> 01:04:56.250 Let's try and make A arc-consistent with B. 01:04:56.250 --> 01:05:00.090 And what that means is to make A arc-consistent with respect to B means 01:05:00.090 --> 01:05:03.120 that for any choice we make in A's domain, 01:05:03.120 --> 01:05:07.790 there is some choice we can make in B's domain that is going to be consistent. 01:05:07.790 --> 01:05:08.670 And we can try that. 01:05:08.670 --> 01:05:11.970 For A, we can choose Tuesday as a possible value for A. 01:05:11.970 --> 01:05:15.450 If I choose Tuesday for A, is there a value for B 01:05:15.450 --> 01:05:17.640 that satisfies the binary constraint? 01:05:17.640 --> 01:05:20.640 Well, yes, B-- Wednesday would satisfy this constraint 01:05:20.640 --> 01:05:24.900 that A does not equal B because Tuesday does not equal Wednesday. 01:05:24.900 --> 01:05:28.650 However, if we chose Wednesday for A, well, 01:05:28.650 --> 01:05:33.930 then there is no choice in B's domain that satisfies this binary constraint. 01:05:33.930 --> 01:05:38.610 There is no way I can choose something for B that satisfies A does not equal B 01:05:38.610 --> 01:05:41.220 because I know B must be Wednesday. 01:05:41.220 --> 01:05:43.410 And so if ever I run into a situation like this 01:05:43.410 --> 01:05:46.770 where I see that here is a possible value for A such 01:05:46.770 --> 01:05:50.940 that there is no choice of the value for B that satisfies the binary constraint, 01:05:50.940 --> 01:05:53.610 well, then this is not arc-consistent. 01:05:53.610 --> 01:05:57.990 And to make it arc-consistent, I would need to take Wednesday and remove it 01:05:57.990 --> 01:05:58.890 from A's domain. 01:05:58.890 --> 01:06:01.470 Because Wednesday was not going to be a possible choice I 01:06:01.470 --> 01:06:05.490 can make for A because it wasn't consistent with this binary constraint 01:06:05.490 --> 01:06:08.525 for B. There was no way I could choose Wednesday for A 01:06:08.525 --> 01:06:13.930 and still have an available solution by choosing something for B as well. 01:06:13.930 --> 01:06:17.153 So here now, I've been able to enforce arc consistency. 01:06:17.153 --> 01:06:19.570 And in doing so, I've actually solved this entire problem. 01:06:19.570 --> 01:06:22.170 They've given these constraints where A and B 01:06:22.170 --> 01:06:25.170 can have exams on either Monday, or Tuesday, or Wednesday. 01:06:25.170 --> 01:06:29.400 The only solution, as it would appear, is that A's exam must be on Tuesday, 01:06:29.400 --> 01:06:31.620 and B's exam must be on Wednesday. 01:06:31.620 --> 01:06:34.980 And that is the only option available to me. 01:06:34.980 --> 01:06:37.980 So if we want to apply our consistency to a larger graph, 01:06:37.980 --> 01:06:40.883 not just looking at one particular pair of arc consistency, 01:06:40.883 --> 01:06:42.300 there are ways we can do that too. 01:06:42.300 --> 01:06:44.592 And we can begin to formalize what the pseudocode would 01:06:44.592 --> 01:06:46.720 look like for trying to write an algorithm that 01:06:46.720 --> 01:06:48.730 enforces arc consistency. 01:06:48.730 --> 01:06:52.300 And we'll start by defining a function called "revise." 01:06:52.300 --> 01:06:55.210 Revise is going to take as input a csp, otherwise known 01:06:55.210 --> 01:07:00.190 as a "constraint satisfaction problem," and also two variables, X and Y. 01:07:00.190 --> 01:07:02.380 And what revise is going to do is it is going 01:07:02.380 --> 01:07:06.490 to make X arc-consistent with respect to Y, 01:07:06.490 --> 01:07:09.790 meaning remove anything from X's domain that doesn't 01:07:09.790 --> 01:07:12.475 allow for a possible option for Y. 01:07:12.475 --> 01:07:14.017 And how does this work? 01:07:14.017 --> 01:07:15.850 Well, we'll go ahead and first keep track of 01:07:15.850 --> 01:07:17.392 whether or not we've made a revision. 01:07:17.392 --> 01:07:20.430 Revise is ultimately going to return true or false. 01:07:20.430 --> 01:07:24.790 It'll return true in the event that we did make a revision to X's domain. 01:07:24.790 --> 01:07:28.210 It'll return false if we didn't make any change to X's domain. 01:07:28.210 --> 01:07:30.970 And we'll see in a moment why that's going to be helpful. 01:07:30.970 --> 01:07:32.920 But we start by saying "revised equals false." 01:07:32.920 --> 01:07:34.812 We haven't made any changes. 01:07:34.812 --> 01:07:36.520 Then we'll say, all right, let's go ahead 01:07:36.520 --> 01:07:40.240 and loop over all of the possible values in X's domain, 01:07:40.240 --> 01:07:44.410 so loop over X's domain for each little x in X's domain. 01:07:44.410 --> 01:07:46.720 I want to make sure that for each of those choices, 01:07:46.720 --> 01:07:51.250 I have some available choice in Y that satisfies the binary constraints that 01:07:51.250 --> 01:07:56.260 are defined inside of my csp, inside of my constraint satisfaction problem. 01:07:56.260 --> 01:08:02.260 So if ever it's the case that there is no value y in Y's domain 01:08:02.260 --> 01:08:06.980 that satisfies the constraint for X and Y, well, if that's the case, 01:08:06.980 --> 01:08:11.150 that means that this value x shouldn't be in X's domain. 01:08:11.150 --> 01:08:13.730 So we'll go ahead and delete x from X's domain. 01:08:13.730 --> 01:08:17.200 And I'll set revised equal to true because I did change X's domain. 01:08:17.200 --> 01:08:20.500 I changed X's domain by removing little x. 01:08:20.500 --> 01:08:24.210 And I removed a little x because it wasn't arc-consistent, 01:08:24.210 --> 01:08:27.040 and there was no way I could choose a value for Y that 01:08:27.040 --> 01:08:30.432 would satisfy this XY constraint. 01:08:30.432 --> 01:08:32.890 So in this case, we'll go ahead and set revised equal true. 01:08:32.890 --> 01:08:36.010 And we'll do this again and again for every value in X's domain. 01:08:36.010 --> 01:08:37.600 Sometimes it might be fine. 01:08:37.600 --> 01:08:41.590 In other cases, it might not allow for a possible choice for Y, in which case 01:08:41.590 --> 01:08:44.439 we need to remove this value from X's domain. 01:08:44.439 --> 01:08:48.100 And at the end, we just return revised to indicate whether or not 01:08:48.100 --> 01:08:50.170 we actually made a change. 01:08:50.170 --> 01:08:52.210 So this function then, this revise function 01:08:52.210 --> 01:08:55.990 is effectively an implementation of what you saw me do graphically a moment ago. 01:08:55.990 --> 01:09:00.399 And it makes one variable, X, arc-consistent with another variable, 01:09:00.399 --> 01:09:03.520 in this case Y. But generally speaking, when 01:09:03.520 --> 01:09:05.560 we want to enforce arc consistency, we'll 01:09:05.560 --> 01:09:08.950 often want to enforce arc consistency not just for a single arc 01:09:08.950 --> 01:09:11.680 but for the entire constraint satisfaction problem. 01:09:11.680 --> 01:09:14.180 And it turns out there's an algorithm to do that as well. 01:09:14.180 --> 01:09:16.420 And that algorithm is known as AC-3. 01:09:16.420 --> 01:09:19.090 AC-3 takes a constraint satisfaction problem, 01:09:19.090 --> 01:09:23.350 and it enforces arc consistency across the entire problem. 01:09:23.350 --> 01:09:24.312 How does it do that? 01:09:24.312 --> 01:09:26.979 Well, it's going to basically maintain a queue or basically just 01:09:26.979 --> 01:09:30.939 a line of all of the arcs that it needs to make consistent. 01:09:30.939 --> 01:09:33.550 And over time, we might remove things from that queue 01:09:33.550 --> 01:09:35.665 as we begin dealing with arc consistency. 01:09:35.665 --> 01:09:37.540 And we might need to add things to that queue 01:09:37.540 --> 01:09:41.840 as well if there are more things we need to make arc-consistent. 01:09:41.840 --> 01:09:43.750 So we'll go ahead and start with a queue that 01:09:43.750 --> 01:09:47.859 contains all of the arcs in the constraint satisfaction problem, all 01:09:47.859 --> 01:09:50.290 of the edges that connect to nodes that have 01:09:50.290 --> 01:09:53.510 some sort of binary constraint between them. 01:09:53.510 --> 01:09:57.550 And now, as long as the queue is not empty, there is work to be done. 01:09:57.550 --> 01:10:01.340 The queue is all of the things that we need to make arc-consistent. 01:10:01.340 --> 01:10:04.810 So as long as the queue is not empty, there's still things we have to do. 01:10:04.810 --> 01:10:06.500 What do we have to do? 01:10:06.500 --> 01:10:10.402 Well, we'll start by dequeuing from the queue, remove something from the queue. 01:10:10.402 --> 01:10:12.610 And strictly speaking, it doesn't need to be a queue, 01:10:12.610 --> 01:10:14.610 but a queue is a traditional way of doing this. 01:10:14.610 --> 01:10:16.660 We'll dequeue from the queue, and that'll 01:10:16.660 --> 01:10:20.320 give us an arc, X and Y, these two variables where I would 01:10:20.320 --> 01:10:24.100 like to make X arc-consistent with Y. 01:10:24.100 --> 01:10:27.070 So how do we make X arc-consistent with Y? 01:10:27.070 --> 01:10:29.380 Well, we can go ahead and just use that revise function 01:10:29.380 --> 01:10:30.820 that we talked about a moment ago. 01:10:30.820 --> 01:10:34.780 We call the revise function, passing as input the constraint satisfaction 01:10:34.780 --> 01:10:37.510 problem, and also these variables X and Y 01:10:37.510 --> 01:10:40.870 because I want to make X arc-consistent with Y, in other words, 01:10:40.870 --> 01:10:47.080 remove any values from X's domain that don't leave an available option for Y. 01:10:47.080 --> 01:10:49.140 And recall, what does revise return? 01:10:49.140 --> 01:10:53.290 Well, it returns true if we actually made a change, if we removed something 01:10:53.290 --> 01:10:57.870 from X's domain because there wasn't an available option for Y, for example. 01:10:57.870 --> 01:11:01.960 And it returns false if we didn't make any change to X's domain at all. 01:11:01.960 --> 01:11:05.177 And it turns out if revise returns false, if we didn't make any changes, 01:11:05.177 --> 01:11:08.260 well, then there's not a whole lot more work to be done here for this arc. 01:11:08.260 --> 01:11:11.800 We can just move ahead to the next arc that's in the queue. 01:11:11.800 --> 01:11:16.390 But if we did make a change, if we did reduce X's domain by removing values 01:11:16.390 --> 01:11:19.570 from X's domain, well, then what we might realize 01:11:19.570 --> 01:11:22.360 is that this creates potential problems later on, 01:11:22.360 --> 01:11:27.490 that it might mean that some arc that was arc-consistent with X, that node 01:11:27.490 --> 01:11:29.890 might no longer be arc-consistent with X. 01:11:29.890 --> 01:11:32.830 Because while there used to be an option that we could choose for X, 01:11:32.830 --> 01:11:35.740 now there might not be because now we might have removed something 01:11:35.740 --> 01:11:40.550 from X that was necessary for some other arc to be arc-consistent. 01:11:40.550 --> 01:11:43.360 And so if ever we did revise X's domain, we're 01:11:43.360 --> 01:11:46.960 going to need to add some things to the queue, some additional arcs 01:11:46.960 --> 01:11:48.520 that we might want to check. 01:11:48.520 --> 01:11:49.940 How do we do that? 01:11:49.940 --> 01:11:54.160 Well, first thing we want to check is to make sure that X's domain is not 0. 01:11:54.160 --> 01:11:58.362 If X's domain is 0, that means there are no available options for X at all, 01:11:58.362 --> 01:12:01.570 and that means that there is no way you can solve the constraint satisfaction 01:12:01.570 --> 01:12:02.070 problem. 01:12:02.070 --> 01:12:04.362 If we've removed everything from X's domain, 01:12:04.362 --> 01:12:06.070 we'll go ahead and just return false here 01:12:06.070 --> 01:12:08.660 to indicate there's no way to solve the problem because there 01:12:08.660 --> 01:12:10.810 is nothing left in X's domain. 01:12:10.810 --> 01:12:15.790 But otherwise, if there are things left in X's domain but fewer things 01:12:15.790 --> 01:12:18.400 than before, well, then what we'll do is we'll 01:12:18.400 --> 01:12:23.860 loop over each variable Z that is in all of X's neighbors except for Y. Y 01:12:23.860 --> 01:12:24.980 we already handled. 01:12:24.980 --> 01:12:27.610 But we'll consider all X's others neighbors 01:12:27.610 --> 01:12:32.230 and ask ourselves, all right, will that arc from each of those Zs to X-- 01:12:32.230 --> 01:12:34.600 that arc might no longer be arc-consistent. 01:12:34.600 --> 01:12:38.150 Because while for each Z there might have been a possible option 01:12:38.150 --> 01:12:41.620 we could choose for X to correspond with each of Z's possible values, 01:12:41.620 --> 01:12:45.888 now there might not be because we removed some elements from X's domain. 01:12:45.888 --> 01:12:47.680 And so what we'll do here is we'll go ahead 01:12:47.680 --> 01:12:51.280 and enqueue, adding something to the queue, this arc, 01:12:51.280 --> 01:12:53.980 Z, X for all of those neighbors' Zs. 01:12:53.980 --> 01:12:56.530 So we need to add back some arcs to the queue 01:12:56.530 --> 01:13:00.328 in order to continue to enforce arc consistency. 01:13:00.328 --> 01:13:02.620 At the very end if we make it through all this process, 01:13:02.620 --> 01:13:04.990 then we can return true. 01:13:04.990 --> 01:13:09.550 But this now is AC-3, this algorithm for enforcing arc consistency 01:13:09.550 --> 01:13:11.410 on a constraint satisfaction problem. 01:13:11.410 --> 01:13:14.560 And the big idea is really just keep track of all of the arcs 01:13:14.560 --> 01:13:16.800 that we might need to make arc-consistent. 01:13:16.800 --> 01:13:19.850 Make it arc-consistent by calling the revise function. 01:13:19.850 --> 01:13:22.600 And if we did revise it, then there are some new arcs 01:13:22.600 --> 01:13:24.820 that might need to be added to the queue in order 01:13:24.820 --> 01:13:27.760 to make sure that everything is still arc-consistent 01:13:27.760 --> 01:13:30.460 even after we've removed some of the elements 01:13:30.460 --> 01:13:33.220 from a particular variable's domain. 01:13:33.220 --> 01:13:37.297 So what then would happen if we tried to enforce arc consistency 01:13:37.297 --> 01:13:39.880 on a graph like this, on a graph where each of these variables 01:13:39.880 --> 01:13:42.880 has a domain of Monday, Tuesday and Wednesday? 01:13:42.880 --> 01:13:45.580 Well, it turns out that by enforcing arc consistency 01:13:45.580 --> 01:13:48.730 on this graph, while it can solve some types of problems, 01:13:48.730 --> 01:13:50.890 nothing actually changes here. 01:13:50.890 --> 01:13:54.410 For any particular arc just considering two variables, 01:13:54.410 --> 01:13:56.620 there's always a way for me to adjust for any 01:13:56.620 --> 01:13:59.868 of the choices I make for one of them, make a choice for the other one 01:13:59.868 --> 01:14:01.660 because there are three options, and I just 01:14:01.660 --> 01:14:03.920 need the two to be different from each other. 01:14:03.920 --> 01:14:06.250 So this is actually quite easy to just take an arc 01:14:06.250 --> 01:14:08.350 and just declare that it is arc-consistent. 01:14:08.350 --> 01:14:10.960 Because if I pick Monday for D, and then I 01:14:10.960 --> 01:14:14.830 just pick something that isn't Monday for B, in arc consistency, 01:14:14.830 --> 01:14:19.900 we only consider consistency between a binary constraint between two nodes. 01:14:19.900 --> 01:14:23.810 And we're not really considering all of the rest of the nodes yet. 01:14:23.810 --> 01:14:27.790 So just using AC-3, the enforcement of arc consistency, 01:14:27.790 --> 01:14:29.800 that can sometimes have the effect of reducing 01:14:29.800 --> 01:14:32.410 domains to make it easier to find solutions. 01:14:32.410 --> 01:14:35.380 But it will not always actually solve the problem. 01:14:35.380 --> 01:14:39.540 We might still need to somehow search to try and find a solution. 01:14:39.540 --> 01:14:43.210 And we can use classical, traditional search algorithms to try to do so. 01:14:43.210 --> 01:14:46.480 You'll recall that a search problem generally consists of these parts. 01:14:46.480 --> 01:14:49.150 We have some initial state, some actions, 01:14:49.150 --> 01:14:52.480 a transition model that takes me from one state to another state, 01:14:52.480 --> 01:14:56.800 a goal test to tell me have I satisfied my objective correctly, 01:14:56.800 --> 01:14:58.778 and then some path cost function. 01:14:58.778 --> 01:15:01.570 Because in the case of maze-solving, I was trying to get to my goal 01:15:01.570 --> 01:15:03.460 as quickly as possible. 01:15:03.460 --> 01:15:08.050 So you could formulate a csp, or a constraint satisfaction problem, 01:15:08.050 --> 01:15:10.000 as one of these types of search problems. 01:15:10.000 --> 01:15:13.450 The initial state will just be an empty assignment 01:15:13.450 --> 01:15:15.580 where an "assignment" is just a way for me 01:15:15.580 --> 01:15:18.950 to assign any particular variable to any particular value. 01:15:18.950 --> 01:15:22.150 So if an empty assignment is no variables are assigned to any values 01:15:22.150 --> 01:15:27.730 yet, then the action I can take is adding some new variable 01:15:27.730 --> 01:15:31.210 equals value pair to that assignment saying, for this assignment, 01:15:31.210 --> 01:15:34.200 let me add a new value for this variable. 01:15:34.200 --> 01:15:37.670 And the transition model just defines what happens when you take that action. 01:15:37.670 --> 01:15:41.050 You get a new assignment that has that variable equal to that value 01:15:41.050 --> 01:15:42.280 inside of it. 01:15:42.280 --> 01:15:45.190 The goal test is just checking to make sure all the variables have 01:15:45.190 --> 01:15:48.930 been assigned and making sure all the constraints have been satisfied. 01:15:48.930 --> 01:15:51.493 And the path cost function is sort of irrelevant. 01:15:51.493 --> 01:15:53.410 I don't really care about what the path really 01:15:53.410 --> 01:15:57.490 is, I just care about finding some assignment that actually satisfies 01:15:57.490 --> 01:15:58.940 all of the constraints. 01:15:58.940 --> 01:16:00.850 So really, all the paths have the same cost. 01:16:00.850 --> 01:16:03.400 I don't really care about the path to the goal. 01:16:03.400 --> 01:16:08.470 I just care about the solution itself, much as we've talked about now before. 01:16:08.470 --> 01:16:11.637 The problem here though is that if we just implement this naive search 01:16:11.637 --> 01:16:13.970 algorithm just by implementing like breadth-first search 01:16:13.970 --> 01:16:17.110 or depth-first search, this is going to be very, very inefficient. 01:16:17.110 --> 01:16:19.780 And there are ways we can take advantage of efficiencies 01:16:19.780 --> 01:16:23.140 in the structure of a constraint satisfaction problem itself. 01:16:23.140 --> 01:16:28.420 And one of the key ideas is that we can really just order these variables. 01:16:28.420 --> 01:16:31.060 And it doesn't matter what order we assign variables in. 01:16:31.060 --> 01:16:34.120 The assignment A equals 2 and then B equals 01:16:34.120 --> 01:16:38.650 8 is identical to the assignment of B equals 8 and then A equals 2. 01:16:38.650 --> 01:16:41.440 Switching the order doesn't really change anything 01:16:41.440 --> 01:16:44.230 about the fundamental nature of that assignment. 01:16:44.230 --> 01:16:47.430 And so there are some ways that we can try and revise 01:16:47.430 --> 01:16:50.580 this idea of a search algorithm to apply it specifically 01:16:50.580 --> 01:16:53.112 for a problem like a constraint satisfaction problem. 01:16:53.112 --> 01:16:55.320 And it turns out the search algorithm we'll generally 01:16:55.320 --> 01:16:57.860 use when talking about constraint satisfaction problems 01:16:57.860 --> 01:17:00.540 is something known as "backtracking search." 01:17:00.540 --> 01:17:02.820 And the big idea of backtracking search is 01:17:02.820 --> 01:17:06.090 we'll go ahead and make assignments from variables to values. 01:17:06.090 --> 01:17:08.820 And if ever we get stuck, we arrive at a place 01:17:08.820 --> 01:17:12.570 where there is no way we can make any forward progress while still preserving 01:17:12.570 --> 01:17:14.940 the constraints that we need to enforce, we'll 01:17:14.940 --> 01:17:18.760 go ahead and backtrack and try something else instead. 01:17:18.760 --> 01:17:22.170 So the very basic sketch of what backtracking search looks like is it 01:17:22.170 --> 01:17:25.770 looks like this, a function called "backtrack" that takes as input 01:17:25.770 --> 01:17:29.010 an assignment and a constraint satisfaction problem. 01:17:29.010 --> 01:17:31.610 So initially, we don't have any assigned variables. 01:17:31.610 --> 01:17:34.080 So when we begin backtracking search, this assignment 01:17:34.080 --> 01:17:37.260 is just going to be the empty assignment with no variables inside of it. 01:17:37.260 --> 01:17:40.590 But we'll see later this is going to be a recursive function. 01:17:40.590 --> 01:17:44.490 So backtrack takes as input the assignment and the problem. 01:17:44.490 --> 01:17:47.850 If the assignment is complete, meaning all of the variables 01:17:47.850 --> 01:17:50.428 have been assigned, we just return that assignment. 01:17:50.428 --> 01:17:52.470 That of course won't be true initially because we 01:17:52.470 --> 01:17:53.880 start with an empty assignment. 01:17:53.880 --> 01:17:56.130 But over time, we might add things to that assignment. 01:17:56.130 --> 01:17:59.190 So if ever the assignment actually is complete, then we're done. 01:17:59.190 --> 01:18:02.140 Then just go ahead and return that assignment. 01:18:02.140 --> 01:18:04.620 But otherwise, there is some work to be done. 01:18:04.620 --> 01:18:08.670 So what we'll need to do is select an unassigned variable 01:18:08.670 --> 01:18:10.030 for this particular problem. 01:18:10.030 --> 01:18:12.447 So we need to take the problem, look at the variables that 01:18:12.447 --> 01:18:15.840 have already been assigned, and pick a variable that has not yet 01:18:15.840 --> 01:18:17.600 been assigned. 01:18:17.600 --> 01:18:19.470 And I'll go ahead and take that variable. 01:18:19.470 --> 01:18:23.473 And then I need to consider all of the values in that variable's domain. 01:18:23.473 --> 01:18:25.890 So we'll go ahead and call this "domain-values" function-- 01:18:25.890 --> 01:18:27.682 we'll talk a little more about that later-- 01:18:27.682 --> 01:18:29.910 that takes a variable and just gives me back 01:18:29.910 --> 01:18:33.190 an ordered list of all the values in its domain. 01:18:33.190 --> 01:18:35.670 So I've taken a random, unselected variable. 01:18:35.670 --> 01:18:38.400 I'm going to loop over all of the possible values. 01:18:38.400 --> 01:18:41.610 And the idea is, let me just try all of these values 01:18:41.610 --> 01:18:44.350 as possible values for the variable. 01:18:44.350 --> 01:18:48.030 So if the value is consistent with the assignment so far, 01:18:48.030 --> 01:18:51.270 it doesn't violate any of the constraints, well, then let's go ahead 01:18:51.270 --> 01:18:53.910 and add variable equals value to the assignment 01:18:53.910 --> 01:18:55.890 because it's so far consistent. 01:18:55.890 --> 01:18:59.250 And now let's recursively call backtrack to try and make 01:18:59.250 --> 01:19:02.070 the rest of the assignments also consistent. 01:19:02.070 --> 01:19:05.100 So we'll ahead and call backtrack on this new assignment 01:19:05.100 --> 01:19:08.620 that I've added this newest-- the variable equals value to. 01:19:08.620 --> 01:19:12.010 And now I recursively call backtrack and see what the result is. 01:19:12.010 --> 01:19:18.210 And if the result isn't a failure, well, then let me just return that result. 01:19:18.210 --> 01:19:21.340 And otherwise, what else could happen? 01:19:21.340 --> 01:19:23.760 Well, if it turns out the result was a failure, well, 01:19:23.760 --> 01:19:26.400 then that means this value was probably a bad choice 01:19:26.400 --> 01:19:27.780 for this particular variable. 01:19:27.780 --> 01:19:30.810 Because when I assigned this variable equal to that value, 01:19:30.810 --> 01:19:34.920 eventually, down the road, I ran into a situation where I violated constraints. 01:19:34.920 --> 01:19:36.360 There was nothing more I could do. 01:19:36.360 --> 01:19:40.020 So now I'll remove variable equals value from the assignment, 01:19:40.020 --> 01:19:43.390 effectively backtracking to say, all right, that value didn't work. 01:19:43.390 --> 01:19:46.390 Let's try another value instead. 01:19:46.390 --> 01:19:48.210 And then at the very end, if we were never 01:19:48.210 --> 01:19:50.370 able to return a complete assignment, we'll 01:19:50.370 --> 01:19:53.790 just go ahead and return failure because that means that none of the values 01:19:53.790 --> 01:19:56.760 worked for this particular variable. 01:19:56.760 --> 01:20:00.480 This now is the idea for backtracking search, to take each of the variables, 01:20:00.480 --> 01:20:04.140 try values for them, and recursively try backtracking search, see 01:20:04.140 --> 01:20:05.400 if we can make progress. 01:20:05.400 --> 01:20:08.310 And if ever we run into a dead end, we run into a situation 01:20:08.310 --> 01:20:10.350 where there is no possible value we can choose 01:20:10.350 --> 01:20:14.720 that satisfies the constraints, we return failure, and that propagates up. 01:20:14.720 --> 01:20:16.470 And eventually, we make a different choice 01:20:16.470 --> 01:20:20.170 by going back and trying something else instead. 01:20:20.170 --> 01:20:22.320 So let's put this algorithm into practice. 01:20:22.320 --> 01:20:26.380 Let's actually try and use backtracking search to solve this problem now where 01:20:26.380 --> 01:20:29.560 I need to figure out how to assign each of these courses to an exam slot 01:20:29.560 --> 01:20:33.430 on Monday, or Tuesday, or Wednesday in such a way that it satisfies these 01:20:33.430 --> 01:20:36.940 constraints, that each of these edges mean those two classes cannot have 01:20:36.940 --> 01:20:39.170 an exam on the same day. 01:20:39.170 --> 01:20:41.147 So I can start by just like starting at a node. 01:20:41.147 --> 01:20:42.980 It doesn't really matter which I start with. 01:20:42.980 --> 01:20:45.066 But in this case, we'll just start with A. 01:20:45.066 --> 01:20:47.440 And I'll ask a question like, all right, let me loop 01:20:47.440 --> 01:20:48.690 over the values in the domain. 01:20:48.690 --> 01:20:51.690 And maybe, in this case, I'll just start with Monday and say, all right, 01:20:51.690 --> 01:20:53.280 let's go ahead and assign A to Monday. 01:20:53.280 --> 01:20:56.010 We'll just go in order, Monday, Tuesday, Wednesday. 01:20:56.010 --> 01:20:59.567 And now let's consider node B. All right, so I've made an assignment to A, 01:20:59.567 --> 01:21:02.650 so I've recursively called backtrack with this new part of the assignment. 01:21:02.650 --> 01:21:05.500 Now I'm looking to pick another unassigned variable like B. 01:21:05.500 --> 01:21:08.333 And I'll say, all right, maybe I'll start with Monday because that's 01:21:08.333 --> 01:21:10.150 the very first value in B's domain. 01:21:10.150 --> 01:21:13.328 And I ask, all right, does Monday violate any constraints? 01:21:13.328 --> 01:21:14.620 And it turns out, yes, it does. 01:21:14.620 --> 01:21:17.440 It violates this constraint here between A and B 01:21:17.440 --> 01:21:19.750 because A and B are now both on Monday. 01:21:19.750 --> 01:21:23.620 And that doesn't work because B can't be on the same day as A. 01:21:23.620 --> 01:21:27.340 So that doesn't work, so we might instead try Tuesday, try the next value 01:21:27.340 --> 01:21:28.360 in B's domain. 01:21:28.360 --> 01:21:31.120 And is that consistent with the assignment so far? 01:21:31.120 --> 01:21:33.080 Well, yeah, B-Tuesday, A-Monday. 01:21:33.080 --> 01:21:35.980 That is consistent so far because they're not on the same day. 01:21:35.980 --> 01:21:36.610 So that's good. 01:21:36.610 --> 01:21:38.620 Now we can recursively call backtrack. 01:21:38.620 --> 01:21:39.490 Try again. 01:21:39.490 --> 01:21:42.350 Pick another unassigned variable, something like D and say, 01:21:42.350 --> 01:21:44.350 all right, let's go through its possible values. 01:21:44.350 --> 01:21:46.810 Is Monday consistent with this assignment? 01:21:46.810 --> 01:21:47.800 Well, yes it is. 01:21:47.800 --> 01:21:50.710 B and D are on different days, Monday versus Tuesday. 01:21:50.710 --> 01:21:53.710 And A and B are also on different days, Monday versus Tuesday. 01:21:53.710 --> 01:21:55.512 So that's fine so far too. 01:21:55.512 --> 01:21:56.720 We'll go ahead and try again. 01:21:56.720 --> 01:22:00.238 Maybe we'll go to this variable here, E, say, can we make that consistent? 01:22:00.238 --> 01:22:01.780 Let's go through the possible values. 01:22:01.780 --> 01:22:03.763 We've recursively called backtrack. 01:22:03.763 --> 01:22:05.680 We might start with Monday and say, all right, 01:22:05.680 --> 01:22:10.330 that's not consistent because D and E now have exams on the same day. 01:22:10.330 --> 01:22:13.270 So we might try Tuesday instead, going to the next one, ask, 01:22:13.270 --> 01:22:14.680 is that consistent? 01:22:14.680 --> 01:22:18.560 Well, no, it's not because B and E, those have exams on the same day. 01:22:18.560 --> 01:22:20.705 And so we try, all right, is Wednesday consistent? 01:22:20.705 --> 01:22:22.330 And it turns out, all right, yes it is. 01:22:22.330 --> 01:22:25.870 Wednesday is consistent because D and E now have exams on different days. 01:22:25.870 --> 01:22:28.420 B and E now have exams on different days. 01:22:28.420 --> 01:22:29.980 All seems to be well so far. 01:22:29.980 --> 01:22:34.550 I recursively call backtrack, select another unassigned variable, 01:22:34.550 --> 01:22:37.250 we'll say maybe to a C this time and say, all right, 01:22:37.250 --> 01:22:39.460 let's try the values that C could take on. 01:22:39.460 --> 01:22:40.810 Let's start with Monday. 01:22:40.810 --> 01:22:44.650 And it turns out that's not consistent because now A and C both have 01:22:44.650 --> 01:22:46.250 exams on the same day. 01:22:46.250 --> 01:22:50.140 So I try Tuesday and say, that's not consistent either because B and C now 01:22:50.140 --> 01:22:51.970 have exams on the same day. 01:22:51.970 --> 01:22:55.510 And then I say, all right, let's go ahead and try Wednesday. 01:22:55.510 --> 01:23:00.190 But that's not consistent either because C and E each have exams on the same day 01:23:00.190 --> 01:23:01.090 too. 01:23:01.090 --> 01:23:04.390 So now we've gone through all of the possible values for C, Monday, Tuesday 01:23:04.390 --> 01:23:06.610 and Wednesday, and none of them are consistent. 01:23:06.610 --> 01:23:09.550 There is no way we can have a consistent assignment. 01:23:09.550 --> 01:23:12.690 Backtrack, in this case, will return a failure. 01:23:12.690 --> 01:23:16.120 And so then we'd say, all right, we have to backtrack back to here. 01:23:16.120 --> 01:23:19.872 Well, now for E, we've tried all of Monday, Tuesday, and Wednesday, 01:23:19.872 --> 01:23:20.830 and none of those work. 01:23:20.830 --> 01:23:24.680 Because Wednesday, which seemed to work, turned out to be a failure. 01:23:24.680 --> 01:23:28.420 So that means there's no possible way we can assign E. So that's a failure too. 01:23:28.420 --> 01:23:31.120 We have to go back up to D, which means that Monday 01:23:31.120 --> 01:23:33.130 assignment to D, that must be wrong. 01:23:33.130 --> 01:23:34.640 We must try something else. 01:23:34.640 --> 01:23:36.473 So we can try, all right, what if D is Tue-- 01:23:36.473 --> 01:23:39.100 what if instead of Monday, we try Tuesday? 01:23:39.100 --> 01:23:41.740 Tuesday, it turns out, is not consistent because B and D now 01:23:41.740 --> 01:23:43.180 have an exam on the same day. 01:23:43.180 --> 01:23:46.405 But Wednesday, as it turns out, works. 01:23:46.405 --> 01:23:48.780 And now we can begin to make some forward progress again. 01:23:48.780 --> 01:23:51.820 We go back to E and say, all right, which of these values works? 01:23:51.820 --> 01:23:55.000 Monday turns out to work by not violating any constraints. 01:23:55.000 --> 01:23:56.602 Then we go up to C now. 01:23:56.602 --> 01:23:58.810 Monday doesn't work because it violates a constraint. 01:23:58.810 --> 01:24:00.787 It violates two actually. 01:24:00.787 --> 01:24:03.370 Tuesday doesn't work because it violates a constraint as well. 01:24:03.370 --> 01:24:04.492 But Wednesday does work. 01:24:04.492 --> 01:24:07.700 Then we can go to the next variable, F, and say, all right, does Monday work? 01:24:07.700 --> 01:24:09.590 Well, no, it violates a constraint. 01:24:09.590 --> 01:24:10.768 But Tuesday does work. 01:24:10.768 --> 01:24:13.060 And then, finally, we can look at the last variable, G, 01:24:13.060 --> 01:24:15.460 recursively calling backtrack one more time. 01:24:15.460 --> 01:24:18.490 Monday is inconsistent, and that violates a constraint. 01:24:18.490 --> 01:24:20.960 Tuesday also violates a constraint. 01:24:20.960 --> 01:24:24.300 But Wednesday, that doesn't violate a constraint. 01:24:24.300 --> 01:24:26.290 And so now, at this point, we recursively 01:24:26.290 --> 01:24:28.030 call backtrack one last time. 01:24:28.030 --> 01:24:31.420 We now have a satisfactory assignment of all of the variables. 01:24:31.420 --> 01:24:33.920 And at this point, we can say that we are now done. 01:24:33.920 --> 01:24:38.410 We have now been able to successfully assign a variable or a value 01:24:38.410 --> 01:24:40.270 to each one of these variables in such a way 01:24:40.270 --> 01:24:42.670 that we're not violating any constraints. 01:24:42.670 --> 01:24:46.720 We're going to go ahead and have classes A and E have their exams on Monday. 01:24:46.720 --> 01:24:49.750 Classes B and F can have their exams on Tuesday. 01:24:49.750 --> 01:24:53.650 And classes C, D, and G can have their exams on Wednesday, 01:24:53.650 --> 01:24:57.490 and there's no violated constraints that might come up there. 01:24:57.490 --> 01:25:00.148 So that then was a graphical look at how this might work. 01:25:00.148 --> 01:25:03.190 Let's now take a look at some code we could use to actually try and solve 01:25:03.190 --> 01:25:05.860 this problem as well. 01:25:05.860 --> 01:25:11.370 So here, I'll go ahead and go into the scheduling directory. 01:25:11.370 --> 01:25:12.390 We're here now. 01:25:12.390 --> 01:25:15.330 We'll start by looking at schedule0.py. 01:25:15.330 --> 01:25:16.350 We're here. 01:25:16.350 --> 01:25:19.740 I define a list of variables, A, B, C, D, E, F, G. 01:25:19.740 --> 01:25:22.470 Those are all of the different classes. 01:25:22.470 --> 01:25:25.680 Then underneath that, I define my list of constraints. 01:25:25.680 --> 01:25:27.750 So constraint A and B, that is a constraint 01:25:27.750 --> 01:25:31.350 because they can't be on the same day, likewise A and C, B and C, 01:25:31.350 --> 01:25:34.920 so on and so forth, enforcing those exact same constraints. 01:25:34.920 --> 01:25:38.740 And here then is what the backtracking function might look like. 01:25:38.740 --> 01:25:42.020 First, if the assignment is complete, if I've 01:25:42.020 --> 01:25:45.200 made an assignment of every variable to a value, 01:25:45.200 --> 01:25:48.000 go ahead and just return that assignment. 01:25:48.000 --> 01:25:51.380 Then we'll select an unassigned variable from that assignment. 01:25:51.380 --> 01:25:55.470 Then for each of the possible values in the domain, Monday, Tuesday, Wednesday, 01:25:55.470 --> 01:25:57.830 let's go ahead and create a new assignment that 01:25:57.830 --> 01:26:00.087 assigns the variable to that value. 01:26:00.087 --> 01:26:02.920 I'll call this consistent function, which I'll show you in a moment. 01:26:02.920 --> 01:26:05.840 That checks to make sure this new assignment is consistent. 01:26:05.840 --> 01:26:08.360 But if it is consistent, we'll go ahead and call backtrack 01:26:08.360 --> 01:26:11.690 to go ahead and continue trying to run backtracking search. 01:26:11.690 --> 01:26:15.380 And as long as the result is not None, meaning it wasn't a failure, 01:26:15.380 --> 01:26:18.210 we can go ahead and return that result. 01:26:18.210 --> 01:26:21.495 But if we make it through all the values and nothing works, 01:26:21.495 --> 01:26:22.370 then it is a failure. 01:26:22.370 --> 01:26:23.630 There's no solution. 01:26:23.630 --> 01:26:26.420 We go ahead and return None here. 01:26:26.420 --> 01:26:28.820 What do these functions do? select_unassigned_variable 01:26:28.820 --> 01:26:31.640 is just going to choose a variable not yet assigned. 01:26:31.640 --> 01:26:33.650 So it's going to loop over all the variables. 01:26:33.650 --> 01:26:37.580 And if it's not already assigned, we'll go ahead and just return that variable. 01:26:37.580 --> 01:26:39.750 And what does the consistent function do? 01:26:39.750 --> 01:26:43.010 Well, the consistent function goes through all the constraints. 01:26:43.010 --> 01:26:46.580 And if we have a situation where we've assigned 01:26:46.580 --> 01:26:50.060 both of those values to variables but they are the same, 01:26:50.060 --> 01:26:52.310 well, then that is a violation of the constraint, 01:26:52.310 --> 01:26:54.350 in which case will return False. 01:26:54.350 --> 01:26:56.750 But if nothing is inconsistent, then the assignment 01:26:56.750 --> 01:27:00.060 is consistent and will return True. 01:27:00.060 --> 01:27:02.210 And then all the program does is it calls 01:27:02.210 --> 01:27:05.510 backtrack on an empty assignment, an empty dictionary that 01:27:05.510 --> 01:27:09.890 has no variable assigned and no values yet, save that inside a solution, 01:27:09.890 --> 01:27:12.420 and then print out that solution. 01:27:12.420 --> 01:27:18.012 So by running this now, I can run python schedule0.py. 01:27:18.012 --> 01:27:21.140 And what I get as a result of that is an assignment 01:27:21.140 --> 01:27:22.760 of all these variables to values. 01:27:22.760 --> 01:27:26.300 And it turns out we assign A to Monday, as we would expect, B to Tuesday, 01:27:26.300 --> 01:27:28.460 C to Wednesday, exactly the same type of thing 01:27:28.460 --> 01:27:31.490 we were talking about before, an assignment of each of these variables 01:27:31.490 --> 01:27:35.120 to values that doesn't violate any constraints. 01:27:35.120 --> 01:27:38.470 And I had to do a fair amount of work in order to implement this idea myself. 01:27:38.470 --> 01:27:40.220 I had to write the backtrack function that 01:27:40.220 --> 01:27:42.770 went ahead and went through this process of recursively 01:27:42.770 --> 01:27:44.780 trying to do this backtracking search. 01:27:44.780 --> 01:27:46.990 But it turns out the constraint satisfaction problems 01:27:46.990 --> 01:27:49.700 are so popular that there exist many libraries that 01:27:49.700 --> 01:27:52.160 already implement this type of idea. 01:27:52.160 --> 01:27:55.790 Again, as with before, the specific library is not as important as the fact 01:27:55.790 --> 01:27:57.560 that libraries do exist. 01:27:57.560 --> 01:28:00.800 This is just one example of a Python constraint library 01:28:00.800 --> 01:28:04.520 where now, rather than having to do all the work from scratch 01:28:04.520 --> 01:28:08.420 inside a schedule1.py, I'm just taking advantage of a library that implements 01:28:08.420 --> 01:28:10.280 a lot of these ideas already. 01:28:10.280 --> 01:28:13.490 So here, I create a new problem, add variables 01:28:13.490 --> 01:28:15.300 to it with particular domains. 01:28:15.300 --> 01:28:18.410 I add a whole bunch of these individual constraints 01:28:18.410 --> 01:28:22.070 where I call addConstraint and pass in a function describing 01:28:22.070 --> 01:28:23.480 what the constraint is. 01:28:23.480 --> 01:28:26.647 And the constraint basically says, it's a function that takes two variables, 01:28:26.647 --> 01:28:29.690 x and y, and makes sure that x is not equal to y, 01:28:29.690 --> 01:28:33.440 enforcing the idea that these two classes cannot have exams on the same 01:28:33.440 --> 01:28:34.620 day. 01:28:34.620 --> 01:28:37.970 And then for any constraint satisfaction problem, 01:28:37.970 --> 01:28:41.840 I can call getSolutions to get all the solutions to that problem 01:28:41.840 --> 01:28:44.360 and then, for each of those solutions, print out 01:28:44.360 --> 01:28:46.690 what that solution happens to be. 01:28:46.690 --> 01:28:50.540 And if I run python schedule.py, I now see 01:28:50.540 --> 01:28:53.060 there are actually a number of different solutions 01:28:53.060 --> 01:28:54.830 that can be used to solve the problem. 01:28:54.830 --> 01:28:56.780 There are, in fact, six different solutions, 01:28:56.780 --> 01:28:59.510 assignments of variables to values that will give me 01:28:59.510 --> 01:29:04.180 a satisfactory answer to this constraint satisfaction problem. 01:29:04.180 --> 01:29:08.020 So this then was an implementation of a very basic backtracking search 01:29:08.020 --> 01:29:10.750 method where, really, we just went through each of the variables, 01:29:10.750 --> 01:29:14.290 picked one that wasn't assigned, tried the possible values the variable could 01:29:14.290 --> 01:29:15.070 take on. 01:29:15.070 --> 01:29:18.460 And then if it was-- if it worked, if it didn't violate any constraints, 01:29:18.460 --> 01:29:20.140 then we kept trying other variables. 01:29:20.140 --> 01:29:22.760 And if ever we hit a dead end, we had to backtrack. 01:29:22.760 --> 01:29:26.350 But ultimately, we might be able to be a little bit more intelligent about how 01:29:26.350 --> 01:29:29.260 we do this in order to improve the efficiency of how 01:29:29.260 --> 01:29:30.730 we solve these sorts of problems. 01:29:30.730 --> 01:29:32.830 And one thing we might imagine trying to do 01:29:32.830 --> 01:29:34.930 is going back to this idea of inference, using 01:29:34.930 --> 01:29:38.020 the knowledge we know to be able to draw conclusions 01:29:38.020 --> 01:29:41.260 in order to make the rest of the problem-solving process a little bit 01:29:41.260 --> 01:29:42.530 easier. 01:29:42.530 --> 01:29:46.510 And let's now go back to where we got stuck in this problem the first time. 01:29:46.510 --> 01:29:50.500 When we were solving this constraint satisfaction problem, we dealt with B, 01:29:50.500 --> 01:29:54.148 and then we went on to D. And we went ahead and just assigned D to Monday 01:29:54.148 --> 01:29:56.440 because that seemed to work with the assignment so far. 01:29:56.440 --> 01:29:58.780 It didn't violate any constraints. 01:29:58.780 --> 01:30:02.410 But it turned out that, later on, that choice turned out to be a bad one, 01:30:02.410 --> 01:30:06.250 that that choice wasn't consistent with the rest of the values 01:30:06.250 --> 01:30:08.142 that we could take on here. 01:30:08.142 --> 01:30:09.850 And the question is, is there anything we 01:30:09.850 --> 01:30:12.820 could do to avoid getting into a situation like this, 01:30:12.820 --> 01:30:15.370 avoid trying to go down a path that's ultimately not 01:30:15.370 --> 01:30:18.100 going to lead anywhere by taking advantage of knowledge 01:30:18.100 --> 01:30:19.540 that we have initially? 01:30:19.540 --> 01:30:21.880 And it turns out we do have that kind of knowledge. 01:30:21.880 --> 01:30:25.010 We can look at just the structure of this graph so far. 01:30:25.010 --> 01:30:29.000 And we can say that, right now, C's domain, for example, 01:30:29.000 --> 01:30:32.560 contains values Monday, Tuesday, and Wednesday. 01:30:32.560 --> 01:30:37.360 And based on those values, we can say that this graph is not arc-consistent. 01:30:37.360 --> 01:30:39.760 Recall that arc consistency is all about making 01:30:39.760 --> 01:30:43.660 sure that for every possible value for a particular node 01:30:43.660 --> 01:30:46.780 that there is some other value that we are able to choose. 01:30:46.780 --> 01:30:50.770 And as we can see here, Monday and Tuesday are not going to be possible 01:30:50.770 --> 01:30:55.990 values that we can choose for C. They're not going to be consistent with a node 01:30:55.990 --> 01:30:59.000 like B, for example, because B is equal to Tuesday, 01:30:59.000 --> 01:31:01.000 which means that C cannot be Tuesday. 01:31:01.000 --> 01:31:04.780 And because A is equal to Monday, C also cannot be Monday. 01:31:04.780 --> 01:31:09.610 So using that information by making C arc-consistent with A and B, 01:31:09.610 --> 01:31:12.790 we could remove Monday and Tuesday from C's domain 01:31:12.790 --> 01:31:16.730 and just leave C with Wednesday, for example. 01:31:16.730 --> 01:31:20.017 And if we continued to try and enforce arc consistency, 01:31:20.017 --> 01:31:22.600 we'd see there are some other conclusions we can draw as well. 01:31:22.600 --> 01:31:26.660 We see that B's only option is Tuesday, and C's only option is Wednesday. 01:31:26.660 --> 01:31:30.000 And so if we want to make E arc-consistent, 01:31:30.000 --> 01:31:33.370 well, E can't be Tuesday because that wouldn't be arc-consistent with B. 01:31:33.370 --> 01:31:36.640 And E can't be Wednesday because that wouldn't be arc-consistent with C. 01:31:36.640 --> 01:31:40.385 So we can go ahead and say E, and just set that equal to Monday, for example. 01:31:40.385 --> 01:31:42.760 And then we can begin to do this process again and again, 01:31:42.760 --> 01:31:46.840 that in order to make D arc-consistent with B and E, then D would have to be 01:31:46.840 --> 01:31:47.420 Wednesday. 01:31:47.420 --> 01:31:49.090 That's the only possible option. 01:31:49.090 --> 01:31:52.760 And likewise, we can make the same judgments for F and G as well. 01:31:52.760 --> 01:31:56.170 And it turns out that without having to do any additional search, just 01:31:56.170 --> 01:32:00.332 by enforcing arc consistency, we were able to actually figure out 01:32:00.332 --> 01:32:02.290 what the assignment of all the variables should 01:32:02.290 --> 01:32:05.390 be without needing to backtrack at all. 01:32:05.390 --> 01:32:08.710 And the way we did that is by interleaving the search 01:32:08.710 --> 01:32:12.040 process and the inference step by this step of trying 01:32:12.040 --> 01:32:14.140 to enforce arc consistency. 01:32:14.140 --> 01:32:17.050 And the algorithm to do this is often called just the "maintaining 01:32:17.050 --> 01:32:22.060 arc-consistency algorithm," which just enforces arc consistency every time 01:32:22.060 --> 01:32:26.180 we make a new assignment of a value to an existing variable. 01:32:26.180 --> 01:32:28.150 So sometimes we can enforce arc consistency 01:32:28.150 --> 01:32:31.360 using that AC-3 algorithm at the very beginning of the problem 01:32:31.360 --> 01:32:35.080 before we even begin searching in order to limit the domain of the variables 01:32:35.080 --> 01:32:36.820 in order to make it easier to search. 01:32:36.820 --> 01:32:40.510 But we can also take advantage of the interleaving of enforcing 01:32:40.510 --> 01:32:44.055 arc consistency with search such that every time in the search process 01:32:44.055 --> 01:32:46.090 when we make a new assignment, we go ahead 01:32:46.090 --> 01:32:49.570 and enforce arc consistency as well to make sure 01:32:49.570 --> 01:32:53.870 that we're just eliminating possible values from domains whenever possible. 01:32:53.870 --> 01:32:55.130 And how do we do this? 01:32:55.130 --> 01:32:57.640 Well, this is really equivalent to just every time 01:32:57.640 --> 01:33:00.330 we make a new assignment to a variable X, 01:33:00.330 --> 01:33:03.560 we'll go ahead and call our AC-3 algorithm, 01:33:03.560 --> 01:33:06.310 this algorithm that enforces arc consistency on a constraint 01:33:06.310 --> 01:33:07.870 satisfaction problem. 01:33:07.870 --> 01:33:11.890 And we go ahead and call that starting it with a queue not of all of the arcs, 01:33:11.890 --> 01:33:15.250 which we did originally, but just have all of the arcs 01:33:15.250 --> 01:33:18.160 that we want to make arc-consistent with X, this thing 01:33:18.160 --> 01:33:20.560 that we have just made an assignment to, so all 01:33:20.560 --> 01:33:24.940 arcs Y, X where Y is a neighbor of X, something that shares 01:33:24.940 --> 01:33:27.740 a constraint with X, for example. 01:33:27.740 --> 01:33:32.060 And by maintaining our consistency in the backtracking search process, 01:33:32.060 --> 01:33:35.170 we can ultimately make our search process a little bit more efficient. 01:33:35.170 --> 01:33:38.960 And so this is the revised version of this backtrack function. 01:33:38.960 --> 01:33:41.680 Same as before-- the changes here are highlighted in yellow-- 01:33:41.680 --> 01:33:45.490 every time we add a new variable equals value to our assignment, 01:33:45.490 --> 01:33:47.740 we'll go ahead and run this inference procedure, which 01:33:47.740 --> 01:33:49.323 might do a number of different things. 01:33:49.323 --> 01:33:52.870 But one thing it could do is call the maintaining arc-consistency algorithm 01:33:52.870 --> 01:33:56.510 to make sure we're able to enforce arc consistency on the problem. 01:33:56.510 --> 01:34:00.650 And we might be able to draw new inferences as a result of that process, 01:34:00.650 --> 01:34:04.890 get new guarantees of this variable needs to be equal to that value, 01:34:04.890 --> 01:34:05.640 for example. 01:34:05.640 --> 01:34:06.765 That might happen one time. 01:34:06.765 --> 01:34:07.910 It might happen many times. 01:34:07.910 --> 01:34:10.432 And so long as those inferences are not a failure, 01:34:10.432 --> 01:34:12.140 as long as they don't lead to a situation 01:34:12.140 --> 01:34:15.290 where there is no possible way to make forward progress, well, then 01:34:15.290 --> 01:34:18.230 we can go ahead and add those inferences, those new knowledge, 01:34:18.230 --> 01:34:20.840 that new pieces of knowledge I know about what variables 01:34:20.840 --> 01:34:22.370 should be assigned to what values. 01:34:22.370 --> 01:34:26.240 I can add those to the assignment in order to more quickly make forward 01:34:26.240 --> 01:34:29.930 progress by taking advantage of information that I can just deduce, 01:34:29.930 --> 01:34:33.800 information I know based on the rest of the structure of the constraint 01:34:33.800 --> 01:34:35.292 satisfaction problem. 01:34:35.292 --> 01:34:37.250 And the only other change I'll need to make now 01:34:37.250 --> 01:34:40.460 is if it turns out this value doesn't work, well, then down here, 01:34:40.460 --> 01:34:44.330 I'll go ahead and need to remove not only variable equals value but also any 01:34:44.330 --> 01:34:48.660 of those inferences that I made, remove that from the assignment as well. 01:34:48.660 --> 01:34:52.670 And so here then we're often able to solve the problem by backtracking less 01:34:52.670 --> 01:34:56.330 than we might originally have needed to just by taking advantage of the fact 01:34:56.330 --> 01:34:58.700 that every time we make a new assignment of one variable 01:34:58.700 --> 01:35:03.200 to one value, that might reduce the domains of other variables as well. 01:35:03.200 --> 01:35:06.710 And we can use that information to begin to more quickly draw conclusions 01:35:06.710 --> 01:35:10.740 in order to try and solve the problem more efficiently as well. 01:35:10.740 --> 01:35:12.770 And it turns out there are other heuristics 01:35:12.770 --> 01:35:16.460 we can use to try and improve the efficiency of our search process 01:35:16.460 --> 01:35:17.120 as well. 01:35:17.120 --> 01:35:20.900 And it really boils down to a couple of these functions that I've talked about, 01:35:20.900 --> 01:35:23.550 but we haven't really talked about how they're working. 01:35:23.550 --> 01:35:28.190 And one of them is this function here, select unassigned variable 01:35:28.190 --> 01:35:31.550 where we're selecting some variable in the constraint satisfaction problem 01:35:31.550 --> 01:35:33.540 that has not yet been assigned. 01:35:33.540 --> 01:35:36.260 So far, I've sort of just been selecting variables at random, 01:35:36.260 --> 01:35:39.170 just like picking one variable and one unassigned variable 01:35:39.170 --> 01:35:41.420 in order to decide, all right, this is the variable 01:35:41.420 --> 01:35:44.365 that we're going to assign next, and then going from there. 01:35:44.365 --> 01:35:47.240 But it turns out that by being a little bit intelligent, by following 01:35:47.240 --> 01:35:50.630 certain heuristics, we might be able to make the search process much more 01:35:50.630 --> 01:35:54.050 efficient just by choosing very carefully which 01:35:54.050 --> 01:35:56.660 variable we should explore next. 01:35:56.660 --> 01:36:01.310 So some of those heuristics include the Minimum Remaining Values, or MRV 01:36:01.310 --> 01:36:03.440 heuristic, which generally says that if I 01:36:03.440 --> 01:36:06.080 have a choice between which variable I should select, 01:36:06.080 --> 01:36:09.200 I should select the variable with the smallest domain, 01:36:09.200 --> 01:36:12.680 the variable that has the fewest number of remaining values left, 01:36:12.680 --> 01:36:16.010 with the idea being if there are only two remaining values left, well, 01:36:16.010 --> 01:36:19.670 I may as well prune one of them very quickly in order to get to the other 01:36:19.670 --> 01:36:24.395 because one of those two has got to be the solution if a solution does exist. 01:36:24.395 --> 01:36:28.790 And sometimes, minimum remaining values might not give a conclusive result 01:36:28.790 --> 01:36:32.180 if all the nodes have the same number of remaining values, for example. 01:36:32.180 --> 01:36:34.970 And in that case, another heuristic that can be helpful to look at 01:36:34.970 --> 01:36:36.860 is the degree heuristic. 01:36:36.860 --> 01:36:39.350 The degree of a node is the number of nodes 01:36:39.350 --> 01:36:42.620 that are attached to that node, the number of nodes that are constrained 01:36:42.620 --> 01:36:44.117 by that particular node. 01:36:44.117 --> 01:36:46.200 And if you imagine which variable should I choose, 01:36:46.200 --> 01:36:48.450 should I choose a variable that has a high degree that 01:36:48.450 --> 01:36:50.990 is connected to a lot of different things or a variable 01:36:50.990 --> 01:36:54.240 with a low degree that is not connected to a lot of different things? 01:36:54.240 --> 01:36:57.410 Well, it can often make sense to choose the variable that 01:36:57.410 --> 01:36:59.450 has the highest degree, that is connected 01:36:59.450 --> 01:37:02.930 to the most other nodes as the thing you would search first. 01:37:02.930 --> 01:37:04.200 Why is that the case? 01:37:04.200 --> 01:37:07.670 Well, it's because by choosing a variable with a high degree, that 01:37:07.670 --> 01:37:11.210 is immediately going to constrain the rest of the variables more, 01:37:11.210 --> 01:37:13.340 and it's more likely to be able to eliminate 01:37:13.340 --> 01:37:15.830 large sections of the state-space that you 01:37:15.830 --> 01:37:18.140 don't need to search through at all. 01:37:18.140 --> 01:37:20.510 So what could this actually look like? 01:37:20.510 --> 01:37:22.680 Let's go back to this search problem here. 01:37:22.680 --> 01:37:25.430 In this particular case, I've made an assignment here. 01:37:25.430 --> 01:37:26.940 I've made an assignment here. 01:37:26.940 --> 01:37:30.040 And the question is, what should I look at next? 01:37:30.040 --> 01:37:33.530 And according to the minimum remaining values heuristic, what I should choose 01:37:33.530 --> 01:37:37.370 is the variable that has the fewest remaining possible values. 01:37:37.370 --> 01:37:39.950 And in this case, that's this node here, node C 01:37:39.950 --> 01:37:42.890 that only has one variable left in this domain, which, in this case, 01:37:42.890 --> 01:37:45.800 is Wednesday, which is a variable reas-- very reasonable choice 01:37:45.800 --> 01:37:49.430 of a next assignment to make because I know it's the only option, for example. 01:37:49.430 --> 01:37:52.770 I know that the only possible option for C is Wednesday. 01:37:52.770 --> 01:37:55.940 So I may as well make that assignment and then potentially explore 01:37:55.940 --> 01:37:58.370 the rest of the space after that. 01:37:58.370 --> 01:38:00.700 But meanwhile, at the very start of the problem 01:38:00.700 --> 01:38:04.160 when I didn't have any knowledge of what nodes should have what values yet, 01:38:04.160 --> 01:38:08.030 I still had to pick what node should be the first one that I try and assign 01:38:08.030 --> 01:38:08.800 a value to. 01:38:08.800 --> 01:38:12.140 And I arbitrarily just chose the one at the top, node A, originally. 01:38:12.140 --> 01:38:14.195 But we can be more intelligent about that. 01:38:14.195 --> 01:38:16.670 And we can look at this particular graph. 01:38:16.670 --> 01:38:19.430 All of them have domains of the same size, domain of size 3, 01:38:19.430 --> 01:38:22.460 so minimum remaining values doesn't really help us there. 01:38:22.460 --> 01:38:25.970 But we might notice that node E has the highest degree. 01:38:25.970 --> 01:38:28.140 It is connected to the most things. 01:38:28.140 --> 01:38:30.980 And so perhaps it makes sense to begin our search, 01:38:30.980 --> 01:38:33.278 rather than starting at node A at the very top, start 01:38:33.278 --> 01:38:36.070 with the node with the highest degree, start by searching from node 01:38:36.070 --> 01:38:39.620 E. Because from there, that's going to much more easily allow 01:38:39.620 --> 01:38:42.080 us to enforce the constraints that are nearby, 01:38:42.080 --> 01:38:44.570 eliminating large portions of the search space 01:38:44.570 --> 01:38:46.550 that I might not need to search through. 01:38:46.550 --> 01:38:49.040 And in fact, by starting with E, we can immediately 01:38:49.040 --> 01:38:50.527 then assign other variables. 01:38:50.527 --> 01:38:53.360 And following that, we can actually assign the rest of the variables 01:38:53.360 --> 01:38:56.450 without needing to do any backtracking at all even if I'm not 01:38:56.450 --> 01:38:58.070 using this inference procedure. 01:38:58.070 --> 01:39:00.560 Just by starting with a node that has a high degree, 01:39:00.560 --> 01:39:03.730 that is going to very quickly restrict the values 01:39:03.730 --> 01:39:06.130 that other nodes can take on. 01:39:06.130 --> 01:39:08.560 So that then is how we can go about selecting 01:39:08.560 --> 01:39:11.050 an unassigned variable in a particular order 01:39:11.050 --> 01:39:12.935 rather than randomly picking a variable. 01:39:12.935 --> 01:39:15.310 If we're a little bit intelligent about how we choose it, 01:39:15.310 --> 01:39:17.260 we can make our search process much, much 01:39:17.260 --> 01:39:19.240 more efficient by making sure we don't have 01:39:19.240 --> 01:39:22.180 to search through portions of the search space that ultimately 01:39:22.180 --> 01:39:23.727 aren't going to matter. 01:39:23.727 --> 01:39:25.810 The other variable we haven't really talked about, 01:39:25.810 --> 01:39:29.890 the other function here is this domain values function, this domain values 01:39:29.890 --> 01:39:32.500 function that takes a variable and gives me back 01:39:32.500 --> 01:39:37.010 a sequence of all of the values inside of that variable's domain. 01:39:37.010 --> 01:39:40.260 The naive way to approach it is what we did before, which is just go in order, 01:39:40.260 --> 01:39:42.978 go Monday, then Tuesday, then Wednesday. 01:39:42.978 --> 01:39:44.770 But the problem is that going in that order 01:39:44.770 --> 01:39:48.010 might not be the most efficient order to search in, that sometimes it 01:39:48.010 --> 01:39:53.450 might be more efficient to choose values that are likely to be solutions first 01:39:53.450 --> 01:39:55.550 and then go to other values. 01:39:55.550 --> 01:39:59.260 Now, how do you assess whether a value is likelier to lead to a solution 01:39:59.260 --> 01:40:01.420 or less likely to lead to a solution? 01:40:01.420 --> 01:40:05.260 Well, one thing you can take a look at is how many 01:40:05.260 --> 01:40:07.510 constraints get added, how many things get removed 01:40:07.510 --> 01:40:11.350 from domains as you make this new assignment of a variable 01:40:11.350 --> 01:40:12.680 to this particular value. 01:40:12.680 --> 01:40:17.390 And the heuristic we can use here is the least constraining value heuristic, 01:40:17.390 --> 01:40:20.140 which is the idea that we should return variables in order 01:40:20.140 --> 01:40:24.040 based on the number of choices that are ruled out for neighboring values. 01:40:24.040 --> 01:40:27.610 And I want to start with the least constraining value, the value that 01:40:27.610 --> 01:40:31.270 rules out the lea-- fewest possible options. 01:40:31.270 --> 01:40:34.450 And the idea there is that if all I care about doing 01:40:34.450 --> 01:40:39.340 is finding a solution, if I start with a value that rules out 01:40:39.340 --> 01:40:42.580 a lot of other choices, I'm ruling out a lot of possibilities 01:40:42.580 --> 01:40:46.330 that maybe is going to make it less likely that this particular choice 01:40:46.330 --> 01:40:47.650 leads to a solution. 01:40:47.650 --> 01:40:49.840 Whereas on the other hand, if I have a variable 01:40:49.840 --> 01:40:53.350 and I start by choosing a value that doesn't rule out very much, 01:40:53.350 --> 01:40:56.470 well, then I still have a lot of space where there might be a solution 01:40:56.470 --> 01:40:57.710 that I could ultimately find. 01:40:57.710 --> 01:41:00.460 And this might seem a little bit counterintuitive and a little bit 01:41:00.460 --> 01:41:03.610 at odds with what we were talking about before where I said, when you're 01:41:03.610 --> 01:41:07.540 picking a variable, you should pick the variable that is going to have 01:41:07.540 --> 01:41:09.467 the fewest possible values remaining. 01:41:09.467 --> 01:41:11.800 But here, I want to pick the value for the variable that 01:41:11.800 --> 01:41:13.360 is the least constraining. 01:41:13.360 --> 01:41:16.240 But the general idea is that when I am picking a variable, 01:41:16.240 --> 01:41:18.910 I would like to prune large portions of the search space 01:41:18.910 --> 01:41:22.150 by just choosing a variable that is going to allow me to quickly eliminate 01:41:22.150 --> 01:41:23.820 possible options. 01:41:23.820 --> 01:41:26.070 Whereas here, within a particular variable, 01:41:26.070 --> 01:41:29.080 as I'm considering values that that variable could take on, 01:41:29.080 --> 01:41:31.570 I would like to just find a solution. 01:41:31.570 --> 01:41:33.850 And so what I want to do is ultimately choose 01:41:33.850 --> 01:41:37.900 a value that still leaves open the possibility of me finding a solution 01:41:37.900 --> 01:41:39.220 to be as likely as possible. 01:41:39.220 --> 01:41:43.000 By not ruling out many options, I leave open the possibility 01:41:43.000 --> 01:41:47.290 that I can still find a solution without needing to go back later and backtrack. 01:41:47.290 --> 01:41:50.560 So an example of that might be, in this particular situation here, 01:41:50.560 --> 01:41:54.550 if I am trying to choose a variable for-- a value for node C here, 01:41:54.550 --> 01:41:56.983 that C is equal to either Tuesday or Wednesday. 01:41:56.983 --> 01:41:59.650 We know it can't be Monday because it conflicts with this domain 01:41:59.650 --> 01:42:02.180 here where we already know that A is Monday. 01:42:02.180 --> 01:42:04.540 So C must be Tuesday or Wednesday. 01:42:04.540 --> 01:42:07.330 And the question is, should I try Tuesday first, 01:42:07.330 --> 01:42:09.310 or should I try Wednesday first? 01:42:09.310 --> 01:42:12.490 And if I try Tuesday, what gets ruled out? 01:42:12.490 --> 01:42:14.800 Well, one option gets ruled out here. 01:42:14.800 --> 01:42:16.990 A second option gets ruled out here. 01:42:16.990 --> 01:42:18.910 And a third option gets ruled out here. 01:42:18.910 --> 01:42:22.120 So choosing Tuesday would rule out three possible options. 01:42:22.120 --> 01:42:23.830 And what about choosing Wednesday? 01:42:23.830 --> 01:42:26.350 Well, choosing Wednesday would rule out one option here, 01:42:26.350 --> 01:42:28.700 and it would rule out one option there. 01:42:28.700 --> 01:42:30.050 And so I have two choices. 01:42:30.050 --> 01:42:32.680 I can choose Tuesday that rules out three options 01:42:32.680 --> 01:42:34.930 or Wednesday that rules out two options. 01:42:34.930 --> 01:42:38.620 And according to the least constraining value heuristic, what I should probably 01:42:38.620 --> 01:42:41.260 do is go ahead and choose Wednesday, the one that rules out 01:42:41.260 --> 01:42:44.050 the fewest number of possible options, leaving open 01:42:44.050 --> 01:42:47.150 as many chances as possible for me to eventually find 01:42:47.150 --> 01:42:49.510 the solution inside of the state-space. 01:42:49.510 --> 01:42:51.560 And ultimately, if you continue this process, 01:42:51.560 --> 01:42:55.690 we will find a solution, an assignment of variables 01:42:55.690 --> 01:42:59.410 to values that allows us to give each of these exams-- 01:42:59.410 --> 01:43:02.920 each of these classes an exam date that doesn't conflict 01:43:02.920 --> 01:43:07.390 with anyone that happens to be enrolled in two classes at the same time. 01:43:07.390 --> 01:43:09.670 So the big takeaway now with all of this is 01:43:09.670 --> 01:43:12.970 that there are a number of different ways we can formulate a problem. 01:43:12.970 --> 01:43:15.700 The ways we've looked at today are we can formulate a problem 01:43:15.700 --> 01:43:18.830 as a local search problem, a problem where we're looking at a current node 01:43:18.830 --> 01:43:21.580 and moving to a neighbor based on whether that neighbor is 01:43:21.580 --> 01:43:24.400 better or worse than the current node that we are looking at. 01:43:24.400 --> 01:43:26.830 We looked at formulating problems as linear programs 01:43:26.830 --> 01:43:30.130 where just by putting things in terms of equations and constraints, 01:43:30.130 --> 01:43:33.100 we're able to solve problems a little bit more efficiently. 01:43:33.100 --> 01:43:36.790 And we saw formulating a problem as a constraint satisfaction problem, 01:43:36.790 --> 01:43:39.370 creating this graph of all of the constraints 01:43:39.370 --> 01:43:42.490 that connect to variables that have some constraint between them, 01:43:42.490 --> 01:43:47.530 and using that information to be able to figure out what the solution should be. 01:43:47.530 --> 01:43:49.418 And so the takeaway of all of this now is 01:43:49.418 --> 01:43:51.710 that if we have some problem in artificial intelligence 01:43:51.710 --> 01:43:54.157 that we would like to use AI to be able to solve them, 01:43:54.157 --> 01:43:56.740 whether that's trying to figure out where hospitals should be, 01:43:56.740 --> 01:43:59.020 or trying to solve the traveling salesman problem, 01:43:59.020 --> 01:44:01.750 and trying to optimize productions, and costs, and whatnot, 01:44:01.750 --> 01:44:04.520 or trying to figure out how to satisfy certain constraints, 01:44:04.520 --> 01:44:07.690 whether that's in a Sudoku puzzle, or whether that's in trying to figure out 01:44:07.690 --> 01:44:11.230 how to schedule exams for a university, or any number of a wide variety 01:44:11.230 --> 01:44:14.620 of types of problems, if we can formulate that problem as one 01:44:14.620 --> 01:44:16.120 of these sorts of problems, 01:44:16.120 --> 01:44:18.820 then we can use these known algorithms, these algorithms 01:44:18.820 --> 01:44:21.850 for enforcing arc consistency and backtracking search, 01:44:21.850 --> 01:44:24.400 these hill-climbing and simulated annealing algorithms, 01:44:24.400 --> 01:44:27.460 these simplex algorithms and interior-point algorithms that 01:44:27.460 --> 01:44:29.440 can be used to solve linear programs, that we 01:44:29.440 --> 01:44:33.610 can use those techniques to begin to solve a whole wide variety of problems 01:44:33.610 --> 01:44:37.910 all in this world of optimization inside of artificial intelligence. 01:44:37.910 --> 01:44:41.080 This was an Introduction to Artificial Intelligence with Python for today. 01:44:41.080 --> 01:44:43.190 We will see you next time.