おそらく、誰もが困難な課題に直面しなければならなかったという事実に直面しました。その解決策は、すぐにだけでなく、頑固な長時間の作業や数日後でも見つけることができませんでした。今日は、そのような問題のクラスの1つであるNP-completeについて説明します。
一般的に、日常生活の中でそのような課題に取り組むことは現実的ですか？実際、それらは非常に多くの場合に発生します：組み合わせ、グラフとネットワーク、論理式の実行、マップの操作、最適な負荷、マップ、離散最適化問題、最長のシーケンスの検索、等しい合計の検索、および多くのセットの問題！そして、これは完全なリストではありません。
カットの下には、非公式のガイドがあります-目の前にNPの問題がある可能性があることを理解する方法と、これが正確に判明した場合の対処方法。今日、私たちはこの問題を実際的な側面から攻撃しています。
彼女が本当にあなたの前にいることを確認してください
NP完全な問題に直面したとき、どのようにしてわかりますか？まず、最も単純な検出ヒューリスティックは、類似したものを判別するために、既知のNP完全問題を検索することです。たとえば、そのようなリストは多数あります。
次に、タスクの次のプロパティを検討します。
- スペースexp（n）からn個の要素が含まれるソリューションを選択する必要があります。
- このスペースから長さnの解がすでにある場合は、簡単に（多項式で）チェックできます。
- 決定要素の1つを選択すると（場合によって）、他のすべて（必ずしもすべてではない）の選択に影響します。
- 最悪の場合、単純な列挙によって指数空間全体を考慮して、オプションを常に列挙することができます。
- パラメータn-ソリューションの長さまたはスペース自体には固定値がありません。つまり、常に固定されている8 x 8のチェスボードについてではなく、N xNの問題の一般的な形式について説明しています。
NP-complete問題のプロパティについて詳しくは、こちらとこちらをご覧ください。
このリストでの作業の例
最近NPコンプリートとして承認された問題の簡単な例を挙げましょう！
記事の資料に基づいています。すでにK <= Nがボードに配置されている場合は、サイズN x NのボードにN個のクイーンを配置する必要があります（元の科学記事の写真）
まず、部分的に制約されたラテンスクエアNPに関する非常に類似した問題が完了していることに注意してください。
次に、リストを確認します。
- スペースexp（N）（= N ^ 2 *（N ^ 2-1）* ....）からN個のクイーンを見つける必要があります。
- N個のクイーンの解決策を確認するのは簡単です。各クイーンについて、対角線、垂直線、水平線を確認する必要があります。
- 1つを設定すると、他の多くの選択が無効になります。ソリューションの要素間には依存関係があります（クイーンを個別に配置することはできません）。
- ここでは、exp（N）で任意に選択したボードのブルートフォースによって問題を解決できます。最初のボードを（i、j）の位置に、2番目のボードを他の空いているボードに配置します。バックトラックは解決策を見つけることが保証されています。
- 問題には固定パラメータがありません。つまり、一般的な形式で定式化され、Nが大きくなるにつれて、複雑さも大きくなります。
ボードがクリーンでタスクが簡単になることが常にわかっている場合は、リストの項目の1つが失敗することに注意してください。
さらに、これは条件付きの実用的なアプローチであり、NP完全な問題を検出するためのヒューリスティックです（すべての長所と短所があります）。
混合
出典
なぜ、同様の問題を抱えているのに、NPの問題に直面していることを正式に理解するのは簡単ではないのですか？私たちは本当にNPの問題を自分たちに向ける必要があります。そうすれば、私たちの問題がNPハードであることを確実に知ることができます。そして、上記のリストのようにそれをシミュレートできた場合、それは完全です。つまり、少なくともNPでNP以下であり、実際には「NP問題の中で最も難しい」（残りのNP問題と同様）。
さて、私たちはそれが必要ですか？実際には、すべてのチェックの後で、NPの問題に直面していることが率直である場合、科学的な記事を書いていなければ、何も証明する必要はありません。
そして、あなたはどちらかが必要です（これについては以下で話します）：
- そのようなタスクを解決するシステムを使用してタスクをシミュレートします。
- あなたのケースで十分に速く機能する解決策を見つけてください。
- 私たちを満足させるおおよその解決策を見つけてください。
あきらめないで！
最も重要なことは、寸法を評価することです-パラメータと現実的なシナリオ！
xkcd.com/287
たとえば、パラメータの値が固定されていないにもかかわらず、条件付きN <100がすべての実際のシナリオで実装されているわけではないことを知っています。つまり、条件付き列挙が実際の解決策になる可能性があります。
あなたはあなた自身のために決定する必要があります：可能で実際にシステムに入るパラメータの私の実際の値は何ですか、データの一般的な分布と特徴は何ですか、実際のものとそうでないものは何ですか？最適なソリューションが必要ですか？これらのポイントを見ていきましょう。
入力データの配布
または、一般的な場合、入力データは任意であるという事実にもかかわらず、クイーンの例を使用すると、通常は1つのクイーン、またはまったく固定されません。つまり、90％の確率で非常に単純なソリューションを使用でき、極端な場合にのみ複雑なソリューションを呼び出すことができます。
平均して、すべての通常の組み合わせが単純な場合の例：クイーンを補完する問題-条件付きDFS +ヒューリスティックは、ほとんどの場合、非常に迅速に解決策を見つけることができ、非常に非標準的な状況でのみ非常に困難になる可能性があることがわかっています。
これは、非常に特殊なNP完全タイリング問題のソリューションが、ロジックプログラミングメソッドを使用してそのような問題のクラス全体をモデル化するための一般的なメソッドに対してどのように評価されたかの例です。
（Relational Data Factorization（Paramonov、Sergey; van Leeuwen、Matthijs; De Raedt、Luc：Relational data factorization、Machine Learning、volume 106）の記事から）
まず、特別なLTM-kソリューションと一般的な方法の速度が大幅に異なります。したがって、このタイプの問題に対するヒューリスティックベースのソリューションは、この問題を完全に解決できます。
第二に、ソリューションの品質を犠牲にすることにより、一般的な近似方法は非常に類似した速度を与えました。
ヒューリスティックと近似
最後の最も強力なツールは、Answer SetProgrammingなどのNP完全な問題モデリングシステムを使用することです。
論理プログラミング言語の詳細。
たとえば、クイーンの配置の問題の解決策は次のようになります。
% domain
row(1..n).
column(1..n).
% alldifferent: guess a solution
1 { queen(X,Y) : column(Y) } 1 :- row(X).
1 { queen(X,Y) : row(X) } 1 :- column(Y).
% remove conflicting answers: check this solution
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 == Y2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.
異なる数のクイーンNの解を見つけるための簡単な実験を実行すると、次のようになります。X軸に沿って-クイーン、Yに沿って-1秒あたりの時間で解を見つけます。
時間の増加は明らかに多項式ではない（論理的である）という事実にもかかわらず、適切な数のクイーンとボードサイズでうまく機能していることがわかります。
次に、実際のボードの寸法がわかれば、この正確なソリューションが実際のシステムでどのように受け入れられるかを理解できます。
結論
チェックリストの形で記事からのアイデアを調べてみましょう
- 本当にNPの問題があると判断します。
- 現実的なパラメータ値とデータ分布が何であるかを理解します。
- 書いてみてください（順序は開発者やタスクによって異なります）：
- 正確なヒューリスティックソリューション（私たちの分析に基づく）-それは十分に速いでしょうか？
- — ?
- NP- — ? , CPU ? .
- : , .
- — , — . !
:
