8 – Improving Backtracking Efficiency

I guess we’ve already seen one optimization. >> How so? >> Well, if I choose the least constraining value for Queensland, we would not have had to back up. Let me show you. We started with Western Australia being orange. Then the Northern territory was green. Since Queensland is not next to Western Australia, I … Read more

7 – Backtracking Search

So which algorithm are we going to show first to solve constraint satisfaction problems? >> Well the stupid one first of course. >> I had to ask. >> Then we’ll add intelligence as we need it. >> Okay, we’ll use simple search. States are defined by the values assigned so far. >> The initial state … Read more

6 – CSP Examples

Besides unary and binary constraints, we could have constraints that involve 3 or more variables or soft constraints like the fact that I prefer to teach on a Tuesday/Thursday schedule. Problems with preference constraints are called constraint optimization problems and are with solving linear programming. >> There are lots of examples of constraint satisfaction problems. … Read more

3 – Constraint Graph

Anyway, unary constraints restrict the value of a given variable, like saying Tasmania can’t be purple. >> Binary constraints relate, at most, two variables. We can represent those with a constraint graph. >> Here’s a constraint graph for our Australia coloring problem. Nodes are the variables, like Western Australia, South Australia, Queensland, etc. Arcs show … Read more

2 – Map Coloring

Map coloring is another classic example of constraint satisfaction. >> We are trying to color this map of Australia, using the minimum number of colors as possible. But making sure that no neighboring regions have the same color. >> I guess if they had the same color, it would be hard to tell where one … Read more

15 – Structured CSPs

Speaking about saving time through deep searching another powerful trick is to look at the structure of the problem and see if we can decompose it to several independent problems. >> For example, Tasmania is independent of the rest of the Australia problem. We can solve it separately. >> Which takes a level off our … Read more

14 – Constraint Propagation Quiz Solution

Here’s the answer. We have several islands on this map, so they can have any of the three colors. However, K2 is constrained to only one color, green, because of the two bordering regions. Finally, the entire network is arc consistent, because we don’t have any regions without a possible color. [BLANK_AUDIO]

12 – Constraint Propagation and Arc Consistency

However, I noticed we could’ve stop our search earlier. >> How? >> At this step we said the Northern Territory in South Australia both had to be blue. >> So? >> But this two regions are adjacent. We know they can’t both be blue. >> I see, for checking propagates information from assigned to unassigned … Read more

11 – Forward Checking

Our next optimization is forward checking. Basically for each unassigned variable. We are going to keep track of the remaining legal values. >> I get it. So, if we ever make a decision that causes an unassigned variable to not be able to have a value. We stop our search and back up. >> Right. … Read more

10 – Backtracking Optimization Quiz Solution

Here are two possible answers. This region is holding a green region and an orange region, so it only has two options for colors. Compared to all other regions, this is the minimum remaining values of those regions. For this region, we can pick the least constraining value which is green in this case. Because … Read more

1 – Introduction

Here at Atlanta we are homes the world’s busiest airport. They have five runways and 2,500 arrivals and departures per day. >> Have you ever wondered how they schedule all those flights? Those runways are putting out a plane every 30 seconds. >> Wow, it turns out this is an example of a classic AI … Read more