FLATz

谷口です。

初投稿なので、簡単に自己紹介します。

年齢	もうすぐ30歳
出身地	名古屋
趣味	ビリヤード

仕事のことのほかに、興味のあることに書いてある組合せ最適化について記事を書いていこうと思います。その導入として、組合せ問題について少し紹介します。

組合せ問題

充足可能性問題：SAT（SATisfiability）という問題をご存知でしょうか？

組合せ問題の中では比較的わかりやすい問題のひとつです。

SATとは

    論理式の集合が与えられ、 
    すべての式に対して真を返す変数の組があるかないかを判定する問題。 
    例えば、 
      a,b,cはそれぞれtrue or falseの2値変数とする。 
      (a ∨ b), (￢a ∨ c), (b ∨ ￢c)という論理式の 
      すべてで真を返すa, b, cの組が存在するか。 
             ∧：AND（論理積）∨：OR（論理和）￢：NOT（否定） 

SATそのものは「最適化」と関わる部分はないのですが、 MAX SAT（最大充足可能問題）などSATを基点とした最適化問題はいくつか存在します。

最後に

SATやその応用問題を通して組合せ最適化の世界を紹介をしていきたいと思います。

参考ページ Wikipedia充足可能性問題

この記事に関するお問い合わせはこちら