決定論的アルゴリズムと非決定論的アルゴリズムの違いを徹底解説

プログラミングにおけるアルゴリズムとは、特定のタスクを実行し、目的の出力を達成するために設計された、明確に定義された命令(手順)の集まりのことです。「定義された命令の集まり」とは、すなわち、それらの命令が想定どおりに実行されれば、どのような結果になるかがあらかじめ把握できているということを意味します。

そして、命令の実行結果に関する知見の有無によって、アルゴリズムは大きく次の2種類に分類されます。

• 決定論的(Deterministic)アルゴリズム
• 非決定論的(Non-deterministic)アルゴリズム

本記事では、それぞれの特徴を解説したうえで、両者の主な違いを比較表でわかりやすく整理します。

決定論的アルゴリズムとは

決定論的アルゴリズムとは、各ステップの実行結果が常に一意に定まるアルゴリズムのことです。言い換えれば、決められた手順を固定のステップ数で実行すれば、必ず「受理(Accept)」または「拒否(Reject)」のいずれかの状態で終了し、同じ入力に対しては何度実行しても必ず同じ結果が得られます。

代表例としては、マージソートやクイックソートといった整列アルゴリズム、四則演算などの算術処理、二分探索などが挙げられます。これらは入力が同一であれば、実行環境やタイミングに関係なく常に同じ出力を返します。

非決定論的アルゴリズムとは

一方、非決定論的アルゴリズムとは、各ステップの結果が一意に定まらず、複数の結果候補の中から選択が行われる可能性があるアルゴリズムのことです。この場合、計算を行うマシンは、後から定義される判定条件に従って、各操作の時点で取り得る結果の中から任意のものを選択することが許されます。

理論計算機科学では、非決定性チューリングマシンの動作モデルや、NP問題(多項式時間で検証はできるが、解を効率的に見つける方法が自明ではない問題)の議論などにおいて、この非決定論的な考え方が重要な役割を果たします。

両者の主な違いの比較表

ここまでの内容を踏まえ、決定論的アルゴリズムと非決定論的アルゴリズムの違いを、5つの観点から以下の表にまとめます。

まとめ

決定論的アルゴリズムは、同じ入力に対して常に同じ手順・同じ結果を返す再現性の高いアルゴリズムであり、日常的なプログラミングで扱われる大多数のアルゴリズムがこれに該当します。一方、非決定論的アルゴリズムは、実行のたびに結果や経路が変わり得るアルゴリズムであり、理論モデルの構築や探索空間が巨大な問題の分析などで概念として活用されます。

アルゴリズムの信頼性や計算量(実行時間)を評価するうえで、この「決定論的か非決定論的か」という視点は非常に重要です。特に計算理論やP≠NP問題などのテーマを学ぶ際には、両者の違いを正しく理解しておくことが土台となります。