問題タブ [np-hard]

二分木をk個の同様のサイズの部分に分割しようとしていました（k-1個のエッジを削除することにより）。この問題に対する効率的なアルゴリズムはありますか? それともNP困難ですか？論文、問題定義などへのポインタはありますか?

-- パーティショニングの品質を評価するための 1 つの妥当なメトリックは、最大パーティションと最小パーティションのサイズのギャップです。別のメトリックは、できるだけ多くの頂点を持つ最小のパーティションを作成することです。

私は割り当て問題の変種のように見える問題に取り組んでいます。サーバーに割り当てる必要があるタスクがあります。サーバーにかかるコストの合計を最小限に抑える必要があります。次の条件が成り立ちます。

1. 各タスクには単位サイズがあります。

2. タスクを複数のサーバーに分割することはできません。タスクは、厳密に 1 つのサーバーによって処理される必要があります。

3. サーバーには、割り当てられるタスクの最大数に制限があります。

4. タスク割り当てのコスト関数は階段関数です。サーバーには最小コスト「a」が発生します。サーバーが処理するタスクごとに、コストは 1 ずつ増加します。特定のサーバーに割り当てられたタスクの数がその容量の半分を超えると、そのサーバーのコストは正の数 'd' に等しくなります。

   4. タスクにはプリファレンスがあります。つまり、特定のタスクをいくつかのサーバーのうちの 1 つに割り当てることができます。

これは NP 困難な問題であると感じていますが、マッピングする NP 完全問題を見つけることができないようです。Bin Packing、Assignment problem、Multiple Knapsacks、bipartite graph matching を試しましたが、これらの問題のどれも、私の問題のすべての重要な特徴を持っていません。それに対応する問題を教えてください。

よろしくお願いします

サキブ

最小セット カバーは、すべての要素をカバーするために必要なセットの最小数を見つけなければならない問題です。たとえば、 の集合X=array(1,2,3,4,5,6)と 5 つの別の集合 S があると想像してください。ここで、

問題は、X のすべての要素をカバーする S のセットの最小数を見つけることです。したがって、明らかに、この場合の最小セット カバーはS[4]andS[5]になります。これらはすべての要素をカバーするからです。このコードを C++ で実装する方法を知っている人はいますか? これは NP 完全であるため、高速なアルゴリズムで解決できないことに注意してください。C++ でのソリューションはすべて歓迎されます。ところで、これは宿題ではありませんが、ソリューションの最後の部分を生成するために、 Quine–McCluskeyプロジェクトでこのアルゴリズムを使用する必要があります。
前もって感謝します。

これは、このサイトでの最初の質問です。

最近、NPについて勉強しています。私はこのトピックについていくつかの混乱を抱えており、私の推論を提案し、誰かが私を検証したいと考えています.

I) 各 NP 問題は Exponential Time で解くことができます。

II) P=NP の場合、NP=NP-完全。

III) 2素因数分解の問題、NPです。

IV) 問題 X が既知の NP 困難な問題に還元できる場合、X は NP 困難である必要があります。

誰かが私の推論を検証し、私を学ぶことができますか?‌

要素の合計を最大化する実数の配列のKサイズのばらばらで連続したサブセットを見つけるアルゴリズムを見つけようとしています。Lx

詳細を説明すると、X は N 個の正の実数のセットです。
X={x[1],x[2],...x[N]} where x[j]>=0 for all j=1,...,N.

呼び出される長さ L の連続するサブセットは、 position で始まり positionで終わるS[i]X の L 個の連続するメンバーとして定義されます。n[i]n[i]+L-1
S[i] = {x[j] | j=n[i],n[i]+1,...,n[i]+L-1} = {x[n[i]],x[n[i]+1],...,x[n[i]+L-1]}.

そのような部分集合のうちの 2 つS[i]とS[j]は|n[i]-n[j]|>=L、つまり、X の同一のメンバーは含まれていません。

各サブセットのメンバーの合計を定義します。

目標は、最大化 S[1],S[2],...,S[K]されるように、長さ L のK 個の連続したばらばらの (重複しない) サブセットを見つけることです。SUM[1]+SUM[2]+...+SUM[K]

私は複雑さの証明にいくつかの困難があります:私は3つの問題を扱っています:A、B、C私は知っています:

• A-> B
• A-> C
• C -> B

A-> B 意味: A に対して「はい」の答えがある場合、B に対して「はい」の答えがあります。A が NP に属し、B と C が NP 完全であることを知っています。さらに、C への 2 次数の呼び出しを使用して A のアルゴリズムを作成できます
。A の複雑さについて何か推測できますか?

より正確に言うと、k 個のオブジェクトのセット P があります。問題 A は、これらのオブジェクトがすべて削除された場合は「はい」と答え、それ以外の場合は「いいえ」と答えます。問題 C は、これらのオブジェクトの 1 つを削除できる場合は「はい」と答え、それ以外の場合は「いいえ」と答えます。各ステップで少なくとも 1 つのオブジェクトを削除する必要があるという制約があります。最悪の場合、P ステップを作成します。したがって、 A のアルゴリズム:

巡回セールスマン問題の修正版を解こうとしています。これは基本的な TSP の修正であり、すべてのノードが色のプロパティを持ち、最適なパスが同じ色の 4 つを超えるノードに連続して接触することはできません。これは、100 ノード以下の接続グラフで実行されます。Concordeを使用してこれを実行しようとしています。

コンコルドの実行に色の制約を追加する方法を知っている人はいますか?

ありがとう