实施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

满意条款的最大数量不是我们想要的吗？

是的，我们正在寻找满足最大条款数量的作业（最好是所有条款）。为此，我们问自己：“在翻转目标时，哪个单个变量将使我们最接近这个目标？”然后翻转。

在我看来，我们正在尝试使用解决方案或近似值来找到解决方案。

使用该解决方案是，如果我们问“多个翻转的哪种组合会带来最佳结果？”还是简单地“哪个任务是最好的？”。但是，这不是我们正在做的事情，我们只在向前迈出一步。使用解决方案的近似值似乎是一个准确的描述。但是，这没什么错。这就是贪婪策略的工作方式。

生成一个具有所有可能翻转的状态空间，并搜索空间以获得最佳近似目标状态的字面空间。

正确的。