2

ウィキペディアでは、次のように書かれています ( 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 は 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

Q13制約を破る(攻撃するQ0、Q2、Q3)。

CONFLICTS(Q1)ランダムに(0,1)orを返します(2,1)(競合の数が最小の値が複数ある場合は、CONFLICTSランダムに 1 つを選択します)。

戻りません(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（ここでは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
于 2016-11-09T10:37:16.070 に答える