1

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

4

2 に答える 2

2

4 つの演算子があるため、n 項のセットに対して 4^(n-1) の可能な値があります。各パスが一連の演算子値を表し、終点が計算の結果である検索空間のグラフを作成できます。

それらすべての終点のうち、正しい答えを与えるものだけが正しい終点で終了します。

ただし、終点から開始すると、逆方向にトラバースできることに注意してください。有効な演算子のセットがある場合にのみ、最初の値で終了します。

したがって、両端からトラバースすると、2 つの計算が途中で一致します。これは、各方向から 4^(n/2) = 2^n のはるかに小さい空間です。2 つの回答セットを一致させるには、途中で取得したリストを並べ替える必要がありますが、重複したパスがたどられないようにするために、すべてのステップでこれを行うことをお勧めします。この時点で、迷路のトラバーサルのように見えます。

既知の NP 完全問題の 1 つはブール充足可能性の問題です。これは、「与えられたブール式の変数を、式が TRUE と評価されるような方法で割り当てることができるかどうかを判断する問題」です。探索空間はブール充足可能性問題の探索空間よりも明らかに大きいため、解は式が充足可能であると判断する (したがって、少なくとも充足可能性を解くのと同じくらい難しい) ため、問題は次のようにすべきだと思います。 NP完全であること。

迷路の意味では、値がゼロから発散する部分的な解は正しい解である可能性が低く、パラメータの最初のスイープが与えられると、サイズ (つまり、すべての乗算) にどのような制限があるかが明確になるはずです。ブール問題の場合。

編集：冒頭で述べたツリーを明確にするため。私たちのリストが

 1 ? 2 ? 5 = X

次に、グラフは次のようになります。

 r1 -->  r2  ---> r3 (X)

 1  +2    3  +5    8
             -5   -2
             *5   15
             /5    0

    -2   -1  +5    4
             -5   -6
             *5   -5
             /5    0

    *2    2  +5    7
             -5   -3
             *5   10
             /5    0

    /2    0  +5    5
             -5   -5
             *5    0
             /5    0

ご覧のとおり、X が -5 の場合、1 -2 *5 または 1 /2 -5 になる可能性があります。-5 から逆方向に作業する:

-5 +5    0
   -5  -10
   *5  -25
   /5   -1

したがって、それぞれの端からステップした場合、中央の列になり、唯一の共通値は -1 と 0 になり、16 回の計算が一方向のみに進むのではなく、8 回の計算で 2 つのパスが生成されます。

私が見逃していたこれが提起するポイントは、整数除算は1:1マッピングではないため、後退することはあいまいです。-4/5 -> 0, -3/5 -> 0 など 4/5 -> 0 まで。同じ値 2 にマップします。これはかなりのハードルです。分割された数のサイズだけ後ろにステップするとき、可能なノードの数を上げるので、5 の場合、4 ではなく 3+5 = 8 の可能な状態があります。

于 2012-11-16T17:52:19.657 に答える
0

これは再帰的な解決策の試みです（単純なバージョンの場合）：

Gen {'x'} = {'x'}
Gen {'x', 'y'} = {'x + y', 'x - y', 'y - x', 'x / y', 'y / x', 'x % y', 'y % x'}
S0 = {a[0]}
Gen S(i + 1) = {j ∈ S(i) | Gen {j, a[i + 1]}}

最終的な答えは次のようになります。∃ j ∈ S(n). x = [[ j ]]

つまり、考えられるすべての値を(式として) 段階的に構築し、最終的にそれらすべてを評価して、そのうちの 1 つが生成できるかどうかを確認しますx(評価は段階的に行うこともできます)。

ただし、ここではa、式を作成するときに からの値が線形に使用されると想定しています。あなたの問題には当てはまらないことに気づきました...

于 2012-11-16T17:59:19.887 に答える