パラメータ化されたアルゴリズムを使用して NP 困難問題を解決する方法

研究活動はおそらく私たちのトレーニングの中で最も興味深い部分です。 大学在学中に自分の選んだ方向に挑戦してみるという考え方です。 たとえば、ソフトウェア エンジニアリングや機械学習の分野の学生は、企業 (主に JetBrains や Yandex ですが、それだけではありません) に研究に行くことがよくあります。

この投稿では、コンピューターサイエンスにおける私のプロジェクトについて話します。 仕事の一環として、私は最も有名な NP 困難問題の XNUMX つを解決するためのアプローチを研究し、実践しました。 頂点カバーの問題.

現在、NP 困難問題に対する興味深いアプローチ、つまりパラメーター化されたアルゴリズムが急速に開発されています。 皆さんに最新の情報を提供し、いくつかの簡単なパラメータ化されたアルゴリズムを説明し、私にとって非常に役に立った強力な方法を 1 つ説明します。 私は PACE チャレンジ コンテストで自分の結果を発表しました。公開テストの結果によれば、私のソリューションは XNUMX 位となり、最終結果は XNUMX 月 XNUMX 日に判明します。

私について

私の名前はヴァシリー・アルフェロフです。サンクトペテルブルクの国立研究大学高等経済学部で現在 179 年生を終えています。 私は学生時代からアルゴリズムに興味があり、モスクワの第 XNUMX 校で学び、コンピューター サイエンス オリンピックに参加して成功しました。

パラメータ化されたアルゴリズムの限られた数の専門家がバーに入ります...

本から抜粋した例 「パラメータ化されたアルゴリズム」

あなたが小さな町のバーの警備員であると想像してください。 毎週金曜日には、街の半分がリラックスするためにあなたのバーにやって来ます。そのため、多くの問題が発生します。喧嘩を防ぐために、乱暴な客をバーから追い出す必要があります。 最終的にはうんざりして、予防策を講じることにします。

あなたの街は小さいため、バーで一緒になった場合、どのペアの客が喧嘩する可能性が高いかが正確にわかります。 のリストはありますか n 今夜バーに来る人たち。 あなたは、誰にも喧嘩をさせずに、何人かの町民をバーに近づけないようにすることにしました。 同時に、上司は利益を失いたくないので、これ以上の利益を与えないと不満を抱くでしょう。 k 人。

残念ながら、目の前にある問題は古典的な NP 困難な問題です。 あなたは彼女を次のように知っているかもしれません 頂点カバー、または頂点カバー問題として。 このような問題では、一般に、許容可能な時間内に動作するアルゴリズムは存在しません。 正確に言うと、証明されていないが非常に強力な仮説 ETH (指数関数的時間仮説) は、この問題は時間内に解決できないと言っています。 つまり、完全な検索より顕著に優れたものは考えられません。 たとえば、誰かがあなたのバーに来るとします。 N = 1000 人間。 その後、完全な検索は次のようになります おおよそのオプションがあります - クレイジーな量。 幸いなことに、あなたの管理者はあなたに制限を与えました k = 10したがって、反復処理が必要な組み合わせの数ははるかに少なくなります。XNUMX 個の要素のサブセットの数は次のようになります。 。 これは改善されましたが、強力なクラスターであっても XNUMX 日ではカウントされません。

バーの訪問者間の緊張した関係のこの状況で喧嘩の可能性を排除するには、ボブ、ダニエル、ヒョードルを締め出す必要があります。 二人だけが取り残されるような解決策はありません。

これは、諦めて全員を受け入れる時期が来たということですか？ 他のオプションを検討してみましょう。 たとえば、非常に多くの人と戦う可能性のある人だけを入れることはできません。 少なくとも戦える人がいれば k+1 他の人がいる場合、その人を中に入れることは絶対にできません。そうでない場合は、全員を締め出さなければなりません k+1 彼が戦うことができる町の人々、それは間違いなく指導者を動揺させるでしょう。

