再提出について

• 緑：　文章の形式に注意
  • 段落を構成する。段落は必ず頭下げをする。
  • 適切な改行を行う。
  • 箇条書きはできるだけ使わない。
  • 図表には、図や表が何を表しているのかがわかる適切なキャプションをつける。

• 黄：　レポート全体の構成に注意 　
  • 図があるだけで、値を示した表がないレポートが目立ちました。
    • 今回の実験では計測した値がわからないと、細かな比較ができません。
  • 考察にあたる章あるいは文章がないものが目立ちました。
  • 章にはしない章だてがあるもの（4.1 図1　などとはしません） 。下の章立て例を参考にしてください。
  • レポートに関係のない作業の報告があるもの
    • 手書きで計測結果を書いている皆さんは勘違い。最終計測だけでレポートを作成します。

• 青：　文章の中に、図表の参照がない (最低、図や表の番号を示して文章にしないと、何について書いているのかわからない）
  • 本文では、どの図や表について論じているのかわかるように、図や表を文章に含めること。
  • 「図1をみると、ＸＸがわかった」というような文章ではなく、図や表のどのような点に注目すると、ＸＸがわかったまでを詳しく文章にしよう。

• ピンク：　データ測定 に誤り。不足。不十分。表がない場合にも、この付せんがついているかもしれません。
  • b, m, dのうち、dはゴールの深さで、ゴールのノードIDではない。
    • 深さdのゴールのうち、DFS, IDSでは左端、BFSでは右端のノードが最悪の場合のゴールにあたる。
    • 配布したプログラムを用いて両端のノードを求めて、最悪の場合にあたるノードについて計測を行うこと。
  • このほか、データに誤りがあると思われるものにも付せんがあります。

<章立て　内容>　以下の章立てを参考にしてください。

1. 目的　（下の内容を書くようにしよう）
　　　背景
　　　3つの探索アルゴリズムの解説
　　　探索対象の木(b, m)とゴールの深さ(d)を変化させた3種類の実行を行って、時間計算量と空間計算量を計測すること
　　　3つの探索アルゴリズムのパフォーマンスを比較し、特徴を論じること

2. 方法
　　　何を使ってどう調べるかの説明があるはず。追試できるように示すこと。
　　　配布プログラムの入出力の説明と、計測の方法を示せばよい

3. 結果
　　　書きにくいようなので、今回は3種類の実行について、計測されたデータの表とグラフを示し、そこから読み取れる内容について、表とグラフのある章に、文章を書く。

　　　3. 1 木の枝分かれ数 (b) の影響
　　　　　　時間計算量、空間計算量の表
　　　　　　時間計算量の変化を見るグラフ （x軸がb, y軸は時間計算量。各探索アルゴリズムの折れ線3本）
　　　　　　空間計算量の変化を見るグラフ （x軸がb, y軸は時間計算量。各探索アルゴリズムの折れ線3本）

　　　 　 時間計算量と空間計算量についてdfs, bfs, idsを比較して、わかったことをまとめよう。
　　　　　図や表のどこを見ればそういえるのかを詳しく書くようにしよう。

　　　　　値が違っているか、同じか。増加の仕方は、一次関数的な増加なのか、それとも、指数関数的な増加なのか
　　　　　また、それはどうしてなのかを、各探索アルゴリズムの特徴から考えてみよう。

　　　3.2 と 3.3 と、続けよう

4. 考察
　　　全体のまとめとして、3つのアルゴリズムの特徴を整理してみよう。
　　　まずDFSとBFS, それからIDSと考えてみるとよい

<計測するように指示があったもの>　特に dとgの混乱に注意。

• 授業中に示した、b,m.dの組。dはノードIDではないので、各アルゴリズムごと、深さdの場合の最悪ノードを求めて実行する。

2 4 4
4 4 4
6 4 4
8 4 4
10 4 4

2 2 2
2 4 2
2 6 2
2 8 2
2 10 2

2 10 2
2 10 4
2 10 6
2 10 8
2 10 10

<背景解説>　探索アルゴリズムのポイント

• 木の形　　b と m
• ゴールの位置　g (深さdと、枝の位置。右端、左端、真ん中)
  • d に対する 両端ノードを求めるプログラムは、配布（公開）済
• 時間計算量の指標 　探索管理リストの先頭の１ノードについて処理を行うループの回数
• 空間計算量の指標　 探索管理リストの長さ 　（スタックやキューの長さ）

3つのアルゴリズム

• 深さ優先探索。
  • 探索管理リストはスタック　深さmについて、bmに比例する探索リストを保持
  • 解に到達するまでの、失敗空間の大きさに注目すること。
• 幅優先探索。
  • 探索管理リストはキュー　深さmについて、bのm乗に比例する探索リストを保持
  • 解までの深さが小さいときに特徴的。
• 反復深化探索
  • 深さ優先探索の改良であることに注目、どんな場合に有効か
  • また、幅優先と比較してどうか