Dovetailing (computer science) とは

Dovetailingは、アルゴリズム設計において、異なる計算を相互に織り交ぜ、本質的に同時に実行する技法です。ダブテールを使用するアルゴリズムは、ダブテイラーと呼ばれることもあります。
無限の長さのパスが潜在的に含まれるツリーを考えてみましょう。この環境で深さ優先検索を実行すると、無限パスを移動して戻ってこない可能性があります。しかし、幅優先探索が使用されている場合、無限パスの存在はもはや問題にはなりません。各ノードは、ルートからの距離に応じて分岐的に訪問されるため、無限のパスは、その経路を探索する
このツリーは、一連のプログラムに類似していると見なすことができます。この場合、深さ優先アプローチは、一度に1つのプログラムを実行することに対応し、現在のプログラムが実行を終了したときにのみ次のプログラムに移動する。プログラムの1つが無限の時間実行される場合、この遷移は決して起こりません。ツリーの同じレベルで各子供を訪問する幅優先のアプローチは、ダブテールに対応しています。ここでは、次のステップに移動する前にすべてのプログラムに対して1つのステップが実行されます。従って、無限ランタイムのプログラムの潜在的な存在にかかわらず、各プログラムにおいて進歩がなされる。
無限の数のプログラムの場合、潜在的に無限に長く、幅優先も深さ先も、すべてのプログラムの進歩を確実にするのに十分ではありません。代わりに、次の手法を使用することができます。最初のプログラムの最初のステップを実行します。次に、第2のプログラムの第1のステップおよび第1のプログラムの第2のステップを実行する。次に、第3のプログラムの第1のステップ、第2のプログラムの第2のステップ、および第1のプログラムの第3のステップを実行する。等々。
注意:アルゴリズムを組み合わせる深さ優先(dovetailingなし)と幅優先(dovetailing)の仕組みに慣れることができます。このダブテールアルゴリズムの再帰的な適用は、無限の数の新しいアルゴリズムにつながり、それぞれのアルゴリズムのダブテール化はわずかに少なくなる。