Реализация алгоритма GSAT - как выбрать, какой букваль переворачивается?

Question

Алгоритм 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;

Разве максимальное количество удовлетворенных положений о том, что мы ищем? Мне кажется, что мы пытаемся использовать решение или приближения к нему, чтобы найти решение.

Я подумал о некоторых способах сделать это, но было бы неплохо услышать другие точки зрения (предположение состоит в том, что после того, как переменная перевернута после ее выбора.):

• Создайте пространство состояния со всеми возможными переворотами и найдите пространство для буквального, которое приводит к лучшему приближению к состоянию цели.
• Случайно выберите переменную, которую я перевернут, начиная с литералов, которые более распространены.
• Выберите случайный буквальный.

Answer 1

Разве максимальное количество удовлетворенных положений о том, что мы ищем?

Да, мы ищем задание, которое удовлетворяет максимальному количеству пунктов (то есть все они, предпочтительно). И с этой целью мы спрашиваем себя: «Какая единственная переменная приведет нас к этой цели при переворачивании?» а затем переверните это.

Мне кажется, что мы пытаемся использовать решение или приближения к нему, чтобы найти решение.

Использование решения было бы, если бы мы спросили: «Какая комбинация из нескольких листов даст наилучший результат?» Или просто «какое задание будет лучшим?». Однако это не то, что мы делаем, мы смотрим только на шаг вперед. Использование приближения решения кажется точным описанием. Однако в этом нет ничего плохого. Вот как работают жадные стратегии.

Создайте пространство состояния со всеми возможными переворотами и найдите пространство для буквального, которое приводит к лучшему приближению к состоянию цели.

Верно.