57 アルゴリズム発見
- 問題解決のプロセスを理解する。
- アルゴリズムの発見のためのヒューリスティックを理解する。
- トップダウン設計とボトムアップ設計の概念を理解する。
- ブラックボックステストとホワイトボックステストの概念を理解する。
57.1 問題解決とアルゴリズム発見
アルゴリズムは、問題を解決するための手順を指す。問題を解決するためには、アルゴリズムを発見し、そのアルゴリズムをプログラムとして実装する必要がある。十分なプログラミング能力があれば、アルゴリズムを実装することは比較的容易である。しかし、アルゴリズムを発見することは、しばしば難しい課題となる。
例 57.1 ここでは、経営工学の分野でよく知られているいくつかの最適化問題を紹介する。これらの問題に対する効率的なアルゴリズムの発見は、経営工学の研究において重要な課題となっている。
ナップサック問題は、\(n\)個のアイテムが与えられ、それぞれのアイテム\(i\)には価値\(w_i\)と重さ\(v_i\)があるとき、重量の合計が\(W\)以下となるようにアイテムを選び、価値の合計を最大化する問題である。
巡回セールスマン問題は、\(n\)個の都市とそれらの都市間の距離が与えられたとき、すべての都市を一度ずつ訪れ、元の都市に戻る最短の経路を求める問題である。
ダイエット問題は、\(n\)種類の食品が与えられ、それぞれの食品には栄養素の含有量と価格があるとき、必要な栄養素を満たしつつ、価格の合計を最小化する食品の組み合わせを求める問題である。
これからの大学4年間では、これらの問題に対するアルゴリズムを順次学んでいくので、楽しみにしていてほしい。
数学者George Pólyaが作成した、「いかにして問題をとくか」（How to Solve It）において、問題を解決するためのプロセスが紹介されている。
- 問題を理解する
- 問題を解くための計画を立てる
- 計画を実行する
- 結果を検証する
この問題解決のプロセスをプログラムに適用すると、次のようになる。
- 問題を理解する
- アルゴリズムを発見する
- アルゴリズムをプログラムとして実装する
- プログラムを実行し、結果を検証する
Pólyaの問題解決のプロセスは、従うべき手順ではなく、完了すべき手順である。問題解決のプロセスは、必ずしも順番に進むわけではなく、必要に応じて順番を入れ替えたり、繰り返したりすることがある。
例えば、アルゴリズムを発見する段階で、問題を十分に理解していないことに気づくことがある。その場合、問題を理解する段階に戻って、再度問題を考える必要がある。また、結果を検証する段階で、アルゴリズムに誤りがあることに気づくことがある。その場合、アルゴリズムを発見する段階に戻って、再度アルゴリズムを考える必要がある。
57.2 問題の理解
問題を理解するためには、問題の定義を明確にし、問題の条件や制約を把握する必要がある。問題の定義は、問題を解決するための出発点となる。
問題の定義を明確にするためには、次のような質問を考えるとよい。
- 問題について、どのような情報が与えられているか？
- 問題の制約と目的は何か？
- 問題の解はどのような形式で表現されるか？
- 問題をどのように数学的に表現できるか？
57.3 アルゴリズムの発見
「いかにして問題をとくか」において、Pólyaは問題解決のためのヒューリスティック（heuristic）を紹介している。ヒューリスティックとは、試行錯誤しながら経験と発明を積み重ねることによって問題を解いてゆく方法である。
下の表は、Pólyaが提案するヒューリスティックの一部を示している。
問題解決のためのヒューリスティック
| ヒューリスティック | 説明 |
|---|---|
| 類推（Analogy） | Can you find a problem analogous to your problem and solve that? |
| 一般化（Generalization） | Can you find a problem more general than your problem? |
| 特殊化（Specialization） | Can you find a problem more specialized? |
| 帰納（Induction） | Can you solve your problem by deriving a generalization from some examples? |
| 分解（Decomposition） | Can you decompose the problem and “recombine its elements in some new manner”? |
57.4 プログラミング
よく知られているプログラミング方法として、トップダウン設計とボトムアップ設計がある。
トップダウン設計（Top-Down Design）は、初めに全体の構造を設計し、次に階層構造に従って上位から下位へとソフトウエアを開発していくものである。
ボトムアップ設計（Bottom-Up Design）は、最初に下位の部品を開発し、次にそれらを組み合わせて上位の部品を作成していくものである。
例 57.2 C言語でトップダウン設計を行う場合、まずはmain()関数を定義し、その中で必要な関数を呼び出す形でプログラムを構築していく。次に、各関数の実装を行う。一方、ボトムアップ設計では、まずは関数を作成し、それらを組み合わせてmain()関数を定義する。
57.5 テスト
プログラムを開発した後は、テストを行うことが重要である。簡単なテストケースを用意し、プログラムが期待通りに動作するかを確認できる。
よりシステム的なテスト方法として、ブラックボックステストとホワイトボックステストがある。
ブラックボックステスト（Black-Box Testing）は、プログラムの内部構造を考慮せず、入力と出力の関係に基づいてテストを行う方法である。どれだけのデータをテストしたかを示す指標はデータカバレッジ（Data Coverage）である。
ホワイトボックステスト（White-Box Testing）は、プログラムの内部構造を考慮し、その構造に基づいてテストを行う方法である。具体的には、コードの各部分が正しく動作するかを確認するために、条件分岐やループなどの制御フローを考慮してテストケースを設計する。テスト対象のソースコードがどれだけ実行されたかを数値で示すコードカバレッジ（Code Coverage）を測定することもある。