Prolog入門(3)

カット

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

   head:- goala, goalb, !, goalc, goald.
   head:- goalp, goalq, ... .
   head:- goalx, goaly, ... .

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

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

カットの一般的使用法

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

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.
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行目を実行中に goala の2度目の実行を する可能性があります。goalaが複雑で計算時間がかかる場合は このプログラムは遅くなります。

head :- goala,goalb.
head :- not(goala),goalc.

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

head :- goala,!, goalb.
head :- goalc.

応用

グラフの経路探索

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

一度通った部屋を、再び通らないためには、通った部屋をメモ していく必要があります。 「既に通った部屋ならばそこには移動しない」という部分は 次の部分です。
    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 の「2年ゼミ課題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"として送って下さい。