問題タブ [np-complete]

私は、親と教師の会議をスケジュールするためのプログラムを書くことを志願しました。校長は、保護者に、英語と数学の先生を (同時に)訪問できる日時を 3 つ選択するよう求めています。

すべての保護者が 3 つの日時を選択したら、できるだけ多くの保護者が両方の教師と会うことができるように、保護者と教師の会議をスケジュールする最適な方法を見つけなければなりません。

(時間の都合で数学の先生が会議に出席できない場合、保護者は英語の先生とのみ会うことになります)

NP型の問題はよくわからないのですが、「最適」と「スケジュール」という言葉を一緒に聞くと不思議に思うのですが…

校長先生にはそれはできないと言いましたが、NPコンプリートなのか知りたかったのです。もしそうなら、以下があると仮定します：

• 500人の親
• 15名の英語教師
• 数学教師5人
• 25 の日時から選択

おばあちゃんのコンピューターで、これを数秒、数分、または数時間で正しく解決できますか?

（NDAの問題を回避するために、この質問の詳細を変更しました。文字通りに解釈すると、この理論上の会社を運営するためのより良い方法があることを認識しています。）

A 社が製造する 1000 個の製品のうち、それぞれが 200 個の異なる製品を保管および配送できる倉庫のグループがあります。各倉庫には 200 個の製品がストックされており、注文が割り当てられており、在庫から注文を処理します。

課題は、各倉庫が自給自足である必要があることです。任意の数 (通常は 5 ～ 10 個) の製品の注文があり、倉庫に割り当てられます。次に、倉庫は注文に必要な製品を梱包し、一緒に出荷します。倉庫で入手できない商品については、注文品を発送する前に、商品を個別に倉庫に配送する必要があります。

したがって、問題は、個々のアイテムを注文して待つことなく、可能な限り多くの注文を梱包できるように、最適な倉庫/製品構成を決定することにあります。

例 (それぞれが文字で表される製品と、5 つの製品ラインを保管できる倉庫を使用):

目標は、履歴データを使用して、将来的に個別に注文される製品の数を最小限に抑えることです。倉庫が特定の方法でセットアップされると、ソフトウェアは、最小限のオーバーヘッドで注文を処理できる倉庫を決定するだけです。

これは、機械学習スタイルの問題としてすぐに思い浮かびます。また、よく知られている特定の NP 完全問題の組み合わせのようにも見えますが、適切に適合するものはないようです。

このタイプの問題を表すモデルはありますか?

セットカバー問題を「解決」するのにどれくらいの時間がかかるかをテストするために、このプログラムを書きました。

これは貪欲な次善のソリューションですが、それでも実行に 147 秒かかりました。ただし、このソリューションは最適にかなり近いはずなので、私の目的には十分であると思います。どうすれば高速化できますか？

良いことよりも悪いことの方が多いので、いくつかの行をコメントアウトしました。編集：宇宙の計算は、実際にはタイミングから離れるべきではありません...それは事前に知ることができます。

私は NP 困難であると思われる組み合わせ最適化問題に取り組んでおり、遺伝的アルゴリズムは私たちのデータセットでうまく機能しています。私たちは研究グループであり、私たちの分野 (数学や CS ではなく) で結果を公開する予定です。原稿をレビューに送る前に、NP 困難な問題を調査したいと思います。

主な質問は 2 つあります。

1) この特定の最適化問題が研究されているかどうか知りたいです。私はライトを徹底的に検索しましたが、まったく同じものは見たことがありません.

2）問題が研究されていない場合は、還元可能性の証明を行うことに挑戦する可能性があり、還元のための優れたNP完全候補へのいくつかのポインターが必要です。

この問題は、サブシーケンス バリアントと 2 部グラフ問題の 2 つの方法で説明できます。

サブシーケンス フレーバーでは、順列を許可する「リラックスした」サブシーケンスを見つけ、最適化して順列数を最小限に抑えたいと考えています。例: (. = その他の文字)

クエリ: abc、ターゲット: ..babc、結果: abc (通常のサブシーケンス)

クエリ: abc、ターゲット: ..baca、結果: bac (1 つの順列を持つサブシーケンス)

二部定式化は、マッチング問題または線形代入問題であり、グラフはクエリ文字ノードとターゲット文字ノードに分割されます。エッジは、各クエリ文字からターゲット文字へのエッジが 1 つだけ存在するように、クエリ文字をターゲット文字に接続します。目的関数は、エッジ交差の数 (「交差数」とも呼ばれます) を最小化することです。これは、エッジの交差を最小限に抑えるためにノードの配置を並べ替える 2 部グラフ レイアウト アルゴリズムに似ていますが、私の問題では、両方のノードの順序が固定されている必要があります。

質問 1 または 2 に関する専門家からの意見はありますか?

前もって感謝します！

問題X（決定問題）がNP完全であることがわかっていて、多項式時間で問題Yに還元されることが証明されている場合、問題YはNP完全であると言えますか？

