理解MinConflicts算法

Question

在维基百科中，它被写成(最小冲突算法)：

值<--使冲突最小化的var值v(var，v，current，csp)

但这意味着什么呢？

例如，如果N皇后问题有以下矩阵：

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

这里有三个冲突，对吧？

如果我们将女王的位置1、1移动到2、3，那么冲突函数的价值是什么：

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

冲突应该返回2还是应该返回4？换句话说，我们应该只计算这位女王的冲突，还是应该把全球所有的冲突都计算在董事会上。

维基百科还说

冲突函数计算特定对象违反的约束数，因为分配的其余部分的状态是已知的。

但这感觉不对。

Answer 1

“如果已知分配的其余状态，冲突函数会计算特定对象违反的约束数”，但这感觉不对。

这是正确的。

0 1 2 3 0 q--1-q-2-q-3-q-q 这里有三个冲突，对吧？

这里CONFLICTED[csp]是[Q0, Q1, Q2, Q3] (Qn意思是n-th列上的女王)。如果随机选择的变量是Q1

0 1 2 3 0 q1--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 q1--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保留在CONFLICTED[csp]中，则可以多次选择相同的CONFLICTED[csp](此处为Q0)。

  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