「非決定性」とは、ある状態のシステムに、ある入力をしたときに、得られる出力とシステムの状態が１通りにはならないことを言う。
たとえば、「第11回Prologの概要」で作ったプログラムで、「?- like(rokuro,X).」の質問をすると、X に該当する犬の名前は１つではなく、幾つも存在した。
有向グラフと、その上の２つの頂点(vertex)を入力し、その間の経路(path)を出力するプログラムを作ろう。
まず、下図のグラフを Prolog の知識として記述しよう。
グラフの矢印をエッジ(edge)という。エッジの知識は、エッジ名、始点名、終点名を１組として記述する。上図のグラフからは下図の知識が作られる。
edge(e1,v1,v2). edge(e2,v1,v3). edge(e3,v1,v4). edge(e4,v2,v5). edge(e5,v3,v5). edge(e6,v3,v6). edge(e7,v4,v6). edge(e8,v5,v7). edge(e9,v6,v7). |
次に、経路を表す知識 path を作ろう。
形式を次のようにする：path(経路,始点名,終点名)。ここで、経路は、エッジ名のリストとする。
一番簡単な場合は、始点名と終点名の間を結ぶエッジが唯一つの場合である。これは、 path([E],V1,V2) :- edge(E, V1, V2). という規則で表すことができる(規則1と呼ぶことにする)。
次に２つ以上のエッジを通過する場合を考える。始点からある１つのエッジを通過したとする。そして、その後の点から終点までの経路とそのエッジを結ぶものが、全体の経路となる。これは、 path([E|P],V1,V2) :- edge(E,V1,Vn), path(P,Vn,V2). という規則で表すことができる(規則2と呼ぶことにする)。
動作確認： たとえば、?- path(P,v3,v7) と実行すると、経路として、P=[e5,e8]lおよびP=[e6,e9]が得られる。
Prolog では、非決定性計算の方法(戦略:strategy)として、縦型探索と「バックトラック」を使っている。縦型探索とは、ある状態から複数の選択肢があるとき、その状態を一時的に記憶しておき、一方を選択して探索を深めるものである。バックトラックは、その一方を選択して探索した後で、記憶していた状態に戻ることである。戻った後は、残りの選択肢を選択し、同様に探索を行う。
Prolog には、バックトラックの機能が備わっている。その様子は、「トレース(trace)」により観察することができる。
例題1 の実行の様子を、トレースで観察しよう。
トレースの手順は次の通りである。
以下に実行例の一部を示す。
[trace] ?- path(P,v3,v6). Call: (7) path(_G313, v3, v6) ? creep ← path の規則は1と2があるが... Call: (8) edge(_G365, v3, v6) ? creep ← 規則1の body を実行 Exit: (8) edge(e6, v3, v6) ? creep ← 規則1の body の成功 Exit: (7) path([e6], v3, v6) ? creep ← 規則1の全体の成功 P = [e6] ; ← セミコロンを押して別解を求める Redo: (8) edge(_G365, v3, v6) ? creep ← 規則1の body を再実行 Fail: (8) edge(_G365, v3, v6) ? creep ← 規則1の body の失敗 Redo: (7) path(_G313, v3, v6) ? creep ← path の規則の再実行 Call: (8) edge(_G365, v3, _L213) ? creep ← 規則2の body(1つめ) を実行 Exit: (8) edge(e5, v3, v5) ? creep ← 規則2の body(1つめ) の成功 Call: (8) path(_G366, v5, v6) ? creep ← 規則2の body(2つめ) を実行 Call: (9) edge(_G368, v5, v6) ? creep ← 規則1の body を実行 Fail: (9) edge(_G368, v5, v6) ? creep ← 規則1の body の失敗 Redo: (9) path(_G366, v5, v6) ? creep ← 規則2の body(2つめ) を再実行 Call: (9) edge(_G368, v5, _L245) ? creap ← 規則2の body(1つめ) を実行 Exit: (9) edge(e8, v5, v7) ? creap ← 規則2の body(1つめ) の成功 Call: (9) path(_G369, v7, v6) ? creep ← 規則2の body(2つめ) を実行 - - - |
Redo と表示されているところは、バックトラックが発生し、処理が戻ってきたところである。Fail の後や、別解の要求(セミコロンの入力)の後に、Redo が生じる。
エッジにコストを付け、経路を求める際、総コスト(コストの総和)を出力するようにしよう。
具体的には、エッジについては、edge(エッジ名, 始点, 終点, コスト) という形式にする。経路については、path(経路, 始点, 終点, コスト)という形式にする。
コストは次の図のように指定しよう。
たとえば、v1 から v7 までを、e2, e6, e9 の経路とするとき、コストは、2 + 1 + 1 = 4 とする。なお、X is 1 + 2 とすると、変数 X には、足し算の計算結果が代入される。
エッジに所要時間を付け、経路を求める際、総所要時間を出力するようにしよう。
時間の記述は、H:M の形式とする。H は時、M は分である。たとえば、1時間30分を要する場合は、1:30 と記述し、2時間5分を要する場合は 2:5 と記述する。
edge と path の第５引数に、所要時間を書き込むように変更せよ。具体的には下図のとおりとする。
時間計算のヒント： 10:20 = H:M というマッチングが可能であり、その結果、H = 10、M = 20 とバインドされる。整数の割り算は // を使う。割り算の余りは mod を使う。たとえば、X is 10 // 3 とすると、X = 3 となる。Y is 5 mod 2 とすると、Y = 1 となる。２つの時間の合計を表す規則 time_add を作っておくと便利である。time_add( H1:M1, H2:M2, H3:M3 ) は、M3 が M1 + M2 の分の値、H3 が H1 + H2 に M1 + M3 の時の値を加えたものとする。H1,M1,H2,M2 は数がバインド済みであるものとする。
エッジに通過可能時刻という条件を付けよう。
ネットワークを辿る際、時刻の概念が加わる。現時刻が、通過可能時刻に満たない場合は、通過可能時刻まで待ち、通過することにする。しかし、現時刻が、通過可能時刻を越えている場合には、通過できないことにする。通過した後は、所要時間を現時刻に加えて、それを新しい現時刻とする。
たとえば、edge(e1,v1,v2,1,0:20,7:5). というエッジは、7時5分に通過可能である。通過後の時刻は、0:20 を加えた 7:25 分になる。通過前時刻が、7時5分に満たない場合は、7時5分まで待った後に通過する。しかし、7時5分を越えている場合は、通過できない。
path は、第5引数が現時刻、第6引数が通過後の時刻を表すものとする。
下図のとおりに通過可能時刻を設定しよう。
実行例： ?- path(P, v1, v7, Cost, 7:00, ArrTm ).を実行すると、P=[e1,e4,e8], Cost=4, ArrTm=10:15という答えと、他2通りが得られる。
ヒント： 現時刻が条件の時刻より早いことをチェックする規則 time_lt( H1:M1, H2:M2 ) を作っておくと便利である。たとえば、?- time_lt( 8:00, 9:00 ). は Yes、?- time_lt( 8:00, 8:05 ). は Yes となる。H1 < H2 が成り立つことや、H1==H2 のときに M1 < M2 が成り立つことが条件となる。
上記のネットワークでは、１つのエッジに、１つの通過条件しか存在しない。複数の通過条件を与えることは簡単で、edge(e1,v1,v2,…).の「…」部分を変えた事実を必要なだけ追加すれば良い。
各 edge で、既に記載している時刻の後に、2 時間おきに23:59まで、通過可能であるように事実を追加しよう。たとえば、e1 は、7:05 の他に、9:05, 11:05, 13:05, 17:05, 19:05, 21:05, 23:05 に通過可能である。もっと具体的に言えば、 edge(e1,v1,v2,1,0:20,9:05). edge(e1,v1,v2,1,0:20,11:05). … というように、事実を追加する。
次の質問をしてみよう。
プログラム作成のコツ(カット & ペースト)： emacs で、C-k (コントロールキーを押しながら k )を押すと、カーソルより行末までが消去される。続けてもう一度 C-k を押すと改行コードが消去される。さらに続けて、C-y を押すと、消去した部分が挿入される。さらに続けて、C-y を押すと、同じものが挿入される。C-y を押すのは、カーソルを移動させた後でも有効である。効率よくプログラムを作成しよう。
Ｑ. 演習の Web ページを家に帰ってからも読むには？
Ａ．演習室で、Web ページをダウンロードし、メモリスティックに入れて、家に持ち帰ってください。
以下を Linux コンソール上で実行してください。
wget -r http://unicorn.ike.tottori-u.ac.jp/tokuhisa/himitsu/200804-enshu3m/
unicorn.ike.tottori-u.ac.jp というディレクトリができるので、そのファイル一式を持ち帰ってください。
Ｑ．Windows の SWI-Prolog で日本語を使うには？
Ａ．Windows の SWI-Prolog では、UTF-8 という文字コードを使うことで日本語が使用できます。
UTF-8を用いたプログラムファイル：まず、Prolog のプログラムファイルを、「メモ帳(Notepad)」で開きます。次に、「名前を付けて保存」を選択します。次に、ウインドウの一番下に「文字コード(E)」という枠があるので、そこで「UTF-8」を選択します。
課題の変更：課題では、学校の計算機を想定していますので、EUCコードを前提にしています。したがって、漢字などの全角文字は、２バイトコードで扱います。ダブルコーテーションで囲んだ文字列は、1 バイトコードのリストになっています。ところが、Windows の SWI-Prolog は、UTF-8 で書かれたプログラムにおいて、ダブルコーテーションで囲んだ文字列を、1つの文字に1つの文字コードとしたリストに変換します。したがって、先頭の1文字や最後の1文字を抽出するという課題にあった規則は、1つのコードを得るようにします。