Алгоритм GSAT по большей части прост: вы получаете формулу в соединительной нормальной форме и переворачиваете литералы предложений до тех пор, пока не найдете решение, удовлетворяющее формуле, или не достигнете предела max_tries / max_flips и не найдете решения.
Я реализую следующий алгоритм:
procedure GSAT(A,Max_Tries,Max_Flips)
A: is a CNF formula
for i:=1 to Max_Tries do
S <- instantiation of variables
for j:=1 to Max_Iter do
if A satisfiable by S then
return S
endif
V <- the variable whose flip yield the most important raise in the number of satisfied clauses;
S <- S with V flipped;
endfor
endfor
return the best instantiation found
end GSAT
У меня проблемы с интерпретацией следующей строки:
V <- the variable whose flip yield the most important raise in the number of satisfied clauses;
Разве мы не ищем максимальное количество удовлетворенных предложений? Мне кажется, что мы пытаемся использовать решение или приближения к нему, чтобы найти решение.
Я подумал о некоторых способах сделать это, но было бы хорошо услышать другие точки зрения (Предполагается, что, как только переменная перевернута, когда она выбрана):
- Создайте пространство состояний со всеми возможными переворотами и найдите пространство для литерала, который дает наилучшее приближение к целевому состоянию.
- Случайно выберите переменную, которую я переверну, начиная с литералов, которые встречаются чаще.
- Выберите случайный литерал.
источник