近似アルゴリズムとは何ですか?どのような問題に適用されますか?この記事でその答えが分かります

COVID-19パンデミックは世界に多大な変化をもたらし、世界中の科学者や研究者が効果的なワクチンの開発に取り組んでいます。彼らが行っていることは、幅広いサンプル空間から可能性の範囲を大まかに絞り、有効な解決策を見つけようとすることです。近似は私たちの生活において重要な役割を果たします。

オンラインでの食品配達を例に挙げてみましょう。私たちはよくオンラインで食品を注文し、迅速な配達サービスを利用します。しかし、配達員がより短時間で目的地に到着できるようにするために、これらのアプリのバックエンドでどのようなアルゴリズムが実行されているか考えたことがありますか?答えは近似アルゴリズムです。この種の問題は「巡回セールスマン問題」です。

食品の配達: 巡回セールスマン問題の現実世界への応用。

この記事では、近似アルゴリズムといくつかの標準的な問題へのその適用性、および特定のアルゴリズムの選択に影響を与える要因について紹介します。

近似アルゴリズムとは何ですか?

近似アルゴリズムは、最適な解を保証できない NP 完全最適化問題に対処する方法です。近似アルゴリズムの目的は、多項式時間で可能な限り最適値に近づくことです。

正確な最適解を与えることはできませんが、問題を最終解の近似値に収束させることができます。その目標は、次の 3 つの主要な特性を満たすことです。

多項式時間で効率的に実行可能。

最適なソリューションを提供できる。

すべての問題インスタンスに有効です。

背景

数式の評価には、定数、変数、および方程式の順序の分析が伴うことが多く、これらを使用して近似の複雑さを測定できます。このタイプの評価では、問題がP 困難問題と NP 困難問題に分解されます。

P 問題と NP 問題に対する戦略

P 問題は多項式時間で解決できる問題です。

NP は非決定性多項式時間の略です。NP 問題とは、多項式時間で答えを近似的に検証する必要がある問題を指します。しかし今では、これらの問題の多くは解決するのに指数関数的な時間が必要であることが分かっています。

P 戦略と NP 戦略。

本当の議論は、P=NP か P≠NP かということです。これまでのいくつかの研究では、両方とも真実であると示唆されています。問題が多項式次数の場合、最適なアルゴリズムは複数存在します。したがって、NP 完全問題では、最適に近いソリューションを見つけて、最も適切なアルゴリズムを選択する方法が 2 つあります。

入力サイズが小さい場合は、指数関数的な実行時間を持つアルゴリズムの方が適している可能性があります。

第二に、決定論的アルゴリズムを近似アルゴリズムに置き換えることで、多項式時間でほぼ最適なソリューションを見つけることができます。

近似アルゴリズムの複雑さは、入力サイズと近似係数から推測できます。次に、いくつかの例を通して、これらのアルゴリズムを実際の問題にどのように適用できるかを検討します。

パーティションの問題

コンピュータサイエンスでは、この問題は次のように定義されます。複数の正の整数の集合 X が与えられた場合、それを要素の合計が等しい 2 つのサブセット X1 と X2 に分割できます。つまり、各サブセットの値の合計は、他のサブセットの値の合計と等しくなります。

例えば、X={3,4,1,3,3,2,3,2,1}は、X1={3,3,2,3}とX2={4,2,3,1,1}に分割でき、それらの値の合計は11になります。

同様に、X={1,3,1,2,1,2}はX1={2,1,1,1}とX2={3,2}に分割でき、両方のサブセットの値の合計は5になります。興味深いことに、これが唯一の解決策ではありません。 X1={1,3,1}とX2={2,1,2}の値の合計も5であり、複数のサブセットが存在する可能性があることを示しています。

これは NP 完全問題であり、問​​題に対してほぼ最適な解を得ることができる擬似多項式時間の動的計画法ソリューションが存在します。

方法と意思決定の手順

それでは、この問題を分析し、いくつかの個別の標準的な質問に分解してみましょう。ここでは、要素の合計が同じである多重集合のサブセットを見つけたいので、問題は次の 2 つの問題に分解できます。

部分集合の合計問題: 部分集合 X の要素の合計は数 W に等しくなります。

多方向数字分割: 整数パラメータ W が与えられた場合、X を W 個の等しいサブセットに分割する方法を決定します。

近似アルゴリズム

前述のように、分割問題を多方向分割問題とサブセット合計問題に分解した後、これらの問題のために開発されたアルゴリズムを検討することができます。

貪欲な数値分割

アルゴリズムはすべての数字をループし、各数字を合計が最小のサブセットに割り当てます。数字がソートされていない場合、実行時の複雑さは O(n) となり、近似率は約 3/2 になります。 Python 疑似コードは次のとおりです。

def find_partition(numbers): """利用可能な数値を 2 つの等和シリーズに分割します。

引数: 数値: 数値のコレクション。たとえば、整数のリスト。

戻り値: 2 つの数値リスト。 """ X = [] Y = [] sum_X = 0 sum_Y = 0 for n in sorted(numbers, reverse=True): if sum_X < sum_Y: X.append(n) sum_X = sum_X + n else: Y.append(n) sum_Y = sum_Y + n return (X, Y)

