問題タブ [np-complete]

私は集合I={P1、P2、...、Pm}を持ち、次のようにR1、R2、...、Rnで表されるIのn個の有限部分集合を持っています。

R1 = {P1、P2}

R2 = {P2、P4}

R3 = {P2、P3、P4}

R4 = {P1、P2、P4}

...。

ここで、円周率は整数を示します。

Riごとに、そのすべての要素の積を計算したいと思います。私の目的は、Ri（i = 1,2、...、n）間でいくつかの共通部分を共有することにより、乗算と除算をできるだけ少なくすることです。

たとえば、最初にP2 * P4を計算できる場合、この結果はR3とR4のすべての要素の積を計算する際に使用できます。

除算も許可されていることに注意してください。たとえば、最初にA = P1 * P2 * P3 * P4を計算し、次にA / P1を使用してR3のすべての要素の積を計算し、R4にA/P3を使用できます。

最小の乗算と除算を使用して、Iのすべてのサブセットのすべての積を計算したい場合、それは集合被覆問題ですか？NP完全？ところで、ここのようにそれを記述するために整数線形計画法の定式化を与えることができますか？

どんな提案でも大歓迎です！

コミュニティ編集：追加の仮定：

• 乗算と同じコストで、除算が許可されます
• 特定のセットに繰り返される要素はありません。例：R5 = {P1, P1, P1, P2}許可されていません

関連する質問:

• 数値のリストを 2 つの等しい合計リストに分割するアルゴリズム
• リストを 2 つの部分に分割し、それらの合計が互いに最も近くなるようにします

2k正確に要素を含むリストがあるとしましょう。ここで、それを 2 つの部分に分割します。各部分の長さは ですが、部分kの合計ができるだけ等しくなるようにします。

簡単な例: [3, 4, 4, 1, 2, 1]に分割される可能性が[1, 4, 3] and [1, 2, 4]あり、差額の合計は1

ここで、パーツが任意の長さを持つことができる場合、これは分割問題のバリエーションであり、弱いことがわかっています。NP-Complete.

しかし、リストを等分に分割することに関する制限(常にkとであるとしましょう2k) は、この問題を多項式時間で解決できるようにしますか? それに対する証拠はありますか（またはそれがまだであるという事実の証明スキームNP）？

私の問題はここの問題と似ていますhttps://cs.stackexchange.com/questions/2244/need-a-np-complete-proof-on-an-exampleですが、少し異なります。

これが私の問題です：

A、B、Cの3つの島があり、扇型の筏がたくさんあります。A-->B-->C から橋を架ける必要があり、各部分に必要なラフトの数は既にわかっています。たとえば、AB を接続するには 4 つのラフトが必要であり、BC を接続するには 3 つのラフトが必要です。

これらの筏はもともと別の位置にあり、コストをかけずに回転できます。興味深いのは、必要に応じてそれらを重ねることができることです。1 台のラフトが移動する距離は、重心の元の位置とその展開位置の間の距離として計算できます。

目的は、橋 A-->B-->C を実現し、橋の各部分の筏の正確な数を使用して、筏を移動する最小の合計距離を持つ解を見つけることです。

私は自分の質問を示すために次の図を使用しました。

この図から、配置が直線ではない可能性があり、筏が別の筏と重なる可能性があることがわかります。

これらの筏の候補地が多すぎます。問題はNPCのようです。自分が正しいかどうか、NPC であることを証明する方法がわかりません。誰でもそれを解決する方法を知っていますか? ありがとう！

0-1ナップサック問題はNP完全として知られています。しかし、各アイテムの重みが同じである場合、問題はまだNP完全ですか？

Given a undirected graph G=(V,E), each edge is associated with a non-negative value.

How to find the maximum number of vertex-disjoint paths from s to t on the graph G, with a constraint that the sum of paths length is not greater than a predefined value T.

長さ x 幅 で定義された複数のサイズのビンがあるとしましょう。それらは「原材料」のサイズと呼ぶことができます。

原材料の量を最小限に抑えるために、その原材料から一定量のテーブル (長方形、ギロチン形式) を切り取る必要があります。

ビンのサイズが同じではないため、それらの値を反映するために、何らかの方法で因数分解するか、優先順位を付ける必要があります。したがって、ビンが大きいほど、明らかに「より高価」になります。

私はこれが NP 完全問題であることを知っており、多項式時間での決定論的アルゴリズムを期待していません。

問題を解決するアルゴリズムが必要です。

どんな提案も役に立ちます！

ありがとう

容量の異なるビンと、指定されたサイズのオブジェクトがあります。目標は、これらのオブジェクトをビンに詰めることです。これまでは、ビンパッキング問題に似ています。しかし、ねじれは、各オブジェクトが別のオブジェクトと部分的にオーバーラップしていることです。したがって、オブジェクト1と2のサイズはs1とs2ですが、同じビンに入れると、埋められたスペースはs1+s2未満になります。オブジェクトの各ペアについてこの重複する値を知っていると仮定すると、この問題の元のビンパッキングのような近似アルゴリズムもありますか？

エッジとノードの両方に重みがあるグラフ G=(V,E) があります。このグラフを分割して、同じサイズのパーティションを作成したいと考えています。パーティションのサイズの定義は、sum(vi)-sum(ej) です。ここで、vi はそのパーティション内のノードであり、ej はそのパーティション内の 2 つのノード間のエッジです。私の問題では、グラフは非常に密集しています（ほぼ完全です）。そのための近似アルゴリズムはありますか？

これは、ビンのサイズが同じでオブジェクトが重なっているビン パッキングの問題と似ています。ノードの重みはノードのサイズであり、エッジの重みは 2 つのオブジェクトがどれだけオーバーラップできるかを示します。

さまざまな整数の長さの道路で接続された町のネットワークがあります。

旅行者は、ある町から別の町へ車で移動したいと考えています。ただし、彼は移動距離を最小限に抑えたくありません。代わりに、彼は旅のガソリン代を最小限に抑えたいと考えています。ガソリンはどの都市でも購入できますが、各都市はさまざまな (整数の) 価格でガソリンを供給します (したがって、最短ルートが必ずしも最安値であるとは限りません)。ガソリン 1 単位で、彼は 1 単位の距離を運転できます。彼の車は、タンクに入れることができるガソリンの量に制限があり、移動する各都市で購入するガソリンの単位を選択できます。最低ガソリン代を求めよ。

この問題を解決するために使用できる効率的なアルゴリズムを知っている人はいますか? このタイプの問題の名前でさえ、私が自分で調査できるように役立つでしょう! 明らかに、最短経路問題とはまったく同じではありません。その他のヒントをいただければ幸いです。

編集-私が抱えている実際の問題は、1000未満の都市があると述べています。<10000 道路; ガソリンタンクの容量は 1 から 100 の間になります。

グラフ彩色のNP完全性を理解するのに苦労しています。

DFSで貪欲な彩色戦略（http://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring）を想定すると、グラフを最適に彩色できるようです。誰かが反例で私を助けてもらえますか？

明確にするために、すべてのノードを-1に色付けします。開始ノードに色を付ける1.隣接ノードにまだ割り当てられていない最小の整数ですべてのノードに色を付けるDFSトラバーサルを続行します。これがグラフの最適な色付けに失敗するのはいつですか？