講義ノート
-------------------------------------------------------------------------------
１０／１３（金）

前期末テスト返却
平均７２．５（前回６０．１）
ＭＡＸ　９１
ＭＩＮ　５５
前期末成績
（テスト点の和＋ノート点）／２
ノート提出候補者（今回テストor前期末成績６０未満）
今回のノート加点法
前期中間テスト＋ノート点≦６０

＜テスト解説＞
１．
（１）ｐ24図2.1
図　計算機の中での内部世界
　　~~~~~~-＞を図で明示する
文　１）定式化・・・本質的な部分を抽出し

（２）pp21〜23
中学生の答案　５点
１）、２）、３）を小問（１）に対応付ける
１）木の本数をｘ本とすると問題文は２ｘ＝１０
問題文の世界（の記述）と（数学的な）定式化との対応関係＋問題文の制約の定
式化
２）方程式を数学的に解く
３）数学的な変形で得た解を、問題文の世界の記述に戻す

２．
（１）p31、p33
部分問題を繰り返し分割し、各部分問題を解く。
各部分問題の解の和でもとの解を求める。
（２）上問（１）の説明と対応させて解く。
１）全体の行程を部分問題に分ける（差異の大きさに応じて）」５点
２）各部分問題を差異の大きい順に再帰的／階層的に解決する」２点
３）各部分問題の差異に対して適切な手段を選ぶ−＞（３）手段・目標表」３点

（３）手段目標表
ｐ33
ある目標においてその目標と現状態との差異を減少させるのにどの手段が有効か
を示した表

手段＼差異｜〜１０００｜１０００〜１００｜１００〜１０｜１０〜１｜以下

（その２）
３
（１）図略

（２）アルゴリズムのステップ実行してサーチ木を作っているか？
１）展開済みノード	Ｓ−＞リストＬ２
２）未展開ノード	Ｂ−＞リストＬ１

（３）
Ｌ１・・・未展開ノードの集合」５点
Ｌ２・・・展開済みノードの集合の展開の逆順（＋１点）
				」５点

（４）
１）
目標状態が見つからないと、サーチレベルがどんどん深くなる」３点
本アルゴリズムはパスのループを検出しない」２点

２）
解１）
Ｓｔｅｐ３・・・先頭ノードがＬ２の要素と重複すればそれを除いてＳｔｅｐ３
へ
解２）
Ｓｔｅｐ５・・・展開した子ノードのうちＬ２の要素と重複すればそれを除いて
残った子ノードをＬ１の先頭へ加える
別解）
反復深化法・・・５点
横型サーチ・・・△３点

（５）
１）Ｓｔｅｐ５・・・Ｌ１の末尾に入れる
２）レベル２で最初にＧが出現するまでアルゴリズムを実行する
（図略）

---------------------------------------------------------------------