荒屋真二著 「人工知能概論 （第２版）」 共立出版 2004.10.1
＜Topページ＞ ＜荒屋研究室へ＞
演習問題の解答例（第１～５章） 最終更新：2004.10.1
第１章
演習問題なし
第２章
2.1 水差し問題の状態空間は図2.3 の有向グラフで表すことができた．この図からすべての解を求めよ．
ただし，同じ操作を繰り返す解は除外する．
(0,0) (4,0) (1,3) (4,3) (0,3) (3,0) (3,3) (4,2) (0,2) (2,0)
(0,0) (4,0) (4,3) (0,3) (3,0) (3,3) (4,2) (0,2) (2,0)
(0,0) (4,0) (1,3) (1,0) (0,1) (4,1) (2,3) (2,0)
以下省略 |
2.2 水差し問題の解は複数存在する．それらのなかで操作の数が最も少ない解（最適解）を求めよ．
| (0,0) (0,3) (3,0) (3,3) (4,2) (0,2) (2,0) |
2.3 解が二つ以上あるような迷路問題を作り，縦型探索法と横型探索法で解いてみよ．縦型あるいは横型探索法では問題によっては最適経路が得られない場合があることを確かめよ．
例えば，次のような迷路問題を考えてみよ。横型探索では最適経路が得られるが，縦型探索では得られない。
＜縦型探索＞
＜横型探索＞
|
2.4 本書で述べた縦型探索法はそのままの形では水差し問題や8パズルを解くことはできない．なぜならば，これらの問題には迷路問題のような行き止まりがないため永久に深く探索してしまうからである．この問題点を回避するために縦型探索法を少し修正した縦型反復深化法（depth-first
iterative-deepening）という探索法がある．これらについて調べ，その要点をまとめよ．
| n = 1, 2, 3, ・・・ として，深さ n までの縦型探索をゴールが見つかるまで繰り返し実行する方法である。深さ最小の解を少ないメモリ消費で見つけることができる。 |
2.5 次の探索木を最良優先探索法と山登り法を用いて解き，両者を比較せよ．
 |
＜最良優先探索法＞ ＜山登り法＞
|
2.6 発見的探索法には，本書で述べた方法以外に，ビーム探索法（beam search），反復深化Ａ＊アルゴリズム（iterative-deepening A* algorithm）などがある．これらについて調べ，その要点をまとめよ．
ビーム探索法とは，A＊アルゴリズムにおいて，展開されていない節点を全て保存するのではなく，一定数（ビーム幅）の最良節点のみを保存する方法である。使用メモリの増大を防げるが最適解は保証されなくなる。ビーム幅を１とすると山登り法と同じなる。
反復深化A＊アルゴリズムとは，A＊アルゴリズムにおいて，発見的関数の値がある閾値（しきい値）以上になった節点の先の探索を中止するようにし，ゴールが見つかるまで閾値を徐々に大きくしていく方法である。 |
2.7 Ａ＊アルゴリズムを用いて8パズルを解く場合，次の図の現在状態 p の評価値 f(p)
を 2.4.2項 で述べた方法を用いて求めよ．
 |
