2

在维基百科中它是这样写的（最小冲突算法）：

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 函数计算特定对象违反的约束的数量，假设其余分配的状态是已知的

但这感觉不对。

4

1 回答 1

1

“CONFLICTS 函数计算特定对象违反的约束的数量，假设其余分配的状态是已知的”，但这感觉不对。

这是正确的。

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

这里我们有3个冲突，对吧？

这CONFLICTED[csp]是[Q0, Q1, Q2, Q3]（表示第 - 列的Qn皇后）。n如果随机选择的变量是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)考虑该州的特定皇后 ( var) current。

系统可能的演变是：

  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（此处） 。Q0CONFLICTED[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
于 2016-11-09T10:37:16.070 回答