手順なら何でもアルゴリズムになるわけではない
アルゴリズムの中心にあるのは、入力を受け取り、曖昧さのない有限の手順によって、目的とする出力を得るという考え方です。「うまく調整する」「適当なところまで続ける」のように、実行する人によって判断が変わる指示では、同じ処理を再現できません。どの状態で何を行うか、いつ処理を終えるかまで明らかになっている必要があります。
たとえば、複数の数から最大値を求めるなら、「先頭の数を暫定的な最大値とする」「次の数と比べ、大きければ最大値を置き換える」「すべての数を調べたら、その値を答えとする」と分けられます。入力される数が変わっても、この手順そのものは変わりません。個別の問題に対する答えではなく、同じ種類の問題へ繰り返し適用できるところが重要です。
料理のレシピはよく使われるたとえですが、「少々」「火が通るまで」など、人の感覚に任せる部分も含みます。コンピュータに実行させる手順では、その判断に必要な条件も具体化しなければなりません。この違いを意識すると、アルゴリズムが単なる作業順ではないことが分かります。
順次・分岐・反復で複雑な処理を組み立てる
多くのアルゴリズムは、処理を上から順に進める「順次」、条件によって次の処理を選ぶ「分岐」、条件を満たす間は処理を繰り返す「反復」を組み合わせて表せます。最大値を求める例では、数を一つずつ読む処理が順次、現在の最大値より大きいかの判断が分岐、最後の数まで比べる動作が反復です。
処理の途中では、値を一時的に覚えておく場所も必要です。先ほどの「暫定的な最大値」は変数に保存できます。また、「現在の数が最大値より大きいか」という条件は、真か偽かで結果が決まる論理演算と結びついています。このように、アルゴリズムはデータを保持する仕組みと、処理の流れを制御する仕組みを組み合わせて作られます。
反復では、必ず終了に近づいているかを確かめることが大切です。回数や終了条件の設計を誤ると、同じ処理を終わりなく続ける無限ループになります。入力が空の場合、値が一つだけの場合、同じ値が複数ある場合など、端にある条件まで考えることで、手順の抜けを見つけやすくなります。
フローチャートとプログラムは同じ手順の別表現
考えたアルゴリズムは、自然言語、箇条書き、フローチャート、疑似コードなどで表せます。疑似コードは、特定のプログラミング言語の細かな書式に縛られず、プログラムに近い形で処理を書く方法です。フローチャートでは、処理や判断を図形と矢印でつなぐため、分岐する場所や繰り返しの範囲を目で追えます。
アルゴリズムとプログラムは同じものではありません。アルゴリズムは問題を解く手順であり、プログラムはその手順を特定のプログラミング言語で記述し、コンピュータが実行できるようにしたものです。一つのアルゴリズムを複数の言語で実装できますし、同じ言語でも書き方は一通りとは限りません。関数として処理を分ければ、役割ごとに手順を確認したり、同じ処理を再利用したりしやすくなります。
表現を変えても、入力に対して行われる判断と操作が同じなら、表しているアルゴリズムは同じです。図で流れを確かめてからコードにする、疑似コードと実行結果を照らし合わせる、といった確認は、実装上の書き間違いと手順そのものの誤りを切り分ける助けになります。
正しいだけでなく、増え方まで比べる
アルゴリズムを評価するときは、まず想定した入力に対して正しい出力を返し、処理が終了するかを確かめます。ただし、正しいアルゴリズムが一つだけとは限りません。同じ答えを出す手順が複数ある場合は、実行に必要な時間や、途中の値を保存するための記憶領域も比較の対象になります。
小さなデータでは差が目立たなくても、データ量が増えると手順による違いが大きくなることがあります。この増え方を入力の大きさとの関係で捉えるのが計算量です。実行する機器やプログラミング言語が変わっても、データ量に対する処理回数の増え方を手掛かりに、手順の性質を比較できます。
たとえば、目的の値を先頭から順に調べる方法と、並んだデータの範囲を段階的に狭める方法では、必要な前提と処理の増え方が異なります。探索アルゴリズムはこの違いを具体的に示します。速さだけを見て選ぶのではなく、データがあらかじめ整列されているか、追加の記憶領域を使えるか、実装や保守が複雑になりすぎないかも含めて判断します。
エレベーターも経路案内も「最適」の意味が違う
アルゴリズムは、計算問題やプログラムの中だけに現れるものではありません。エレベーターがどの呼び出しに先に応じるか、経路案内がどの道を示すか、検索サービスがどの順番で結果を並べるかにも、一定の判断手順があります。外からは一度の操作に見えても、内部では入力の取得、条件の比較、候補の選択、結果の出力という処理が進んでいます。
ここで興味深いのは、「最適」が一つに決まらないことです。経路なら、距離が短い道、所要時間が短い道、料金が安い道は一致しない場合があります。エレベーターでも、待ち時間を抑えることと、移動量を抑えることでは選び方が変わります。何を良い結果とするかを先に定めなければ、手順同士を適切に比べられません。
さらに、入力や条件が同じなら、必ず同じ出力になるアルゴリズムだけがあるわけではありません。処理の途中で乱数を利用するアルゴリズムもあり、同じ問題に対して異なる候補を試す用途などに使われます。それでも、乱数をどこで使い、どの条件で結果を採用し、いつ終了するかという手順は明確です。アルゴリズムを考えることは、操作の順番を並べるだけでなく、目的・入力・判断基準・終了条件を一つの仕組みにまとめることなのです。