L18: Conflict Recording

Question 1

What is conflict recording?

Answer 1

When a dead end is encountered, establish a reason for the dead-end (in terms of variable assignments). Add a new constraint to stop that dead-end from re-occurring.

This can be viewed as a form of learning, where useful information uncovered by the problem solver is recorded for later use.

Question 2

What is a minimal conflict set?A

Answer 2

Contains no subsets that are also conflict sets

Question 3

How can we improve graph based learning?

Answer 3

Use value based learning, jump-back learning.

Question 4

What are the non-binary forward checking algorithms called?

Answer 4

nFC0
nFC1

Question 5

What is nFC1?

Answer 5

Create binary constraints from non-binary constraints involving the current variable.

Question 6

If a problem is arc consistent, does it have a solution.

Answer 6

No

Question 7

How can we see if a problem does not have a solution?

Answer 7

Path consistency

Question 8

What is strong path consistency?

Answer 8

When there is both arc and path consistency.

Question 9

What is node consistency?

Answer 9

We can assign a value to any one variable consistently.

Question 10

What is arc consistency?

Answer 10

Given a consistent assignment to any one variable, we can extend it to 2 variables consistently.

Question 11

What is path consistency?

Answer 11

Given a consistent assignment to any 2 variables, we can extend it to 3 variables consistently.