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