問題タブ [np-hard]

複雑な名前で申し訳ありませんが、当然のことです。問題を提示させてください。

コンテキスト: パーティショニングを行いたいタイプのロケーション ネットワークがあります。

問題の定義: 頂点 V、辺 E、および辺の重み W のセットを持つ無向重み付きグラフ G = {V,E,w} があります。辺は V のすべての頂点の間に存在します。

ここで、サイズ |C1|...|CN| のサイクル C = {C1...CN} があります。st |C1|...|CN| の合計 頂点の総数 |V| に等しい。サイクル Ci のスコアは、パスに含まれるすべてのエッジの重みの合計です。

最後に、目的は次のとおりです。C のサイクルが互いに交差しないという制約の下で、C のすべてのサイクルを組み合わせたスコアが最大になるように、C のすべてのサイクルを G に適合させたいと考えています。

したがって、素人の言葉で言えば、定義された長さのサイクルでグラフを埋めたいと思います。グローバルな重みは最適です。

この問題に対する私の見解: この問題は、パッキング問題やハミルトン サイクルのようなものに還元できるため、少なくとも NP 困難です。

最適解は疑似多項式でさえない可能性があります。問題をいくつかの異なる方法 (グラフ) で定式化しようとしましたが、常に状態爆発が発生するため、扱いやすい 2D 動的プログラミング アプローチはおそらく不可能です (間違っている場合は訂正してください)。

したがって、おそらく近似アプローチを使用する必要があるようです。頭に浮かぶことの 1 つは、独自の近似アプローチを使用して、グラフ全体のハミルトニアン パスを見つけようとすることです。次に、次のステップは、局所最適ハミルトニアン パスを「カット」してサイクルを生成する場所を見つけることです。|C|!*|V| があります。これらの「カットサイト」を配置する方法。階乗は、これらのサイクルと |V| の順序の順列から得られます。開始位置の総数から得られます。剪定を行っても (つまり、同じサイズのサイクルが存在する場合)、これは大きな |C| に対しては依然として扱いにくいものです。小さい |C| の場合は力ずくで問題ないと思いますが、大きい |C| の場合は局所最適配置の近似値を得るために山登り法が必要になります。

ところで、皆さんどう思いますか？

私の問題はここの問題と似ています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 であることを証明する方法がわかりません。誰でもそれを解決する方法を知っていますか? ありがとう！

if l1 is in NP-HARD、したがって、すべての L2!=空のセットに対して、l1*l2 is in np-hard.

いつ：

それは真か偽か、そしてその理由は?

私はそれを承認できませんが、反例も見つかりません。

たとえば、一連の文字列があるとします。

初期文字列を構築するために使用できる部分文字列の最適な「レキシコン」を見つけたいと思います。基準は、レキシコンとそのレキシコンを使用する文字列の両方を格納するために必要なメモリの最小量です。

たとえば、指定された文字列のセットの場合、部分文字列の最適なレキシコンは次のようになります。

次の方法でエンコードされた文字列の初期セットを使用します (それぞれ\Nがレキシコンからの文字列 N への参照を表します)。

元の文字列の 22 文字 + 元のアルファベットを構成する 8 文字に対して、文字列を作成するために使用される合計 8 つの参照 + レキシコンを格納するために必要な 14 文字。フットプリントの正確な式が必要な場合は、 と仮定しsizeof( reference ) == sizeof( char )、1 つの文字列 (エンコードされた文字列とレキシコン内の両方) のフットプリントは であり、length of string * sizeof( char or reference )追加のオーバーヘッドはありません。

この問題を解決するための最適なアルゴリズムは何ですか? このアルゴリズムには確立された名前がありますか? NP困難ですか？もしそうなら、最適ではないが多項式の解はありますか?

編集:私が思い付くことができる最善の解決策は次のとおりです:文字列の初期セットで最長の共通部分文字列を見つけます。(substring_length - 1) * total_occurrences_of_it_in_the_set - substring_lengthその置換によって保存された文字/参照の数を考慮して、その部分文字列のスコアを とします。次に、すべての小さな部分文字列 (長さ 2 まで) を見つけて、同じ方法でスコアを計算します。この方法で見つかったすべての部分文字列の中で、最大のスコアを持つ部分文字列が勝ち、レキシコンに入ります。次に、文字列の最初のセットで部分文字列がそれへの参照に置き換えられ、文字列のセットに単一の文字とレキシコン参照のみが含まれるまでプロセスが繰り返されます。その後、残りのすべての単一文字をレキシコンに導入し、それらをセット内の参照に置き換えます。スコアリングの説明は次のとおりです。substring_length代わりに参照を追加し (したがって)、部分文字列を格納するために文字が-1必要です(したがって)。substring_length-substring_length

あなたが考えることができるより良いアプローチはありますか？

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

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

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

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

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

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

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

私はBinPack問題の特別な変形を使用します。私はナイーブなアルゴリズムatmを使用しているので、初期の調査を行うためにどのように呼び出されるかを知りたいです。または、この問題を既知のものに減らす方法を知っている人はいますか？

問題：特定の数量とサイズのアイテムIとビンBがあります。

すべてのアイテムサイズの合計は、少なくともすべてのビンの合計のサイズです。

各ビンは、完全に満たされるように、アイテムまたはアイテムの一部で満たされる必要があります。s(b,i)はbにあるiの部分のサイズであり、そうでない場合は0です。

目標は、すべてのビンを埋めるために必要なアイテムパーツの数を最小限に抑えることです。

与えられたものは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ハードですか？