Reputation: 65
This problem is about CSP w/ backtracking using the following heuristics for variable/value selection:
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.
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].
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].
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