この原則に従って、できる限りすべての人を捨てましょう。 そうすれば、他の誰もがそれ以上のもので戦うことができます k 人々。 それらを捨てる k ああ、あなたが防ぐことができるのはこれだけです 衝突。 これは、それ以上ある場合には、 誰かが少なくとも XNUMX つの紛争に巻き込まれている場合、すべてを防ぐことは確かに不可能です。 もちろん、完全に紛争のない人々を確実に受け入れることになるため、XNUMX 人中 XNUMX 人のサイズのサブセットをすべて調査する必要があります。 おおよそあります であり、この数の操作はクラスター上ですでに整理されています。

紛争がまったくない個人を安全に連れて行くことができるのであれば、紛争に XNUMX つだけ参加する個人はどうなるでしょうか? 実際、相手のドアを閉めることによっても侵入される可能性があります。 確かに、アリスがボブとだけ対立している場合、アリスを XNUMX 人から外しても負けません。ボブには他の対立があるかもしれませんが、アリスには確かに対立はありません。 それに、二人とも入れないと意味がありません。 そのような操作の後、それ以上は何も残りません 未解決の運命を持つゲストたち：私たちにあるのはただ一つ それぞれの紛争には XNUMX 人の参加者がおり、それぞれが少なくとも XNUMX 件の紛争に関与しています。 したがって、残っているのは整理することだけです これらのオプションは、ラップトップで半日かかると簡単に考えられます。

実際、単純な推論でさらに魅力的な条件を達成することができます。 すべての紛争を必ず解決する必要があることに注意してください。つまり、対立する各ペアから、参加させない人を少なくとも XNUMX 人選択します。 次のアルゴリズムを考えてみましょう。競合がある場合、そこから XNUMX つの参加者を削除して残りから再帰的に開始し、次に他の参加者を削除して再帰的に開始します。 すべてのステップで誰かを除外するため、このようなアルゴリズムの再帰木は深さの二分木になります。 kしたがって、合計すると、アルゴリズムは次のように動作します。 どこ n は頂点の数であり、 m - リブの数。 この例では、これは約 XNUMX 万ですが、ラップトップだけでなく携帯電話でも一瞬で計算できます。

上記の例は一例です パラメータ化されたアルゴリズム。 パラメータ化されたアルゴリズムは、時間内に実行されるアルゴリズムです f(k) ポリ(n)どこ p - 多項式、 f は任意の計算可能な関数であり、 k - 何らかのパラメータ。問題のサイズよりもはるかに小さい可能性があります。

このアルゴリズムが例を示す前のすべての推論 カーネル化 パラメータ化されたアルゴリズムを作成するための一般的な手法の XNUMX つです。 カーネライゼーションとは、問題のサイズをパラメータの関数によって制限される値まで縮小することです。 結果として生じる問題は、多くの場合、カーネルと呼ばれます。 したがって、頂点の次数に関する単純な推論により、答えのサイズによってパラメーター化された、頂点カバー問題の二次カーネルが得られました。 このタスクでは他にも選択できる設定がありますが(LP 上の頂点カバーなど)、これについて説明します。

ペースチャレンジ

