Loading article…
アルゴリズム設計におけるダブテイルとは、異なる計算を相互に組み合わせ、実質的に同時に実行する手法である。ダブテイルを用いるアルゴリズムは、ダブテイルアルゴリズムと呼ばれることもある。
無限の長さのパスを含む可能性のあるツリー（ただし、各ノードは有限個の子ノードしか持たない）を考えてみましょう。このような環境で深さ優先探索を実行すると、探索は無限のパスに沿って進み、戻ってこなくなる可能性があり、ツリーの一部が未探索のまま残ってしまう可能性があります。しかし、幅優先探索を使用する場合は、無限のパスの存在はもはや問題になりません。各ノードはルートからの距離に応じて分岐しながら訪問されるため、無限のパスは、そのパスに沿って進む探索の部分のみに影響を与えます。
このツリーはプログラムの集合に例えることができます。この場合、深さ優先探索は、一度に1つのプログラムを実行し、現在のプログラムの実行が完了した後にのみ次のプログラムに進むことに相当します。いずれかのプログラムが無限に実行される場合、この遷移は決して起こりません。ツリーの同じレベルにある各子ノードを訪問する幅優先探索は、ダブテイル処理の一例であり、次のプログラムに進む前に各プログラムに対して1つのステップを実行します。したがって、終了しないプログラムが存在する可能性に関係なく、各プログラムで処理が進行します。
別の例としては、非決定性チューリングマシンMを決定性チューリングマシン（例えば、汎用チューリングマシン）でシミュレートする場合が挙げられます。このような場合、 Mの計算分岐のいずれかに無限ループが含まれる可能性があるので、ダブテイル法を用いる必要があります。
無限個のプログラムがあり、それぞれが無限に長い可能性がある場合、幅優先探索も深さ優先探索も、すべてのプログラムの実行を確実に進めるには不十分です。代わりに、次の手法を用いることができます。まず、最初のプログラムの最初のステップを実行します。次に、最初のプログラムの2番目のステップと2番目のプログラムの最初のステップを実行します。次に、最初のプログラムの3番目のステップ、2番目のプログラムの2番目のステップ、3番目のプログラムの最初のステップを実行します。これを繰り返します。この手法は、対角化（例えば、Haskellの「universe」パッケージや「Omega」モナドなどで使用されている）としても知られています。