問題タブ [np]

ウィキによると、ポリ時間の np complte 問題を A に変換すると、 A は np ハードです。http://en.wikipedia.org/wiki/NP-hardを参照

しかし、以下の pdf は、多項式時間で np ハード問題を問題 A に変換すると、A は np ハード http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard であると述べています。 pdf

どっちを信じればいい?

私はこの問題に対して合理的なアルゴリズムを考え出そうとしています:

ボールがたくさんあるとしましょう。各ボールには少なくとも 1 つの色がありますが、多色にすることもできます。各ボールには、それに関連付けられた重量と値があります。ワンカラーのボックスもたくさんあります。各ボックスには、保持できるボールの最大数があります。目標は、合計の重みWを維持しながら、ボックス内の値の合計を最大化することです。唯一のルールは次のとおりです。

ボールを箱に入れるには、少なくとも箱の色がなければなりません。

(たとえば、青と緑のボールを青のボックスまたは緑のボックスに配置できますが、赤のボックスには配置できません。)

私はいくつかの調査を行いましたが、これはナップザックの問題に似ており、ハンガリーのアルゴリズムで解決できるようにも見えますが、どちらの問題にも還元できないようです。

この種の問題を多項式時間で解けるようにする動的計画法アルゴリズムがあるのか​​、それとも単なる巡回セールスマンの問題であるかに興味があります。色数が最大で X であることを知っていれば役に立ちますか? どんな助けでも大歓迎です。それが助けになるなら、変数名で問題を少し形式化することもできます。ありがとう！

簡単な例を次に示します。

最大重量: 5

ボール:

赤いボール 1 個 - (値 = 5、重み = 1)

1 個の青いボール - (値 = 3、重み = 1)

緑/赤/青のボール 1 個 - (値 = 2、重み = 4)

緑/青のボール 1 個 - (値 = 4、重み = 1)

赤/青のボール 1 個 - (値 = 1、重み = 1)

ボックス:

赤 1 個 (ボール 1 個を保持)

青1個（ボール2個入り）

グリーン 1個（ボール1個入り）

最適解:

赤い箱の赤いボール

青い箱に入った青いボールと赤/青のボール

緑の箱に入った緑/青のボール

合計値: 13 (5 + 3 + 1 + 4)

総重量: 4 (1 + 1 + 1 + 1)

注: 緑/赤/青のボールは赤/青のボールよりも価値がありましたが、その重さから限界を超えていたでしょう。

編集：

1 つの明確なポイント: 同じ色の組み合わせのボールは、必ずしも同じ重量と値を持つとは限りません。たとえば、値が 3 で重みが 1 の赤いボールと、値が 2 で重みが 5 の別の赤いボールを作成できます。

編集2：

動的計画法アルゴリズムを考え出すのに役立つ場合は、整数の重みと値を想定できます。

プロジェクトに取り組んでいると、この問題に遭遇しました。ここでは、問題の実際の領域外の用語で言い換えます (花火と形状の口径について話すことはできると思いますが、理解がさらに複雑になります)。それを解決するための（おそらくおおよその）アルゴリズムを探しています。

さまざまなサイズのn 個のコンテナーと、さまざまなサイズの職業とさまざまな色の m個のオブジェクトがあります (オブジェクトは多色になる可能性があるため、オブジェクトの色は本当にセットです)。

私の目的は、コンテナーごとにさまざまな色が最小限に抑えられるように、すべてのオブジェクトをコンテナーに収めることです (それが可能であることは既にわかっています)。「色の種類が最小限に抑えられている」とは、コンテナごとの異なる色の数の合計が最小限であることを意味します。

例。サイズ 2 の 2 つのコンテナと、{red}、{red, green}、{blue}、{blue, green} の色を持つ 4 つのオブジェクトがあり、それぞれのサイズは 1 です。最適なソリューションは [{red} 、{赤、緑}]、[{青}、{青、緑}]、合計の種類は 2+2=4 です。悪い解決策は [{red}, {blue}], [{red, green}, {blue, green}] で、合計の種類は 2+3=5 です。

私の推測では、ナップザックの問題よりも難しいように聞こえるので、この問題は NP 困難であると思います。オブジェクトの値は負の値に変換され、さらに同じコンテナー内の他のオブジェクトに依存します。しかし、おおよその解決策を得るために問題に取り組む方法については、私には良い考えがありません。とにかくそれは大歓迎です。

入力: n 要素の M 個の順序付きタプルのセット。各要素はセットです。つまり、(A1、A2、...、An)、各 Ai はセットです。

問題: これらの n タプルを組み合わせて、n タプルの最小セットを作成します。2 つの n-タプルは、1 つの位置のみが異なる場合、つまり次のように組み合わせることができます。

