Loading article…
ハイブリッドアルゴリズムとは、同じ問題を解決する 2 つ以上の他のアルゴリズムを組み合わせたアルゴリズムです。データの特性に基づいて 1 つを選択するか、アルゴリズムの実行中にそれらのアルゴリズムを切り替えます。これは通常、各アルゴリズムの望ましい機能を組み合わせるために行われ、全体的なアルゴリズムが個々のコンポーネントよりも優れたものになります。
「ハイブリッド アルゴリズム」とは、単に複数のアルゴリズムを組み合わせて異なる問題を解決することを指すのではなく (多くのアルゴリズムはより単純な部分の組み合わせと考えることができます)、同じ問題を解決するが、他の特性 (特にパフォーマンス) が異なるアルゴリズムを組み合わせることだけを指します。
例
コンピュータサイエンスでは、ハイブリッド アルゴリズムは、再帰アルゴリズム、特に分割統治法や減少統治法の 実装の最適化された実際の実装で非常に一般的です。これらのアルゴリズムでは、再帰の深いところに行くにつれてデータのサイズが小さくなります。この場合、1 つのアルゴリズムが全体的なアプローチ (大きなデータの場合) に使用されますが、再帰の深いところで、小さなデータに対してより効率的な別のアルゴリズムに切り替わります。一般的な例はソート アルゴリズムで、挿入ソートは大きなデータには非効率的ですが、小さなデータ (たとえば、5 から 10 個の要素) に対しては非常に効率的であり、最初にマージソートやクイック ソートなどの別のアルゴリズムを適用した後、最終ステップとして使用されます。マージ ソートとクイック ソートは大きなデータに対して漸近的に最適ですが、小さなデータに適用するとオーバーヘッドが大きくなるため、再帰の最後で別のアルゴリズムが使用されます。高度に最適化されたハイブリッド ソート アルゴリズムはTimsortです。これは、マージ ソート、挿入ソート、およびマージ ロジック内の 追加ロジック (バイナリ検索を含む) を組み合わせたものです。
単純なハイブリッド再帰アルゴリズムの一般的な手順は、ベースケースを短絡することです。これは、アームズレングス再帰とも呼ばれます。この場合、関数呼び出しの前に次のステップがベースケースになるかどうかがチェックされ、不要な関数呼び出しが回避されます。たとえば、ツリーでは、子ノードに再帰してから null かどうかを確認するのではなく、再帰する前に null をチェックします。これは、多くのツリー アルゴリズムのように、アルゴリズムが通常ベースケースに何度も遭遇する場合に効率化に役立ちますが、それ以外の場合は、複雑さが増すため、特に学術分野では不適切なスタイルと見なされます。
パフォーマンス上の理由によるハイブリッド アルゴリズムの別の例としては、introsortとintroselect があります。これらは、平均パフォーマンスを高速化するために 1 つのアルゴリズムを組み合わせ、最悪の場合のパフォーマンスを (漸近的に) 最適にするために別のアルゴリズムにフォールバックします。 introsort はquicksortで始まりますが、 quicksort がうまく進んでいない場合はヒープ ソートに切り替えます。同様に、 introselect はquickselectで始まりますが、 quickselect がうまく進んでいない場合は median of mediansに切り替えます。
集中型分散アルゴリズムは、多くの場合、個別のアルゴリズム（各分散プロセッサで実行）と結合アルゴリズム（集中型ディストリビュータで実行）で構成されるハイブリッド アルゴリズムとして考えることができます。これらはそれぞれ、アルゴリズム全体を 1 つのプロセッサで実行するか、計算全体をディストリビュータで実行して、些細な結果（各プロセッサからの 1 要素のデータ セット）を結合することに対応します。これらのアルゴリズムの基本的な例は、分散ソートです。これは特に外部ソートに使用され、データを個別のサブセットに分割し、サブセットをソートしてから、サブセットを完全にソートされたデータに結合します。例としては、バケット ソートやフラッシュソートがあります。
ただし、一般的に分散アルゴリズムはハイブリッド アルゴリズムである必要はありません。個々のアルゴリズム、または組み合わせアルゴリズムや通信アルゴリズムが異なる問題を解決する可能性があるためです。たとえば、MapReduceなどのモデルでは、 Map および Reduce ステップは異なる問題を解決し、これらを組み合わせることで別の 3 番目の問題を解決します。