行き止まりで戻って探し直す
バックトラックとは、行き止まりに着いたら直前の選択に戻り、別の候補を試す探し方です。Prolog は答えを探すとき、いつもこの方法を使います。
駅から駅へ行く経路を考えます。分かれ道で一方を選び、行き止まりなら分かれ道に戻って、もう一方を試します。この動きを Prolog がどう自動でやるのかを見ます。
このレッスンのゴール
メモ
Prolog が行き詰まったとき、戻って別の候補を試すことを説明できる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| リスト | 値を順に並べたもの | [a, b, c] |
| 先頭と残り | リストを最初の1つと、残りに分ける形 | [H|T] |
| 選択点 | 候補が複数あり、選び直せる場所 | |
| バックトラック | 失敗したとき、選択点に戻って別の候補を試すこと | |
| 探索 | 条件に合う答えを、候補から探すこと |
学生が入力するセルは、このプレビューでは空白です。
リストは先頭と残りに分けられる
リストは、角かっこの中に値を並べて書きます。[10, 20, 30] は3つの値のリストです。
[H|T] と書くと、リストを先頭と残りに分けられます。H は最初の1つ、T は残りのリストです。リストを扱う規則は、この形を使って書きます。
例: リストを足し算する規則
% 空のリストの合計は 0 です。
total([], 0).
% 先頭 H と、残りの合計 Rest を足します。
total([H|T], Sum) :- total(T, Rest), Sum is Rest + H.リストを先頭と残りに分ける
docker exec prolog swipl -q -g "[H|T] = [10, 20, 30], writeln(H), writeln(T)" -t halt lists.plここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
lists.pl の total で合計を出す
docker exec prolog swipl -q -g "total([3, 4, 5], S), writeln(S)" -t halt lists.plここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
member は候補を順に試す
member(X, List) は、X が List の中にあるかを調べます。X が変数なら、リストの値を先頭から1つずつ X に当てはめます。
つまり member は、選択点を作ります。1つ目の答えのあとに、まだ試していない値が残っている、という状態です。
候補を全部出す
docker exec prolog swipl -q -g "forall(member(X, [a, b, c]), writeln(X))" -t halt lists.plここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
リストを2つに分ける全部の方法
docker exec prolog swipl -q -g "forall(append(X, Y, [1, 2]), (write(X), write(' + '), writeln(Y)))" -t halt lists.plここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
失敗すると直前の選択に戻る
Prolog は、条件を左から順に調べます。ある条件が失敗すると、直前の選択点にバックトラックします。そこで次の候補を試し、また右へ進みます。
候補が尽きた選択点では、さらにその前に戻ります。最初の選択点でも尽きたら、質問全体が失敗です。
例: member の候補を試す
| 手順 | X の候補 | 条件 X >= 2 | 次にすること |
|---|---|---|---|
| 1 | 1 | 失敗 | 選択点に戻って次の候補へ |
| 2 | 2 | 成功 | 右へ進み、答えが決まる |
| 3 | (戻ればさらに 3) | (未使用) | 答えを全部求めるときだけ試す |
学生が入力するセルは、このプレビューでは空白です。
戻りながら探す様子を出力する
docker exec prolog swipl -q -g "member(X, [1, 2, 3]), write(try(X)), nl, X >= 2, writeln(found(X))" -t halt lists.plここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
全部の候補が行き止まりのとき
docker exec prolog swipl -q -g "(member(X, [1, 2, 3]), write(try(X)), nl, X > 5)" -t halt lists.plここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
「戻ると、さっき画面に出した文字も消える」と考える人が多くいます。戻って取り消されるのは、変数の値の選び方だけです。出した文字は残るので、try(1) は消えずに表示されます。
経路探索は選択点の連続である
駅の道を road(A, B). の事実で書くと、経路の規則も短く書けます。path は「A から B まで、通る駅のリスト」です。
分かれ道では、Prolog が選択点を作ります。経路が見つかったら答えを出し、バックトラックで別の経路を探します。
例: 駅から駅への経路
% 例です。このファイルはラボにはありません。
road(hana, kawa).
road(hana, mori).
road(kawa, mori).
road(kawa, umi).
road(mori, umi).
% 着いたら、駅を1つだけ含む経路です。
path(A, A, [A]).
% 次の駅 C へ進み、C から先の経路を足します。
path(A, B, [A|Rest]) :- road(A, C), path(C, B, Rest).
% path(hana, umi, P) の答えは、順に次の3つです。
% [hana,kawa,mori,umi] [hana,kawa,umi] [hana,mori,umi]