列挙アルゴリズム

コンピュータサイエンスにおいて、列挙アルゴリズムとは、計算問題の解を列挙するアルゴリズムのことです。形式的には、このようなアルゴリズムは、関数問題と同様に、入力を受け取り、解のリストを生成する問題に適用されます。列挙アルゴリズムは、各入力に対して、重複のないすべての解のリストを生成し、その後停止する必要があります。列挙アルゴリズムのパフォーマンスは、解を生成するのに必要な時間、つまりすべての解を生成するのに必要な合計時間、または連続する2つの解間の最大遅延と、最初の解を出力するまでの時間としてカウントされる前処理時間のいずれかで測定されます。この複雑さは、出力依存型アルゴリズムの場合と同様に、入力のサイズ、個々の出力のサイズ、またはすべての出力セットの合計サイズで表現できます。

列挙問題${\displaystyle P}$は関係として定義される${\displaystyle R}$任意のアルファベットの文字列に対して${\displaystyle \Sigma }$:

${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}}$

アルゴリズムが解決する${\displaystyle P}$すべての入力に対して${\displaystyle x}$このアルゴリズムは（無限の場合もある）数列を生成する${\displaystyle y}$そのため${\displaystyle y}$重複がなく、${\displaystyle z\in y}$かつその場合に限り${\displaystyle (x,z)\in R}$アルゴリズムは、シーケンスが${\displaystyle y}$有限である。

列挙問題は計算複雑性理論の文脈で研究されており、そのような問題に対していくつかの複雑性クラスが導入されている。

このようなクラスの非常に一般的な例として、EnumP ^{[ 1 ]}があります。これは、可能な出力の正しさを入力と出力の多項式時間でチェックできる問題のクラスです。形式的には、このような問題には、問題の入力xと候補出力yを入力として受け取り、入力xに対するyが正しい出力であるかどうかをxとyの多項式時間で判定するアルゴリズムA が存在しなければなりません。たとえば、このクラスには、NPクラスの問題の証拠を列挙することに相当するすべての問題が含まれます。

定義されているその他のクラスは以下のとおりです。EnumPにも含まれる問題の場合、これらの問題は具体的度の低いものから高いものへと順に並べられています。

• 出力多項式とは、その完全な出力を多項式時間で計算できる問題のクラスのことである。
• 増分多項式時間とは、すべてのiに対して、i番目の出力が入力サイズとiの数に関して多項式時間で生成できる問題のクラスです。
• 多項式遅延とは、連続する2つの出力間の遅延が入力の多項式であり（かつ出力とは無関係である）問題のクラスを指します。
• 強多項式遅延とは、各出力前の遅延がその特定の出力のサイズに関して多項式となる（入力や他の出力とは無関係な）問題のクラスを指します。前処理は一般的に多項式であると仮定されます。
• 定遅延とは、各出力までの遅延が一定、つまり入力と出力に依存しない問題のクラスを指します。前処理フェーズは一般的に入力の多項式であると仮定されます。

• バックトラッキング：すべての解を列挙する最も簡単な方法は、可能な結果の空間を体系的に探索することです（各ステップで分割します）。 ^{[ 2 ]}ただし、これを実行すると遅延に関する十分な保証が得られない場合があります。つまり、バックトラッキング アルゴリズムは、完全な解を生み出さない可能な結果の空間の部分を探索するのに長い時間を費やす可能性があります。
• フラッシュライトサーチ：この手法は、すべての可能な解の空間を探索しながら、各ステップで現在の部分解を部分解に拡張できるかどうかを解くことで、バックトラッキングを改善します。 ^{[ 1 ]}答えが「いいえ」の場合、アルゴリズムはすぐにバックトラックして時間の無駄を回避できるため、任意の2つの完全な解間の遅延に関する保証を示すことが容易になります。特に、この手法は自己還元可能な問題によく適用されます。
• 集合演算における閉包性：2つの集合の非交和を列挙したい場合、まず最初の集合を列挙し、次に2番目の集合を列挙することで問題を解決できます。和集合が非交和ではないが、集合をソート順に列挙できる場合は、重複をその場で削除しながら、両方の集合に対して並列に列挙を実行できます。和集合が非交和ではなく、両方の集合がソートされていない場合は、ハッシュテーブルを使用するなどして、メモリ使用量が増える代償で重複を削除できます。同様に、 2つの集合の直積は、一方の集合を列挙し、各結果を2番目のステップで得られたすべての結果と結合することで効率的に列挙できます。

• 頂点列挙問題とは、線形不等式のシステムとして記述された多面体が与えられ、その多面体の頂点を列挙しなければならない問題である。
• ハイパーグラフの最小横断線を列挙する。この問題は単調双対化に関連しており、データベース理論やグラフ理論の多くの応用と結びついている。^{[ 3 ]}
• 例えば、連言クエリや単項二階述語で表現されたクエリなど、データベースクエリに対する回答を列挙する。連言クエリは線形前処理と定数遅延で列挙できるという特徴付けがデータベース理論でなされている。 ^{[ 4 ]}
• 入力グラフ内の最大クリークを列挙する問題（例： Bron–Kerboschアルゴリズム）
• マトロイドやグリードイドなどの構造のすべての要素を列挙する
• グラフに関するいくつかの問題、例えば、独立集合、パス、カットなどの列挙。
• 知識コンパイルで研究される制限クラス内のブール関数の表現、例えば連言標準形または選言標準形で記述されたブール式、OBDDなどの二分決定図、またはブール回路の満足割り当てを列挙する(例: NNF)。^{[ 5 ]}

列挙アルゴリズムの概念は、計算可能性理論の分野でも、 RE（再帰的に列挙可能な問題の総称）のような高複雑度クラスを定義するために用いられます。REは、集合のすべての要素を生成する列挙アルゴリズムが存在する集合のクラスです。集合が無限集合の場合、アルゴリズムは永久に実行される可能性がありますが、各解は有限時間後に生成されなければなりません。