人工知能 小テスト 11:復習問題

人工知能 小テスト 11:復習問題
2015 年 7 月 10 日(金)
学籍番号:
名前:
問1. 図 1 に示す探索木より深さ優先探索,及び幅優先探索を用い,その各節点の展開順序を下のオ
ープンリストへ手順 3 から記せ.記入の必要のない欄は×を記入する事.また,探索木の S は
START ノード,G は GOAL ノードとする.節の展開は,どちらも左側を優先すること.
手順
オープンリスト
深さ優先探索
幅優先探索
1
S
S
2
a, b
a, b
3
図 1. 探索木
問2.
4
5
図 2 に示すコスト付き探索木より最適探索を用い,G1,G2 の GOAL ノードのいずれか 1 つに到
達するまで探索を行う.この過程で探索する各節点の展開順序を,下のオープンリストへ手順 3
から記せ.ただし,括弧の中は START ノード S からそのノードまでのコストとする.また,記述の
際には,ノードだけでなく,START ノード S からのコストも記入すること.
図 2. コスト付き探索木
手順
オープンリスト
1
S(0)
2
a(2), b(3), c(6)
3
4
5
問3.
3 枚の円盤のハノイの塔において、始状態を終状態に導くプロセスを示せ.円盤は 1 ステップにつ
き 1 枚のみ移動でき,また,どの円盤も,それより小さい円盤の上に置くことができないとする.
図 3. 始状態
問4.
図 4. 終状態
図 5 に示す評価値の与えられたゲームの木より αβ 法を用いて,そのオープンリスト,各接点の αβ
値の変化をそれぞれの表の続きに記入せよ.また,αβ カットの起こる枝について,α カットか β カッ
トかを記入し,さらにどこの枝がカットされるのかを記入せよ.ただし,αβ 値の表記は節点名(下限,
上限)とし, αβ カットの表記はカット名(カットする枝)とすること.
αβ カットの記入例 {α カット(S,a 間の枝)}
探索方法:深さ優先探索
図 5. ゲームの木
手順
オープンリスト
1
S
2
a, b
3
c, d, b
4
g, d, b
5
d, b
6
αβ 値
c(
d(
,
αβ カット
,
), a(
,
), a(
,
), S(
e(
,
)
), b(
,
), S(
)
,
)
,
)
7
8
9
10
e(
,