h(p) = 0+2+0+1+1+0+0+1 = 5
f(p) = g(p)+h(p) = 3+5 = 8 |
2.8 次のゲーム木に対して，ミニマックス法およびアルファ・ベータ法で探索した場合の探索過程と結果を説明せよ．
第３章
3.1 図3.4のボール渡しプログラムにおいて，同図(b) の初期状態を次のように変えて実行した場合の推論過程を図3.5にならって書け．
1: (person ＾name shiro ＾has nil)
2: (person ＾name saburo ＾has ball)
3: (person ＾name jiro ＾has nil)
4: (person ＾name ichiro ＾has ball)
| ルールは，r1, r3, r2 の順に発火する。競合集合は，{ (r1,4,3), (r3,2,1) },
{ (r3,2,1) }, { (r2,6,7) }, { } と変化する。WM の変化は省略する。 |
3.2 図3.6ではルールr2とr3を省略しているが，それらのルールを実際に書け．
(p r2 (person ^name jiro ^has {<x> <> nil } )
(person ^name saburo ^has nil)
--> (modify 1 ^has nil)
(modify 2 ^has <x>))
(p r3 (person ^name saburo ^has {<x> <> nil } )
(person ^name shiro ^has nil)
--> (modify 1 ^has nil)
(modify 2 ^has <x>)) |
3.3 競合集合CSが次のような場合，OPS5のLEX戦略ではどのインスタンシエーションが選択されるか．ただし，ルールはra, rb, rcの順に書かれており，それらの条件のきつさはすべて同じであるものとする．
(a) CS =｛(ra 2 3), (rb 4 3), (rc 2 4)｝
(b) CS =｛(ra 2 4),(rb 4 1), (rc 2 4)｝
(a) (rb 4 3)
(b) (ra 2 4) |
第４章
4.1 次のような知識を意味ネットワークおよびフレームを用いて表現せよ．
① ピーコはカナリヤである．
② カナリヤは鳥である．
③ 鳥には翼がある．
④ カナリヤの色は黄色である．
⑤ ピーコは1歳である．
4.2 図4.1の意味ネットワークに対して，次のような質問を表す質問ネットワークを作り，部分照合法を適用せよ．
① チワワの人気は何位ですか．
② チワワの性格は人なつこいですか．
4.3 講義室C32やC33はC棟にあり，C棟やD棟は大学敷地にあることを，フレームを用いて表現せよ．
第５章
5.1 英文"The apple is red."を，命題論理および述語論理で記述せよ．
命題論理： p
述語論理：∀x [ apple(x) → red(x) ] |
5.2 次のペアは単一化可能か．可能ならばそのときの変数代入を求めよ．
ただし，x, y, z は変数とする．
① p(x, orange) p(apple, y)
② p(x, y) q(z)
③ p(x, y) p(q(z), r(y))
① x = apple, y = orange
②単一化不可能 （述語が異なるため））
③単一化不可能 （y = r(y) = r(r(y)) = r(r(r(y))) = ・・・ となるため） |
5.3 次の論理式を節形式に変換せよ．ただし，x, y, z は変数とする．
① ∀x∀y∀z [(p(x, y) ∧ q(y, z)) → r(x, z)]
② ～∃x getup(Taro, x)
③ ∀x [(p(x) ∧ q(x)) → (r(x) ∨ (∃y∀z (s(y, z) → t(x, y) ∨ u(z))))]
① ～p(x, y)∨～q(y, z)∨r(x, z)
② ～getup(Taro, x)
③ ～p(x)∨～q(x)∨r(x)∨～s(S1, z)∨t(x, S1)∨u(z) ただし，S1はスコーレム定数 |
5.4 次の問題をホーン節で記述し，SNLによる導出により解け．
「動物を治療できるのは獣医である．獣医になるにはその資格が必要である．花子は獣医の資格をもっている．タマは猫であり，猫は動物である．さて，花子はタマを治療できるだろうか．」
① ～veterinarian(x1)∨～animal(x2)∨can-cure(x1, x2)
② ～has-qualification-of-vet(x3)∨veterinarian(x3)
③ has-qualification-of-vet(Hanako)
④ cat(Tama)
⑤ ～cat(x4)∨animal(x4)
⑥ can-cure(Hanako, Tama) ・・・・・ 証明したい命題
 |
5.5 図5.5 のプログラムにおいて図5.7 の質問に対する答えはどうなるか．
① yes
② X = kazuko; X = masakazu
③ X = masakazu
④ X = kazuko, Y = ichiro; X = masakazu, Y = ichiro; ・・・以下省略
⑤ X = jiro; X = masakazu
⑥ X = jiro |
5.6 「叔父」および「叔母」の定義をPrologで書け．
uncle(X, Y):-brother(X, Z), parent(Z, Y).
aunt(X, Y):-sister(X, Z), parent(Z, Y). |
