了解 MinConflicts 算法

Question

在维基百科中是这样写的 (Min-conflicts algorithm):

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 return 2 还是应该 return 4？换句话说，我们应该只计算这个特定皇后的冲突，还是应该计算棋盘上全局的所有冲突。

维基百科也说

The CONFLICTS function counts the number of constraints violated by a particular object, given that the state of the rest of the assignment is known

但这感觉不对。

Answer 1

"The CONFLICTS function counts the number of constraints violated by a particular object, given that the state of the rest of the assignment is known" but this doesn't feel right.

没错。

  0 1 2 3
0 Q - - -
1 - Q - -
2 - - Q -
3 - - - Q
Here we have 3 conflicts, right?

此处 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)随机returns (0,1)或(2,1)（如果有多个值有最小冲突数，则CONFLICTS取其一随机）。

它不是return(3,1)。

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

CONFLICTS(Q1)随机return秒(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

了解 MinConflicts 算法

Understanding MinConflicts algorithm

algorithm

artificial-intelligence

heuristics

constraint-satisfaction