Prolog入門(3)

カット

カットは、Prologのバックトラックを制御します。カットは、「目標としてはただちに成功するが、再計算では失敗する」という働きをしますが、さらに後戻り操作に対する副作用として「カットよりも左側にある goal と head の後戻りを行わない」という機能を持ちます。

   head:- goal_a, goal_b, !, goal_c, goal_d.
   head:- goal_p, goal_q, ... .
   head:- goal_x, goal_y, ... .

上の例では、goal_a や goal_bを実行中に失敗した場合は再試行(後戻り)が行われますし、(同じheadの)次の行を試すことも行われます。ただし、一旦 goal_a と goal_b が成功してその右の ! を越えてしまったら、!の左側のゴール( goal_a や goal_b) を再試行したり、次の行(同じ head を持つ節)を実行することは行われなくなります。 goal_c と goal_d の間では再試行が行われますが。

カットによって再試行を行わないことをPrologに伝えることができますが、これには次のような利点があります。

解には無関係な目標をあらかじめ指示できるので、無駄な計算をする必要がなくなる。
後戻りの点を記憶する必要がなくなるので、実行に必要な記憶領域を小さくできる。

カットの一般的使用法

カットは次のような場合をプログラム中に示すために使われます。

この位置に到達したら、ゴールに対して正しい規則を使っている。
別の解を試すことなく、あるゴールを直ちに失敗とすべき。 (failと組み合せて使う)
後戻りによる別の解の探索を停止したい。解が一つしかない時は、一つ解を見付けたらもう後戻りは必要ない。

sumto.pl

sum_to(N,1) :- N =< 1.
sum_to(N,R) :- N1 is N-1, sum_to(N1,R1), R is R1 + N.

sumto(N,1) :- N =< 1, !.
sumto(N,R) :- N1 is N-1, sumto(N1,R1), R is R1 + N.

sumto.pl の実行例

File → Consult で sumto.pl 読み込んだあと
?- sumto(5,X).
X = 15 ;
No
?- sum_to(5,X).
X = 15 ;
X = 16 ;
X = 16 ;
X = 15 ;
X = 13 ;
X = 10 ;
X = 6 ;
X = 1 ;
X = -5 ;

この後、;を入力して後戻りさせる度に延々続く

プログラムの様式としては、カットを使うようりもnotを使用する方がよい、とされています。なぜならば、カットのあるプログラムは人間が読み難いからです。もし、すべてのカットのかわりにnotを使っていいのであれば、プログラムは読みやすくなることでしょう。しかし、実行効率は落ちるかもしれません。

次のプログラムは2行目を実行中に goal_a の２度目の実行をする可能性があります。goal_aが複雑で計算時間がかかる場合はこのプログラムは遅くなります。

head :- goal_a,goal_b.
head :- not(goal_a),goal_c.

goal_a を１一度だけ実行するには、カットをつかって次のように記述できます。

head :- goal_a,!, goal_b.
head :- goal_c.

応用

グラフの経路探索

グラフの経路を探索するプログラムを考えましょう。

一度通った部屋を、再び通らないためには、通った部屋をメモしていく必要があります。「既に通った部屋ならばそこには移動しない」という部分は次の部分です。

    can_go(X,Z),          ← 現在の位置(X)から移動できる新しい部屋(Z)を見つけて
    not(member(Z,Memo)),  ← そこがMemoに載っていなければ
    go(Z,Y,[X|Memo],Ans). ← Xをメモに加えてZに移動し、探索を続ける。

maze.pl

/*
      a--b--c
      |  |  |
   d--e--f--+
   |     |
   g-----h
*/
connected(a,b).
connected(a,e).
connected(b,c).
connected(b,f).
connected(c,f).
connected(d,e).
connected(d,g).
connected(e,f).
connected(f,h).
connected(g,h).

can_go(X,Y) :- connected(X,Y).
can_go(X,Y) :- connected(Y,X).

go(X,X,Memo,[X|Memo]).
go(X,Y,Memo,Ans) :- can_go(X,Z),not(member(Z,Memo)),go(Z,Y,[X|Memo],Ans).

実行例

maze.plをConsultしてから

?- go(a,h,[],P).

P = [h, f, c, b, a] ;

P = [h, g, d, e, f, c, b, a] ;

P = [h, f, b, a] ;

P = [h, g, d, e, f, b, a] ;

P = [h, f, e, a] ;

P = [h, g, d, e, a] ;

No

課題C1

[1] 最大値を求めるプログラムを考えます。これが正しく動作することを確かめなさい。

max.pl

max(X,Y,X) :- X > Y, !.
max(_,Y,Y).

[2]このプログラムでカットを取り去るとどのような不都合が起きますか？例を挙げて説明して下さい。

max2.pl

max(X,Y,X) :- X > Y.
max(_,Y,Y).

[3] また、カットの位置を次のように変更するとどのような不都合が起きますか？例を挙げて説明して下さい。

max3.pl

max(X,Y,X) :- !, X > Y.
max(_,Y,Y).

〆切までに課題提出WEB の「２年ゼミ課題C」の自分のグループ名のところから max.pl, max2.pl, max3.pl を別々に提出して下さい。それぞれコメントに「C1」「C2」「C3」といれること。また、C2とC3に関してはコメント欄に不都合の起きる説明を書いて下さい。

オプション課題C4

次のような一方通行の道でつながれた場所があったとき、指定した場所から指定した場所までの道のりを求めるプログラム path.pl に書きなさい。

      8
  a ---→ b
3↑      ↓2  4
  c ←--- d ---→ e
     5   ↓3
          f----→ g
             6

できた人は、上記と同じ提出先にコメント欄を "C4"として送って下さい。