人工知能小テスト 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( ,