GSATアルゴリズムの実装 - フリップするリテラルを選択する方法は？

Question

GSATアルゴリズムは、ほとんどの場合、簡単です。式を満たすソリューションを見つけるか、max_tres/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

満足している条項の最大数は、私たちが探しているものではありませんか？

はい、条項の最大数を満たす課題を探しています（それはすべて、できれば）。そしてそのために、私たちは「どの単一の変数がそれをひっくり返すときにこの目標に最も近づくのか？」と自問します。そして、それをひっくり返します。

ソリューションまたは近似を使用してソリューションを見つけようとしているように思えます。

解決策を使用すると、「複数のフリップの組み合わせが最良の結果が得られるのはどの組み合わせですか？」と尋ねられた場合になります。または、単に「どの課題が最善でしょうか？」。しかし、それは私たちがやっていることではなく、一歩先を見ています。ソリューションの近似を使用すると、正確な説明のようです。しかし、それは何の問題もありません。それが貪欲な戦略の仕組みです。

すべての可能なフリップで状態空間を生成し、目標状態に最適な近似をもたらす文字通りのスペースを検索します。

右。