競争 ペースチャレンジ (パラメーター化されたアルゴリズムと計算実験チャレンジ) は、パラメーター化されたアルゴリズムと、計算問題を解決するために実際に使用されるアプローチとのつながりを確立するために 2015 年に誕生しました。 最初の XNUMX つのコンテストは、グラフのツリー幅を見つけることに専念しました (ツリー幅)、シュタイナー木を探しています (シュタイナーツリー) サイクルをカットする一連の頂点を検索します (フィードバック頂点セット）。 今年、挑戦できる問題の XNUMX つは、上記の頂点カバー問題でした。

このコンテストは年々人気が高まっています。 予備データを信じれば、今年は 24 チームが頂点カバー問題だけを解決するコンテストに参加しました。 競争は数時間やXNUMX週間ではなく、数か月続くことは注目に値します。 チームには文献を研究し、独自のアイデアを考え出し、それを実装してみる機会があります。 本質的に、このコンテストは研究プロジェクトです。 最も効果的なソリューションのアイデアと受賞者の表彰はカンファレンスと併せて開催されます。 IPEC (パラメータ化された正確な計算に関する国際シンポジウム) はヨーロッパ最大の年次アルゴリズム会議の一環として開催されます。 ALGO。 コンテスト自体の詳細情報は、次のサイトでご覧いただけます。 オンライン、そして前年の結果は嘘をつきます ここで.

解決策のスキーム

頂点カバーの問題を解決するために、パラメーター化されたアルゴリズムを使用してみました。 これらは通常、単純化ルール (理想的にはカーネル化につながる) と分割ルールの XNUMX つの部分で構成されます。 簡略化ルールは、多項式時間での入力の前処理です。 このようなルールを適用する目的は、問題を同等のより小さな問題に縮小することです。 単純化ルールはアルゴリズムの中で最もコストがかかる部分であり、この部分を適用すると合計実行時間が長くなります。 単純な多項式時間の代わりに。 私たちの場合、分割ルールは、各頂点について、その頂点またはその隣接頂点のいずれかを答えとして取得する必要があるという事実に基づいています。

一般的なスキームは次のとおりです。単純化ルールを適用し、いくつかの頂点を選択し、XNUMX つの再帰呼び出しを行います。最初の呼び出しでは応答としてその頂点を取得し、もう XNUMX つはその近傍をすべて取得します。 これを、この頂点に沿った分割 (分岐) と呼びます。

次の段落では、このスキームに XNUMX つだけ追加します。

分割 (分岐) ルールのアイデア

分割が行われる頂点を選択する方法について説明します。
主なアイデアは、アルゴリズムの意味で非常に貪欲です。最大次数の頂点を取得し、それに沿って分割しましょう。 なぜその方が良く見えるのでしょうか？ 再帰呼び出しの XNUMX 番目の分岐では、この方法で多くの頂点を削除するためです。 残りのグラフは小さいので、すぐに作業できます。

このアプローチは、すでに説明した単純なカーネライゼーション技術と組み合わせることでうまく機能し、数千頂点のサイズのいくつかのテストを解決します。 ただし、たとえば、立方体グラフ (つまり、各頂点の次数が XNUMX であるグラフ) ではうまく機能しません。
非常に単純なアイデアに基づいた別のアイデアもあります。グラフが切り離されている場合、その接続されたコンポーネントの問題は、最後に答えを組み合わせて独立して解決できます。 ちなみに、これはスキームに約束された小さな変更であり、解決策を大幅に高速化します。以前は、この場合、コンポーネントの応答を計算するために時間の積を計算していましたが、現在は時間の積を求めて計算しています。合計。 また、分岐を高速化するには、接続されたグラフを切断されたグラフに変える必要があります。

どうやってするの？ グラフに明確なポイントがある場合は、そこに向かって戦う必要があります。 アーティキュレーション ポイントは、削除されるとグラフの接続性が失われる頂点です。 グラフ内のすべての接合点は、古典的なアルゴリズムを使用して線形時間で見つけることができます。 このアプローチにより、分岐が大幅に高速化されます。

選択した頂点のいずれかが削除されると、グラフは接続されたコンポーネントに分割されます。

私たちはこれを実行しますが、さらに多くのことを望んでいます。 たとえば、グラフ内で小さな頂点のカットを探し、そこから頂点に沿って分割します。 最小のグローバル頂点カットを見つけるために私が知っている最も効率的な方法は、立方時間で構築される Gomori-Hu ツリーを使用することです。 PACE チャレンジでは、一般的なグラフ サイズは数千頂点です。 この状況では、再帰ツリーの各頂点で数十億の操作を実行する必要があります。 割り当てられた時間内に問題を解決するのはまったく不可能であることがわかりました。

ソリューションを最適化してみましょう。 頂点のペア間の最小頂点カットは、最大フローを構築する任意のアルゴリズムによって見つけることができます。 そのようなネットワークに入れることができます ディニッツアルゴリズム、実際には非常に速く動作します。 稼働時間の推定を理論的に証明できるのではないかという疑念がある 、これはすでにかなり許容されます。

ランダムな頂点のペアの間でカットを探し、最もバランスのとれたものを選択することを何度か試みました。 残念ながら、これはオープン PACE Challenge テストで悪い結果をもたらしました。 これを、最大次数の頂点を分割し、降下の深さに制限を付けて実行するアルゴリズムと比較しました。 この方法でカットを見つけようとするアルゴリズムにより、大きなグラフが残されてしまいました。 これは、カットが非常にアンバランスであることが判明したという事実によるものです。5 ～ 10 個の頂点を削除しても、15 ～ 20 個しか分割できませんでした。

理論的に最速のアルゴリズムに関する記事では、分割する頂点の選択にさらに高度なテクニックが使用されていることに注目してください。 このような手法は実装が非常に複雑で、時間とメモリの点でパフォーマンスが劣ることがよくあります。 実践に十分耐えられるものを特定できませんでした。

単純化ルールを適用する方法

私たちはカーネル化のアイデアをすでに持っています。 思い出させてください:

1. 孤立した頂点がある場合は削除します。
2. 次数 1 の頂点がある場合は、それを削除し、その隣接頂点を応答として受け取ります。
3. 少なくとも次数の頂点があれば k+1、 それを取り戻す。

最初の XNUMX つではすべてが明らかですが、XNUMX つ目ではトリックが XNUMX つあります。 バーに関する漫画の問題で、上限が与えられたとします。 k、PACE Challenge では、最小サイズの頂点カバーを見つけるだけで済みます。 これは、検索問題から意思決定問題への典型的な変換であり、多くの場合、XNUMX つのタイプの問題の間に違いはありません。 実際に、頂点カバー問題のソルバーを作成する場合は、違いが生じる可能性があります。 たとえば、XNUMX 番目の点のように。

実装の観点からは、XNUMX つの方法があります。 最初のアプローチは、反復深化と呼ばれます。 それは次のとおりです。答えに対して下からの合理的な制約を設定して開始し、その後、再帰でこの制約よりも下位に進むことなく、この制約を上からの答えに対する制約として使用してアルゴリズムを実行できます。 何らかの答えが見つかった場合は、それが最適であることが保証されます。そうでない場合は、この制限を XNUMX つ増やしてやり直すことができます。

別のアプローチは、現在の最適な答えを保存し、より小さい答えを探し、見つかったときにこのパラメーターを変更することです。 k 検索時に不要な枝をより多くカットするため。

夜間に数回実験を行った後、私はこれら XNUMX つの方法の組み合わせに落ち着きました。まず、検索深さに何らかの制限を付けてアルゴリズムを実行し (メインのソリューションと比べて時間が無視できるように選択します)、最適な方法を使用します。答えの上限として見つかった解、つまり同じもの k.

次数 2 の頂点

次数 0 と 1 の頂点を扱いました。 これは次数 2 の頂点で実行できることがわかりますが、これにはグラフからのより複雑な操作が必要になります。

これを説明するには、何らかの方法で頂点を指定する必要があります。 次数 2 の頂点を頂点と呼びましょう v、およびその近傍 - 頂点 x и y。 次に XNUMX つのケースを取り上げます。

1. 時 x и y - 隣人。 それなら答えてもいいよ x и yと v 消去。 確かに、この三角形から少なくとも XNUMX つの頂点を代わりに取得する必要があり、取得できれば絶対に負けません。 x и y: 彼らにはおそらく他にも隣人がいるでしょう、そして v 彼らはここにはいない。
2. 時 x и y -隣人ではありません。 次に、XNUMX つの頂点すべてを XNUMX つに接着できることが述べられています。 この場合、最適な答えが存在し、その中で次のいずれかを選択するという考え方です。 v、または両方の頂点 x и y。 さらに、最初のケースでは、すべての近隣諸国を対応させる必要があります x и y、しかしXNUMX番目ではそれは必要ありません。 これは、応答として接着された頂点を取得しない場合と取得する場合に正確に対応します。 どちらの場合も、そのような操作からの応答が XNUMX つ減少することに注意する必要があります。

このアプローチを公平な直線時間内に正確に実装するのは非常に難しいことに注意してください。 頂点の結合は複雑な操作であり、隣接する頂点のリストをコピーする必要があります。 これを不注意に行うと、実行時間が漸近的に最適ではなくなる可能性があります (たとえば、接着するたびに多くのエッジをコピーした場合など)。 私は、次数 2 の頂点からパス全体を見つけて、そのような頂点からのサイクル、または XNUMX つを除くすべての頂点からのサイクルなどの特殊なケースを分析することに落ち着きました。

さらに、この操作は可逆的であり、再帰から戻るときにグラフを元の形式に戻す必要があります。 これを確実にするために、マージされた頂点のエッジ リストをクリアせず、どのエッジをどこに配置する必要があるかだけを知っていました。 このグラフの実装にも精度が必要ですが、かなりの直線時間が得られます。 また、数万のエッジのグラフの場合、プロセッサのキャッシュに収まるため、速度の点で大きな利点が得られます。

線形カーネル

最後に、カーネルの最も興味深い部分です。

まず、XNUMX 部グラフでは最小頂点カバーが次の式で求められることを思い出してください。 。 これを行うには、アルゴリズムを使用する必要があります ホップクロフト・カープ そこで最大の一致を見つけて、定理を使用します。 ケーニッヒ・エゲルヴァリ.

線形カーネルの考え方は次のとおりです。まずグラフを分岐します。つまり、各頂点の代わりにグラフを分岐します。 v XNUMXつのピークを追加しましょう и 、各エッジの代わりに ユー - ヴ リブをXNUMX本追加しましょう и 。 結果のグラフは XNUMX 部構成になります。 その中で最小の頂点カバーを見つけてみましょう。 元のグラフの一部の頂点は XNUMX 回そこに到達し、一部は XNUMX 回だけ、また一部は決して到達しません。 ネムハウザー・トロッターの定理は、この場合、一度もヒットしなかった頂点を削除し、二回ヒットした頂点を取り戻すことができると述べています。 さらに、残りの頂点 (XNUMX 回ヒットした頂点) のうち、少なくとも半分を答えとして受け取る必要があると彼女は言います。

私たちはたった今、これ以上離れてはならないことを学んだところです 2k ピーク実際、余りの答えがすべての頂点の少なくとも半分である場合、合計でこれ以上の頂点は存在しません。 2k.

ここで私は小さな一歩を踏み出すことができました。 この方法で構築されたカーネルは、二部グラフでどのような種類の最小頂点カバーを採用したかに依存することは明らかです。 残りの頂点の数が最小限になるように XNUMX つ取りたいと思います。 以前は、時間内にのみこれを行うことができました 。 私はその時にこのアルゴリズムの実装を思いつきました したがって、このコアは、各分岐段階で数十万の頂点からなるグラフ内で検索できます。

結果

実際に試してみると、私のソリューションは数百の頂点と数千のエッジのテストでうまく機能することがわかりました。 このようなテストでは、10 分以内に解決策が見つかることが十分に期待できます。 原則として、グラフに十分な数の高い次数 (次数 XNUMX 以上など) の頂点があれば、許容可能な時間内に答えが見つかる確率は高くなります。

コンテストに参加するには、ソリューションを次の宛先に送信する必要がありました。 オプティアイオ。 そこで提示された情報から判断すると、 タブレット, 公開テストでの私の解法は、XNUMX 件中 XNUMX 位にランクされ、XNUMX 位と大きな差をつけられています。 正直に言うと、コンテスト自体でソリューションがどのように評価されるかは完全には明らかではありません。たとえば、私のソリューションは XNUMX 位のソリューションよりも少ないテストに合格しましたが、合格したテストではより高速に動作します。

クローズドテストの結果はXNUMX月XNUMX日に判明する。

出所： habr.com