N-PrologにおけるAC-3
N-Prologの開発、拡張もほぼ終えてしばらくノンビリとしようと思っていました。しかし、中途半端になっていたCLPFDのことが気にかかります。AC-3というアルゴリズムのことをしっかり理解したくなりました。そこで手計算で試行錯誤していました。この旅、N-Prolog ver4.36をもってAC-3アルゴリズムを実装し組み込みました。満足感に浸っています。
AC-3
1977年に発表された論文がベースになり改良を加えられたAC-3というのが良く使われているそうです。下記のyoutube動画がとても参考になります。
力ずくで総当たりで生成、検査をすれば簡単な問題ならコンピューターで計算できます。しかし、複雑で解空間が広い問題の場合、効率よく計算をしないといけません。事前に解空間を絞りこんでいく必要があります。それがAC-3です。
N-Prologでの実行例
下記の図はN-Prologで簡単な制約論理式を解いている様子です。Xは1から３までの範囲、Yも１から3までの範囲、Zは１から5までの範囲とします。このときX+Y＋Z=1となるものを求めます。人間なら直感的に１＋１＋１＝３しかないことがわかります。これをコンピューターにやらせるには無駄な探索範囲を削除しないと非効率です。
X -> Y について成り立つXの範囲を調べます。２と３は成り立たないことがわかります。逆方向のY->Xも調べます。次にY->Zについて調べます。2,3,4,5の場合には成り立たないことがわかります。逆も調べます。成り立たない要素を削除します。削除したあとで念のためにその削除後の範囲でも今まで調べてきたものが成立していることを再度調べ直します。
ヒューリスティック
無事、AC-3が実装できたのでnqueens問題のコードをAc-3にかけてみました。解空間はほとんど縮小しません。こういう問題にはAC-3は不向きです。魔法陣も同様です。send_more_moneyパズルも同様です。これらには人間がやるようなヒューリスティックな手法を用いないと効率がよくなりません。
車輪の再発明
車輪の再発明をバカにする人がいます。しかし、やってみるとこれがなかなか頭を酷使するのです。理屈を理解したとしてもそれをどういうデータ構造で実現したらいいのだろう？などなど問題は山のようにありました。これを丁寧に解決してようやくAC-3の動作を試すことができました。深い満足感に浸っています。SWI-PrologなどはCLPFDを極めて高速に解きます。そこには深い洞察、工夫があることがよくわかりました。やってみた甲斐がありました。N-PrologのCLPFDが実用になるかどうかは疑問です。しかし、学習用には使えるでしょう。label述語にAC-3の判定の様子をトレース出力する機能を追加しておきました。
知的探求心を満たしてくれたAC-3とChatGPTに感謝します。目標は達成しました。しばらく作りかけのプラモデルの製作、それとエレキギターでノンビリします。また、お会いしましょう。
https://github.com/sasagawa888/nprolog