理解MinConflicts算法

Question

维基百科是这样写的(最小冲突算法):

value <-- the value v for var that minimizes CONFLICTS(var,v,current,csp)

但是这是什么意思呢?

例如，如果我有以下N皇后问题的矩阵:

  0 1 2 3
0 Q - - -
1 - Q - -
2 - - Q -
3 - - - Q

这里有3个冲突，对吧?

如果我们将皇后从位置1,1移动到位置2,3，那么CONFLICTS函数的值是多少呢?

  0 1 2 3
0 Q - - -
1 - - - -
2 - - Q -
3 - Q - Q

CONFLICTS应该返回2还是应该返回4?换句话说，我们应该只计算这个特定皇后的冲突，还是应该计算棋盘上所有的冲突。

维基百科也说

如果赋值的其余部分的状态已知，则CONFLICTS函数计算特定对象违反的约束数

但是这感觉不对

Answer 1

"如果赋值的其余部分的状态是已知的，那么CONFLICTS函数会计算特定对象违反的约束的数量"，但这感觉不对。

它是对的。

  0 1 2 3
0 Q - - -
1 - Q - -
2 - - Q -
3 - - - Q

这里有3个冲突，对吧?

这里CONFLICTED[csp]为[Q0, Q1, Q2, Q3] (Qn为n第1列的皇后)。如果随机选择的变量是Q1:

  0 1 2 3
0 Q 1 - -
1 - Q - -
2 - 1 Q -
3 - 2 - Q

Q1打破了3的约束(它攻击了Q0, Q2, Q3)。

CONFLICTS(Q1)随机返回(0,1)或(2,1)(如果有多个值具有最小冲突数，CONFLICTS随机选择一个)。

不返回(3,1)

  0 1 2 3
0 Q 1 - -
1 - 3 - -
2 - 1 Q -
3 - Q - Q

CONFLICTS(Q1)随机返回(0,1)或(2,1)。

CONFLICTS(var, v, current, csp)考虑一个处于current状态的女王(var)。

---

系统的一个可能演化是:

  0 1 2 3
0 Q 1 - -
1 - Q - -
2 - 1 Q -
3 - 2 - Q
CONFLICTED[csp] = [Q0, Q1, Q2, Q3];
var = Q1
value = (0, 1)

---

  0 1 2 3
0 Q Q - -
1 1 - - -
2 1 - Q -
3 1 - - Q
CONFLICTED[csp] = [Q0, Q1, Q2, Q3];
var = Q0
value = (1, 0)

---

  0 1 2 3
0 1 Q - -
1 Q - - -
2 1 - Q -
3 1 - - Q
CONFLICTED[csp] = [Q0, Q1, Q2, Q3];
var = Q0
value = (2, 0)

同一个var(这里是Q0)可以被多次选中，如果它仍然在CONFLICTED[csp]中。

---

  0 1 2 3
0 - Q 2 -
1 - - 1 -
2 Q - Q -
3 - - 1 Q
CONFLICTED[csp] = [Q0, Q2, Q3];
var = Q2
value = (3, 2)

---

  0 1 2 3
0 - Q - 1
1 - - - 0
2 Q - - 2
3 - - Q Q
CONFLICTED[csp] = [Q2, Q3];
var = Q3
value = (1, 3)

---

  0 1 2 3
0 - Q - -
1 - - - Q
2 Q - - -
3 - - Q -
CONFLICTED[csp] = [];
current_state is a solution of csp