人工知能概論 2000 Introduction to Artificial Intelligence 2000 |
,
, updated
人工知能概論 2000 のページへ戻る (back to AI lecture 2000 index page)
------------------------------------------------------------- 9/20(木)晴れ ノート:山崎 3.1 ブラインド探索のまとめ Q1.各サーチ手法(縦型、横型、反復深化法)の探索過程(スタートから下に向 かって、サーチ木(p35図3.1)の各ノードを訪れる順序)をイラストで表せ。 例)・横型 ・縦型 ・反復深化法 cutoff=1,2,3に分けて、イラストを書け。 ・ポイント cutoff = サーチの深さを1つずつ大きくしながら、 縦型サーチを繰り返す。 3.2 ヒューリスティック探索(pp.43-46 , 配布資料、 知能工学ノート(9/4)) ヒューリスティック(Heuristics) ・正しいという裏付けはないが、経験的に正しいと信じられている知識 →サーチのとき、役に立つ知識 9/6,スタートから目標状態(ゴール)までの最短経路(path)を求める。 ex.ゲームの早解き ゴール=エンディング表示 プレイ時間最小 現状態が、ゴールにどれだけ近いか? (pp.43-44) h(x) 〃 を表す(見積もる/推定する)関数 Q2.なぜ、”見積もる”のか? 実際のゴールまでの距離(展開ノード.etc)は、サーチで展開し、 ゴールまでたどりついて初めて確定するから → 展開せずに/するよりも小さいコストで距離やコストを見積もりたい。 3.2.1 山登り法(hill climbing) pp.44-45 アルゴリズム Q3.ブラインドサーチ法との違いはどこか? Step5 : h(n') = min(h(ni)) → 対応する本文の説明をマーク 例:山登り法でのh(x)の例 問題:カーナビ h(x)の例・・・1)ゴールまでの直線距離 2)高速/一般道ごとの平均時速を用いて算出した予想走行時間 山登り法の特徴 ・サーチコスト 小 ・ゴールにたどりつく前にh(n') = min(h(ni))のノードが見つからなくなると, そこから先に進めない → 図3.3(左) アルゴリズムの挙動 霧の中での高度計での登山/下山 3.2.2 最良優先サーチ 山登り法とのちがい → 全ての未展開ノードからh(n') = min(h(ni))を選ぶ。 →図3.4 Q4.両アルゴリズムがStep5でソート(調べる)するノードをそれぞれ (点線で)示せ。 -------------------------------------------------------------------------