Kungfunk
Kungfunk

Reputation: 65

Constraint Satisfaction Problem - Least constraining value question

This problem is about CSP w/ backtracking using the following heuristics for variable/value selection:

  1. Choose the most constrained variable, if tie go to 2
  2. Choose the most constraining variable, if tie do alphabetical
  3. Choose the least constraining value, if tie do numeric

Assume we have the following variables and domains (there could be more):

A = {0, 1, 2, 3}

B = {0, 1, 2, 3}

C = {0, 1, 2, 3}

w/ the following constraints:

A > B, B > C

Let's assume I have determined that my next assignment is to B, and I'm attempting to choose the least constraining value. All options will eliminate 5 values from the neighbors' values listed above, keeping 3 remaining:

B = 0 -> A = [1, 2, 3] & C = []

B = 1 -> A =[2, 3] & C = [0]

B = 2 -> A = [3] & C = [0, 1]

B = 3 -> A = [] & C = [0, 1, 2]

How does the least constraining value order these options? I can see a few different ways.

  1. It simply counts how many values were eliminated w/ no other edge-case logic. If this is the case, than the above options are all tied, which means the order for B would be [0, 1, 2 3].

  2. It counts how many values were eliminated but handles the case where at least one variable has no values left in its domain. In this case, the order would be [1, 2, 0, 3].

  3. It calculates how many different possible assignments can happen with the neighboring variables, which is different than calculating how many values were eliminated. For example, let's assume A had 2 choices left, and C had 3 choices left. This would mean there are 2 * 3 = 6 possible assignments, w/ only 2 + 3 = 5 values left. However, if A had 4 choices left, but C only had 1 left, than there are 4 * 1 = 4 possible assignments left, but still 4 + 1 = 5 values left. In this case, the ordering would still be [1, 2, 0, 3], but w/ a different reasoning behind it.

Upvotes: 0

Views: 311

Answers (0)

Related Questions