A = (A1, A2, ..., An) と B = (B1, B2, ..., Bn) は (A1, A2, ..., Ai U Bi, Ai+1, ..) に結合できます。 ., An) iff Aj = Bj, for every j != i.

例: 入力: 4 2 タプル: ({1}, {1}), ({1}, {2}), ({3}, {1}), ({3}, {2}) 出力: 1 つの 2 タプル: ({1, 3}, {1, 2})

私の質問は、この問題にどのようにアプローチしますか? 既知のNP問題に還元できるかどうか知っていますか? 1 つのアイデアは、これをグラフとしてモデル化することです。タプル A と B を組み合わせることができる場合、色 i (i = それらが異なる位置) でそれらの間に色付きのエッジを描画します。

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

私は航空運送会社の管理業務を行っています。彼らはここで航空機用コンテナなどを製造しています。彼らが私にコーディングしてほしいことの 1 つは、フロアの担当者が特定の資料を最大限に活用するために使用できる注文最適化スクリプトです。概要を簡単に説明すると、1 ユニットあたり 10 メートルの一定量のビームを注文するとします。5x 6m、10x 3.5m、4x 3m のビームチャンクが必要です。これらは、10m をより小さな部分にカットすることによって得られます。注文する必要がある 10m ビームの最小数量はどれくらいですか?

マルチプロセッサのジョブ スケジューリング問題 (1 つのビームがプロセッサで、各チャンクがジョブ) といくつかの類似点があります。 -時間を設定します。マルチプロセッサ ジョブ スケジューリングの問題は NP 完全ですが、私のバリエーションの問題も同様ではないでしょうか。同様の問題とそれらを解決するための方法を知っている人はいますか？

80 個のノードがあり、サイクルが移動する距離を最小限に保ちながら、これらから長さ 40 のサイクルを見つける必要があります。一部のノードは直接接続できません。それらは特定のエリアにあり、あるエリア内ではなく、あるエリアから別のエリアにしか移動できません。

ここで一般的に質問しているだけですが、40 ノードの最適な (最短の) サイクルを得るには、どのような手法を使用できますか? これまでのところ、基本的な置換オプティマイザーと貪欲な DFS だけを作成しました。今から始めるのに最適なアプローチは何だろうかと思いますか？

問題がNP完全であると言うことが本当に何を意味するのか理解できないようです。誰かが次の質問で私を助けてもらえますか？

NP完全問題は、多項式時間でそれを解くためのアルゴリズムが存在しないことを証明できる問題です。その声明は本当ですか？

このようなアルゴリズムがNP完全問題に存在しないことを誰かが実際に証明できるので、このステートメントは真実ではないと言いたいと思います。さまざまな情報源を調べてみると、NP完全問題の多項式時間アルゴリズムは知られていないことがわかります。ただし、それを証明することはできません。

どんな助けでも大歓迎です。ありがとう。

SOの回答の1つで次を読みました。

巡回セールスマン問題は、通常、すべての都市を結ぶ最も安いルートを見つけることです。これは意思決定の問題ではなく、提案された解決策を直接検証することはできません。これを決定問題として言い換えることができます: コスト C が与えられた場合、C よりも安いルートはありますか? この問題は NP 完全であり、少しの作業で元の TSP を、変更された NP 完全な形式とほぼ同じくらい簡単に解くことができます。したがって、TSP は少なくとも NP 完全問題と同じくらい難しいため、NP 困難です。

TSP が NP-Complete であることは理解していますが、どのように問題が NP-Hard なのですか? NP にあるが P にない問題は NP-Hard であると読みました。このことを TSP に関連付けることはできません。これを説明してください。

与えられたものは3つ

1) 'n' 個の正負の整数の配列。2) 数値「x」。3) 演算子: 「+」、「-」、「%」、「/」

配列を評価すると結果が「x」になるような式を配列で形成します。

たとえば、配列 [5,3,-1,6,2,3] と x=2 を考えてみましょう。1 つの可能な解決策は次のようになります。

5 / 3 + (-1) + 6 / 2 - 1

5 / 3 の結果が 1 であると仮定します (常に整数除算)。

これのもう 1 つの複雑なバリエーションがあります。

この問題の複雑な変形では、BODMASS ルールが適用されないと仮定します。したがって、任意の時点で要素「m」をトラバースすると、中間結果「y」が得られます。'y' と a[m + 1] には任意の演算子を適用できます。

たとえば、バリアント 1 では、

5 + 3 - 2 / 2 = 7 (2 / 2 が最初に評価されるため、5 + 3 - 1)

バリアント 2 では、

5 + 3 - 2 / 2 = 3 (5 + 3 = 8。配列は 8 - 2 / 2 に縮小されました。現在、8 -2 = 6。配列は 6 / 2 に縮小され、3 に評価されます)。

アルゴリズム/数学/DS の専門家ですか?

これはNPハードですか？