5

問題

私は、SAT 最適化問題の特別なサブセットを見ています。SAT および関連トピックに慣れていない方は、関連するウィキペディアの記事をご覧ください。

TRUE=(a OR b OR c OR d) AND (a OR f) AND ...

NOT はなく、接続詞の標準形です。これは簡単に解決できます。ただし、ステートメント全体を真にするために、真の割り当ての数を最小限に抑えようとしています。その問題を解決する方法が見つかりませんでした。

可能な解決策

私はそれを解決するために次の方法を思いつきました：

  1. 有向グラフに変換し、頂点のサブセットのみにまたがる最小全域木を検索します。エドモンドのアルゴリズムがありますが、それは頂点のサブセットではなく完全なグラフの MST を提供します。
    • 頂点のサブセットの問題を解決する Edmond のアルゴリズムのバージョンがあるのではないでしょうか?
    • 元の問題から他のアルゴリズムで解決できるグラフを作成する方法があるのではないでしょうか?
  2. SAT ソルバー、LIP ソルバー、または徹底的な検索を使用します。この問題を講義資料として使用しようとしているので、これらの解決策には興味がありません。

質問

アイデアやコメントはありますか？うまくいくかもしれない他のアプローチを考え出すことができますか?

4

1 に答える 1

9

この問題もNP 困難です。

ヒッティング セットから東方向の縮小を示すことができます。

ヒッティング セットの問題: 与えられたセットとS1,S2,...,Sn数k: 選択されたサイズSのkセット。[別の定義: それぞれのとの交点は空ではありません]。SisSsSiSiS

リダクション: ヒット セットのインスタンスについては、問題のインスタンスを
構築します。S'i のこれらの要素は、式の変数です。(S1,...,Sn,k)(S'1 AND S'2 And ... S'n,k)S'iSi

証明:
Hitting Set -> この問題: hittins set のインスタンスがある場合、 のSすべての要素に true を代入することにより、式は要素でS満たされます。で。 この問題 -> ヒット セット:割り当てが true であるすべての要素でビルドします [ヒット セット -> この問題と同じ考え]。kS'ivSSiS'i
S

このための最適化問題を探しているため、NP 困難でもあります。正確な解を探している場合は、指数アルゴリズムを試す必要があります。

于 2012-01-17T14:21:51.817 に答える