数値をソートすると、実行時間の複雑さが O(n logn) に増加し、近似率は 7/6 に増加します。数値が[0,1]の範囲内で均一に分布している場合、近似率は約1 + O(log logn/n)になります。

分割問題の図解。

上の図は、すべてのパーティションをバイナリ ツリーの形式で示しています。ツリーのルートはセット内の最大数を表し、各レベルは入力数に対応し、各独立したブランチは異なるサブセットに対応します。これらのコレクションを走査するには深さ優先走査が必要であり、空間計算量は O(n)、時間計算量は O(2^n) になります。

適用範囲:

アルゴリズムを変更して実行時の複雑さを改善することができます。各レベルの主な目標は、現在の数値を最小の合計を持つサブセットに割り当てるブランチを構築することです。まず貪欲な数字分割によって合計を求め、次に最適化に切り替えて完全な多項式時間の近似解を得ます。

カルマルカー・カープアルゴリズム

Karmarkar-Karp アルゴリズムは、数字を降順で並べる最大差法を指し、元の数字を差の値に置き換えてセットに入れ続けます。 Java 疑似コード実装は次のとおりです。

int karmarkarKarpPartition(int[] baseArr) { // 最大ヒープを作成する PriorityQueue heap = new PriorityQueue(baseArr.length, REVERSE_INT_CMP);

for (int 値: baseArr) { heap.add(値); }

while (heap.size() > 1) { int val1 = heap.poll(); int val2 = heap.poll(); heap.add(val1 - val2); }

heap.poll() を返します。

アルゴリズムは入力セット S とパラメータ k で構成されます。 S を k 個のサブセットに分割し、これらのサブセット内の数値の合計が等しくなるようにして、目的の出力を構築します。アルゴリズムには次の主要なステップが含まれます。

数字を降順に並べます。

元の数字を差分と置き換えて、数字が 1 つだけになるまで続けます。

バックトラッキング アルゴリズムを使用してパーティション分割を完了します。

適用範囲:

このアルゴリズムは、バイナリ ツリーを構築することによってパーティション分割することを前提としています。各レベルは数字のペアを表し、左のブランチは数字をその差で置き換えることを表し、右のブランチは差を同じサブセットに配置することを表します。アルゴリズムは、まず最大差を通じて解を見つけ、その後、より良い近似解を探し続けます。空間計算量は O(n) ですが、最悪の場合の時間計算量は O(2^n) になる可能性があります。

箱詰めの問題

ビンパッキング問題には、現実世界でさまざまな応用があります。たとえば、インドの廃棄物管理システムを根本的に改善する方法などです。この問題は、ごみ箱詰め問題を使用して解決できます。この問題は、x 量のごみに対して必要なごみ箱の数を当局が決定するのに役立ちます。

コンテナ船: 梱包問題の実際の応用。

コンピュータ サイエンスでは、この問題はさまざまなメモリ管理技術で使用できます。このアルゴリズムでは、冗長性を排除し、スペースの無駄を最小限に抑えることで、さまざまな形状とサイズのオブジェクトをパックできます。

例えば、n個のアイテムを含む集合が与えられた場合、各アイテムのサイズはs1、s2、..、sn（0

古典的な方法:

1. 次のフィット: 現在のアイテムが現在のボックスに収まるかどうかを確認します。収まる場合はアイテムがチェスト内に配置され、収まらない場合は新しいチェストが開かれます。

例を見てみましょう。項目は 0.5、0.7、0.5、0.2、0.4、0.2、0.5、0.1、0.6 で、ビン サイズはすべて 1 です。

近傍適応アルゴリズムに基づくビンパッキング ソリューション (M = ビンの合計数 = 6)。

2. 最初のフィット: 箱を順番に確認し、スペースがなくなるまで最初の箱に新しいアイテムを入れてから、新しい箱を使用します。

例を見てみましょう。項目は 0.5、0.7、0.5、0.2、0.4、0.2、0.5、0.1、0.6 で、ビン サイズはすべて 1 です。

ファーストマッチング法に基づくビンパッキングソリューション (M = ビンの合計数 = 5)。

3. 最適なフィット: 箱を順番に確認し、新しいアイテムをそれぞれ最もフィットする箱に配置します。収まらない場合は、新しいボックスが作成されます。

例を見てみましょう。項目は 0.5、0.7、0.5、0.2、0.4、0.2、0.5、0.1、0.6 で、ビン サイズはすべて 1 です。

最適マッチング法に基づくビンパッキングソリューション (M = ビンの合計数 = 5)。

この方法の出力は最初のマッチング方法と同じですが、この方法の利点は、FFD よりも高速であることです。つまり、時間計算量は O(nlogn) です。

自然な方法:

すべてのアイテムのサイズが事前にわかっている場合、自然な解決策としては、まずアイテムを最大から最小の順に並べ替えてから、次のヒューリスティックを適用することです。

最初の一致減少法

ベストマッチング減少法

同じ例 0.7、0.6、0.5、0.5、0.5、0.4、0.2、0.2、0.1 があるとすると、順序は 0.7、0.6、0.5、0.5、0.5、0.4、0.2、0.2、0.1 になります。

最適化方法 (M = ビンの合計数 = 4)。