Section 6.4 問題解決の手順
問題を解決するには、発見した解を具体的な手順に明確化する必要がある。
定義 6.7. アルゴリズム.
問題の解を手順にして書き表したものをアルゴリズム(algorithm)という[22][23][40]。問題解決にあたっては、アルゴリズムの手順をプログラムとして書き表した上で実行することも多い。 ただし、プログラムはアルゴリズムを書き表したものや、コンピュータで動かすものとは限らない。 「式典のプログラム」のように、機械ではなく人間が実施するものも「プログラム」と呼ばれることがある。
定義 6.8. プログラム.
実行するべき命令の列をプログラム(program)という。アルゴリズムを人間が理解するために表現する方法には、フローチャート(flowchart)[41]やUMLのアクティビティ図(activity diagram)、プログラミング言語風に表す疑似コード(pseudo-code)などがある。
注釈 6.9. 構造化定理.
Böhm(ベーム)とJacopini(ヤコピニ)は、アルゴリズムをプログラムで実現する上で、どのような制御構造が必要かを示した[43]。 彼らの定理は、構造化定理として知られている。 構造化定理によれば、アルゴリズムの実装には、逐次・選択・反復の3種類の制御構造があればよい。図6.10に、フローチャートによる逐次・選択・反復の表現を示す。
逐次(sequence)(順次)は、命令を1つずつ順番に実行する制御構造である。 逐次実行では同時に複数の命令を実行できないため、並列実行は行えない。
選択(selection)(条件分岐)は、指定された条件(命題)の真偽によって、次に実行する命令を変える制御構造である。 多くのプログラミング言語では、if文として実装されている。
反復(iteration)(繰り返し)は、指定された条件(命題)が真である限り、いくつかの命令を実行し続ける制御構造である。 多くのプログラミング言語では、while文として実装されている。
アルゴリズムで解く基本的な問題には、列を特定の順番に並び替える整列(sorting)や、特定の空間の中で最適な解を探す探索(search)がある。
注釈 6.11. 探索.
ある問題の解を求める最も単純な方法は、考えうるすべての組み合わせを総当たりで試す全数探索である。 特に、暗号の解読や認証の通過を目的に行う全数探索は、総当たり攻撃(brute-force attack)と呼ばれる。 全数探索は単純で古典的だが、解の範囲がある程度限定される場合には、人手でも行える他、コンピュータを使って機械的にも行えるため、十分有効な方法である。
全数探索のうち、一つの場合に注目してより深く探索する深さ優先探索は、注目した部分に解が含まれる場合は高速に解を発見できるが、注目した部分に解が含まれない場合は探索に長時間を要する。 深さ優先探索は特定の場合を深めることから、垂直思考と類似している。
また、複数の場合を順に調べてより広く探索する幅優先探索は、解が比較的浅い部分にある場合は高速に解を発見できるが、解が深い部分にある場合は探索に長時間を要する。 幅優先探索は多数の場合を検討することから、水平思考と類似している。
実用上は、深さ優先と幅優先を組み合わせた方法や、評価関数に基づいて次に探索すべき部分を決定する方法などが使われる。 また、すべての場合を検討するのではなく、確率的に場合を選択し、選択した場合のみを検討するMonte Carlo法などもよく使われる。 