conflict - 4 皇后，最小冲突

Question

我想要一些有关min-conflicts algorithm 的帮助。

  A B C D
1 _ _ Q Q
2 Q _ _ _
3 _ _ _ _
4 _ Q _ _

如果我们在这一点上，

• 算法会随机选择移动其中一个C还是D因为它们都产生相同数量的冲突（C与 冲突D，D与 冲突C），
• 还是它会选择D，因为我们可以移动的最佳位置C在第 3 行，这将导致 1 个冲突，如果我们选择D并将其移动到第 3 行，将导致 0 个冲突。

Answer 1

维基百科页面的相关行：

 var <-- a randomly chosen variable from the set of conflicted variables CONFLICTED[csp]
 value <-- the value v for var that minimizes CONFLICTS(var,v,current,csp)
 set var = value in current_state

1. var表示随机选择的皇后 C 或 D 的位置。
2. 设置var为所述女王的位置，以最小化考虑到董事会的其余部分的冲突

所以，这是你的第一选择，“算法随机选择移动 C 或 D ...”，而不是“因为它们都产生相同数量的冲突”。C 或 D，因为它们参与一个或多个冲突。

它确实提到“如果有多个值具有最少的冲突，它会随机选择一个。” 一旦您了解了算法的基本公式，似乎可能会有这种修改，也可以认为是最小约束搜索。