[講義メモ]Theory of Discrete Algorithms(5/11)

今まで取り扱った問題とは別に,新しく3SATをやる.

充足可能性問題 – Wikipedia

詳しくはWikiのSATのページを見てみるとよく分かるけど
CNFの論理式を充足する変数の組を見つけてくる問題.
もちろん小さいCNFなら総当たりとかすれば分かるけどね.

3CNFの例
f = (x1∨x2∨x3) ∧ (¬x1∨x2∨¬x4) ∧ …

時間複雑さを,変数の数nとして T(n) = 1.84^n
という見積りから,いかに指数の底を小さくできるのかという話.
Local Searchを使う.

教科書とか,数学ガールにも出てきたね.








適当にインスタンスを作り,それが正しい解に向かうようにランダムに解を修正していった.
Googleとかで Local Search for 3SAT とか検索するといいよ.

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です