「充足可能性問題(3-SAT)を解く乱択アルゴリズム」 by Haxe
初雪です。さっき吹雪いてました。てか3か月ほどブログ更新滞ってました(>_<)
統計とか機械学習の勉強も進んでないのですが、今日はリハビリに、また例の 3-SAT ネタでも投下しときます。
半年以上前に『Rで「充足可能性問題(3-SAT)を解く乱択アルゴリズム」』て記事でこんなこと書いています:
新しい言語を覚えるときに、数学ガール 乱択アルゴリズムの「充足可能性問題(3-SAT)を解く乱択アルゴリズム」(p.353)を実装するという癖がついてしましました。
また新しい言語で書いてみました。
今仕事で使っている、Haxe(wikipedia:Haxe)で。
Haxeというのが元々ActionScriptから派生した言語で、基本構文もECMAScriptにほぼ準拠してるので、結局以前に書いた JavaScript 版とかなり近い実装になっちゃいました。今回も焼き直し感が否めないです。
ただ、今までの言語と違う点が1点。
今までの言語(最期の一覧します)は、所謂「スクリプト言語」だったのですが、今回は一応分類上は「コンパイル言語」。今までは言語の動的な性質を利用(eval 関数またはそれに相当するものを利用して文字列を解析・実行等)してきたのですが、今回はそれが使えない*1。
で。
今回は、「クローズ(Clause)を表す文字列を自前で解析」しています。parseClause 関数参照。
てかこの方法は他の言語でも応用できますね。しかも、今までは言語の癖に合わせて入力を少しずつ変えてきたけど、入力形式を統一することも可能ですね。
ちなみに動作は、JavaScript、C++、Java*2 の各プラットフォームで確認しています。
最後に、今までの Rw3sat の実装を一覧列挙。
- Ruby版: https://gist.github.com/960956
- JavaScript版: https://gist.github.com/966408
- CoffeScript版: https://gist.github.com/1000913
- R版: https://gist.github.com/2811277
- Python版: https://gist.github.com/2818831
- Haxe版: https://gist.github.com/4148331
*1:一応、Haxe のコンパイル先を JavaScript にすれば、条件コンパイルや untyped コードを組み合わせて JavaScript のコードも書ける、つまり eval も使えるのですが、クロスプラットフォームで動くものにしたかったので今回は使用していません。
*2:日本語が文字化けしますが、一応動作します。