CLPFD ヒューリスティックな工夫

はじめに

自作のN-PrologにCLPFDを搭載しました。制約論理という考え方を理解したかったからです。自分なりに試行錯誤しできるだけ早期に枝刈りをするということを目標に基本部分を開発、搭載しました。しかし、制約論理は奥が深いのです。

単純な例　9queens

以下は単純な例です。9queensを解いています。

:- use_module(clpfd).

nqueens(Queens) :-
    length(Queens, 9),       
    Queens ins 1..9,         
    all_different(Queens),   
    safe(Queens),       
    label(Queens).
    
safe([]).
safe([Q|Rest]) :-
    safe(Rest),
    no_attack(Q, Rest, 1).
    
no_attack(_, [], _).
no_attack(Q, [Q2|Rest], Dist) :-
    Q #\= Q2 + Dist,  
    Q #\= Q2 - Dist,
    Dist1 #= Dist + 1,
    no_attack(Q, Rest, Dist1).

test :- nqueens(X),fail.    

解を表示しないで実行時間を計測、SWI-Prologと比較すると次のようになりました。

SWIに比べて2倍ちょっと遅いですが、それほど悪くはありません。

SWIに勝った！？？？

ところで次の覆面算でSWIはおもいっきり遅いのです。

mask(Wrong,M,Right) :-
    Xs = [W, R, O, N, G, M, I, H, T],
    Xs ins 1..9,
    all_different(Xs),
    Wrong #= 10000*W + 1000*R + 100*O + 10*N + G,
    Right #= 10000*R + 1000*I + 100*G + 10*H + T,
    Wrong * M #= Right,
    label([Wrong,M,Right]).

なんと！N-Prologの方が20倍も高速なのです？なんだそりゃ？　でも、まああのSWIを超えるというのですから
作った本人も驚きです。メジャーリーグで活躍する大谷選手の気分です。しかし・・・

同じ覆面算でも

よくあるsend-more-moneyの覆面算となると結果はがらりと変わります。

send([S,E,N,D,M,O,R,Y]) :-
    Vars = [S,E,N,D,M,O,R,Y],
    Vars ins 0..9,
    all_different(Vars),
    S #\= 0,
    M #\= 0,
    1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E
    #= 10000*M + 1000*O + 100*N + 10*E + Y,
    label(Vars).

SWIは桁違いに高速です。世界レベルの凄さを見た気分です。

ヒューリスティック

どうやらSWIはヒューリスティックな手法を用いているようです。人間がsend_more_moneyの問題を人力で解くときに総当りをするはずがありません。上位の桁から推論して「こうなるはずだ！」という風にして各桁の値を求めていくはずです。SWIはそれを行っているようです。

これはなかなかおもしろい問題です。人間はいかにしたら効率よく問題を解けるのかというのをいつも模索しています。脳の計算能力はデジタルコンピューターには遥かに劣ります。しかし、それをカバーする推論能力はコンピューター以上です。面白いテーマです。いずれじっくり自分でもやってみようと思っています。

でも、今年は積みプラモデルを完成させるのでお楽しみは後回しです。

追記

変数の順番を変えるだけで劇的に高速になります。それにしてもSWIは桁違いに高速ではあるのですが。

さらに桁上がりを含めた各桁の制約式を追加すると高速化しました。