Понимание 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 получение:

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

Следует ли КОНФЛИКТЫ вернуть 2 или он должен вернуть 4? Другими словами, следует ли считать только конфликты этой конкретной королевы или мы должны считать все конфликты глобально на борту.

Википедия также говорит

Функция КОНФЛИКТЫ подсчитывает количество ограничений, нарушенных конкретным объектом, учитывая, что состояние остальной части задания известно

, но это не хорошо чувстовать.

Answer 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 выбирает один случайным образом).

It не возвращение (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