私の最初の考えは、いいえ、問題YはそれがNPにあることを示す必要があるということでした。しかし、さらに考えた後、XがYに縮小された場合、YはすでにNP完全であると見なされます。今、私は混乱しています...どんな助けもいただければ幸いです。

私の質問に対する「完璧な」解決策はおそらくないことを私は知っています（これはナップザックのバリエーションまたはビンパッキング問題のように聞こえます）が、これが私のシナリオです：

SQLデータベーステーブルのリストをn個（たとえば7個）のほぼ同じサイズのパイルに分割したいと思います（これにより、一部のメンテナンスタスクを1週間全体にほぼ均等に分散できます）。

サイズ1からサイズ10,000,000までの範囲の100個のテーブル（これは高くても低くてもかまいませんが、5000より高くなることはないでしょう）があるとしましょう（もちろん、大きなテーブルはそれほど一般的ではありません）。

私の当初のアイデアは、テーブルをアルファベット順に（疑似ランダムに）並べ替えてから、最初からウォークスルーし、合計がSum（Size）/7を超えると次のグループに移動することでした。一部のデータベースでは、これはおそらく正常に機能しますが、2つの巨大なテーブルが隣り合っている場合、これは非常に不均等なグループになります。（これは思ったほどありそうもないことではありません。Account_HistoryとAccount_History_Archiveの2つの巨大なテーブルを検討してください）。

さまざまなソースデータで「良好な」結果をもたらす、一般的に受け入れられている手法はありますか？私は、より正確なグループ化ではなく、より単純な手法に傾倒します（メンテナンスが他の日よりもわずかに長く実行される場合、それほど大きな問題ではありません）。

「G がサイズ k のクリークとサイズ k の独立集合の両方を持っているかどうか、与えられた入力 G と k を決定することが NP-Complete であることを証明してください。これは 2 ではなく 1 つの問題であることに注意してください。答えは、次の場合にのみ「はい」です。 G にはこれらのサブセットの両方があります。」

この問題は私のアルゴリズム コースで出されましたが、大勢の学生がそれを理解できませんでした。ここに私たちがこれまでに持っているものがあります...

クリーク問題と独立集合問題の両方が、それ自体で NP 完全であることはわかっています。いくつかの「証明書」がNPにある場合、この問題の検証が行われることもわかっています。

この問題は、上記の問題 (独立集合とクリークの両方を含む) を、完全にクリークまたは独立集合で構成される問題のいずれかに縮約することです (少なくとも、それは私たちが行う必要があると考えていることです)。リダクションを元の形式に戻すために必要な情報を失うことなく、このリダクションを実行する方法はわかりません。

私は立ち往生している問題があり、どこから始めても見つからないので、どうしようもなくスタックオーバーフローに目を向けています。

この問題は、それが np-hard か多項式かを調べ、np-hard が np-completeness を証明する場合、そうでない場合はアルゴリズムを提供することを求めています。

問題は次のとおりです。

n 個のモジュールからなる製品が存在します。各モジュールを構築できる会社が 2 つありますが、費用はかかります (c_ij、i: モジュール番号、j: 会社番号)。モジュール a と b が別の会社によって構築されている場合は、追加コスト (p_ab) もかかります。モジュール a と b は連続している必要はありません。a と c にも同じ追加コストが適用されます。予想どおり、この問題は、総コストが最小になるように、企業へのモジュールの割り当てを見つけることを望んでいます。

何か案は ？

大きな (数千ノード) 有向グラフGと、はるかに小さい (3-5 ノード) 有向グラフgがあるとします。Gにgの同型がいくつあるかを数えたいと思います。言い換えれば、G内の一意のノード セットがgに一致する数を知りたいのです。これはサブグラフ同型問題のインスタンスであり、したがって NP 完全であることを認識しています。ただし、 gが小さいと仮定すると、これを行うための合理的に効率的なアルゴリズムはありますか?

最初に言っておきますが、私は理論などについてよく知りません。しかし、これが NP なのか NP 完全な問題なのか疑問に思っていました。具体的には、部分和問題の特殊なケースのように聞こえます。

とにかく、私が最近プレイしている Alchemy というゲームが、この考えを促しました。基本的には、4 つの基本要素から始めて、それらを組み合わせて他の要素を作成します。

たとえば、要素を作成する場合、これは短い「レシピ」です。

では、コンピュータが 4 つの基本的な要素しか作成できなかったとしますが、要素の複数のセットを作成できます。したがって、他の要素を組み合わせて任意の要素を作成するプログラムを作成します。このプログラムは、電球を作成するリストをどのように処理しますか?

明らかに、火+空気=エネルギー、土+土=砂、砂+火=ガラス、エネルギー+ガラス=電球です。

しかし、リストを処理するプログラムを作成し、ブルートフォース型のメソッドを実行してすべての要素を調べ、そのレシピを確認することなくそれを理解する方法は考えられません。

これはNPの問題ですか？それとも、これを理解できないだけですか？