Constraint propagation
From 6.034 Wiki
(→Search: the box) |
Current revision (23:39, 18 October 2008) (view source) (→Examples: search) |
||
| Line 112: | Line 112: | ||
|} | |} | ||
| - | And from here, there's nothing left to do but search. | + | And from here, there's nothing left to do but search. Following the ''most constrained first'' principle, you'd start from the cell labeled "2-3", because it's not on the edge, and therefore it has four constraints while the others have three. |
Current revision
This page aims to clarify the terminology that 6.034 uses for constraint propagation.
When you are solving a problem with constraint propagation, you typically have to do two things: reduce domains and search. You've already learned a variety of ways to search, and now there's a variety of ways to reduce domains as well. In addition, we give you recommendations about which methods are best at solving typical problems.
Reducing domains
As you solve a constraint propagation problem, you typically gain information that certain options are no longer available. In a map coloring problem, for example, when you color a state red, you know that red is no longer an option for its neighboring states.
Your options here include:
- Backchecking only
- You never change the domains; you only backtrack when you see that you've already violated a constraint.
- Forward checking
- When a node is assigned a value, you reduce the domains of its neighboring nodes to only include the options that are still possible. If you reduce a domain to 0, you need to backtrack.
- Forward checking with propagation through singletons
- If you reduce a domain to size 1, make an assignment there and forward check from that node as well.
- Forward checking with propagation through reduced domains
- When you reduce a domain, you also see if you can reduce other domains that neighbor it. This can be very computationally expensive.
You can try the Demonstrations, which allow you to compare many of these methods on a map coloring problem.
On a quiz, we'll tell you what strategy to use for domain reduction. But if you're faced with a constraint propagation problem outside of a quiz, we endorse forward checking with propagation through singletons as the method that works best on most problems.
Search
Logic puzzles can often be solved with domain reduction alone, but in the real world you will have to try some assignments and see what works. This is a search problem! So you have some options:
- Breadth-first search is a bad idea here. You're going to waste time exploring every possible assignment when you really just want one solution that works.
- Depth-first search is meant for this kind of problem, where any step gets you closer to your goal. But where do you search first?
- Depth-first search, most constrained first tells you to start searching at the nodes that constrain the most other nodes, because it reduces your remaining search space as much as possible.
- You could of course use other methods such as beam search or A*, which we haven't really discussed in the context of constraint propagation. These would make sense if you have some heuristic estimate of how likely you are to get stuck.
Of these methods, we recommend depth first, most constrained first for most problems.
Examples
Remember the "Elevation" problem from mega-recitation? Let's do it again without the confused terminology.
You're trying to map this hill, where you know the elevations of a few grid cells, and you know that adjacent grid cells differ in height by at most 1.
| 5 | |||
| 2 | |||
| 3 | |||
| 1 | 1 |
How much can you conclude before you have to search?
If you're using backchecking only, then the only thing you're really doing is searching, and there's nothing you can conclude beforehand.
With forward checking, several domains become smaller. (Dashes represent ranges of possible numbers. Bold numbers have been assigned and forward-checked.)
| 1-3 | 4-6 | 5 | 4-6 |
| 2 | 1-3 | 4 | |
| 1-2 | 2-4 | 3 | 2 |
| 1 | 0-2 | 2 | 1 |
This created some singleton domains! So you could assign those values and keep going if you use forward checking with propagation through singletons. The next step is:
| 1-3 | 4-6 | 5 | 4-6 |
| 2 | 3 | 4 | 3 |
| 1-2 | 2-4 | 3 | 2 |
| 1 | 1-2 | 2 | 1 |
Now you can propagate even more through the new singletons:
| 1-3 | 4 | 5 | 4 |
| 2 | 3 | 4 | 3 |
| 1-2 | 2-4 | 3 | 2 |
| 1 | 1-2 | 2 | 1 |
One more time:
| 3 | 4 | 5 | 4 |
| 2 | 3 | 4 | 3 |
| 1-2 | 2-4 | 3 | 2 |
| 1 | 1-2 | 2 | 1 |
That's all you can get before you search using propagation through singletons, but there isn't much left to search.
You could get a little more information if you chose to propagate through all reduced domains, instead of just singletons. What's that 2-4 doing toward the lower left, when it's adjacent to things that can only be 1-2? Given that information, that cell can actually be at most 3.
| 3 | 4 | 5 | 4 |
| 2 | 3 | 4 | 3 |
| 1-2 | 2-3 | 3 | 2 |
| 1 | 1-2 | 2 | 1 |
And from here, there's nothing left to do but search. Following the most constrained first principle, you'd start from the cell labeled "2-3", because it's not on the edge, and therefore it has four constraints while the others have three.
