1.アルゴリズムとは

キーワード

• 深さ優先探索
• 幅優先探索
• マッチング

1.1 アルゴリズムとは何か

• アルゴリズム：問題を解くための方法・手順
• 選択肢を順に調べる方法：線型探索法
• 選択肢を半分に区切って調べる方法：二分探索法
• どちらも立派なアルゴリズム

1.2 アルゴリズムの例：深さ優先探索と幅優先探索

探索アルゴリズムについて例をあげる。

• 深さ優先探索(DFS)：とりあえず突き進む動作を繰り返していく手法
  • 様々なアルゴリズムの基礎となるもの
  • 矛盾が見つかったら１つ前の選択肢に戻る
  • 力任せな探索アルゴリズムだが、探索順序を工夫することで性能が劇的に変化する
  • グラフ上の探索と考えると良い
• 幅優先探索(BFS)：出発点に近いところから探索していく手法
  • 何かを達成するための最短手順を知りたいときに使う
  • こちらも力任せな探索アルゴリズム

1.3 アルゴリズムの例：マッチング

• 2カテゴリ間のつながりについて考える問題で使う
• 詳しくは16章

1.4 アルゴリズムの記述方法

• 文章で記述
  • 概要を把握するのに有効
  • 細かい動作を伝えるのは大変
• 疑似コードを使う
  • 細かい動作を伝えやすい

1.5 アルゴリズムを学ぶ意義

• 問題解決に対してのアプローチ方法・視点を増やすことができる
  • アルゴリズムを学ぶ前：具体的な答えを示す以外に解決方法を提示できない
  • アルゴリズムを学んだ後：問題を解くためのアルゴリズム(方法)を提示することができる