Search code examples
algorithmartificial-intelligenceheuristicsconstraint-satisfaction

Understanding MinConflicts algorithm

In wikipedia it is written (Min-conflicts algorithm):

value <-- the value v for var that minimizes CONFLICTS(var,v,current,csp)

but what does that mean?

For example if I have the following matrix for the N queen problem:

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

Here we have 3 conflicts, right?

What would be the value of the CONFLICTS function if we move the queen on position 1,1 to position 2,3 getting:

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

Should CONFLICTS return 2 or should it return 4? In other words should we count only the conflicts of this particular queen or should we count all conflicts globally on the board.

Wikipedia also says

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.

Solution

  • "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.

    It's right.

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

    Here we have 3 conflicts, right?

    Here CONFLICTED[csp] is [Q0, Q1, Q2, Q3] (Qn means queen on n-th column). If the randomly chosen variable is Q1:

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

    Q1 breaks 3 constraints (it attacks Q0, Q2, Q3).

    CONFLICTS(Q1) randomly returns (0,1) or (2,1) (if there is more than one value with a minimum number of conflicts, CONFLICTS chooses one randomly).

    It does not return (3,1).

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

    CONFLICTS(Q1) randomly returns (0,1) or (2,1).

    CONFLICTS(var, v, current, csp) considers a particular queen (var) in the current state.

    A possible evolution of the system is:

      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)

    The same var (here Q0) can be selected multiple times if it remains in 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