algorithm - 一部の整数の xor をゼロにするために必要な最小合計

Question

これは、アルゴリズムとビットごとの xor 操作を扱う質問です。ここx1*x2*x3*....*xn=Pで、star( *) 操作は XOR(ビット単位) 操作を表し、 x1 から xn は正の整数です。P も正の整数です。この関係が成立するようなmin(a1+a2+a3+.....an) を見つける必要があります --> . 「+」は通常の加算操作を表します。(x1+a1)*(x2+a2)*(x3+a3)*....*(xn+an)=0

Answer 1

有界整数線形計画問題としての再表現

この問題は、次の有界 ILP (整数線形計画法) 問題として言い換えることができます。

Let x1,...,xN be as in the original problem, i.e. the goal is to minimize(a1+...+aN)
under the conditions (x1+a1) XOR ... (xN+aN) = 0, a1,...,aN >= 0.

The following is than an equivalent bounded ILP:
Find b[k,i] (0 <= k <= K, 1 <= i <= N) and s[k] (0 <= k <= K) such that
  (A) b[k,i] in {0, 1} for all i=1..n, k=0..K,
  (B) s[k] is an integer >= 0 for all k=0..K,
  (C) sum(b[k,i]*2^k, k=0..K) >= x[i] for all i = 1..N,
  (D) sum(b[k,i], i=1..N) = 2*s[k] for all k = 0..K
and minimize
  sum(b[k,i]*2^k, i=1..n, k=0..K).

From a solution of the bounded ILP the ai's are obtained by
  a[i] = sum(b[k,i]*2^k, k=0..(K-1)) - x[i]

ここで、b[k,i] は単に (xi+ai) のバイナリ表現の k 番目のビットです (条件 (A) および (C))。全体の XOR をゼロにするには、すべての k に対して b[k,i] の偶数が 1 でなければなりません。これは条件(B)と(D)で表されます。((D) の左辺の合計は、2*s[k] に等しく、s[k] が整数の場合、偶数でなければならないことに注意してください)。

Ｋ、すなわち、すべての（ｘｉ＋ａｉ）を表すのに必要なビット数（実際には＋１）は、事前に決定されなければならない。すべての xi が < 2^K となるように K を選択すれば十分です。つまり、ai は最大の xi よりも 1 ビット大きくなります。しかし、より大きな K を選択しても問題はありません。上位ビットは単純にゼロになります。K を小さく選択すると、ILP には解がありません。

解決策の存在

最小条件を無視すると、問題は次のように言い換えることができます。

x <= y の x、yz が与えられた場合、(x+a) XOR (y+b) = z となる a と b を見つけます。

元の問題のインスタンスが N >= 2 の場合、x=x1、y=x2、z=(x3 XOR x4 XOR ... xn) とします。適切な a と b が見つかったら、a1=a、a2=b、a3=...=an=0 と設定して、元の問題の解を取得します。

単純化された問題は次のように解決されます (ここでも最小性は無視されます)。

1. If (y XOR z) >= x then a: = ((y XOR z) - x), b := 0 は解 (*)
2. (x XOR z) >= y の場合、a := 0、b := ((x XOR z) - y) は解 (*)
3. それ以外の場合は、(x+a) XOR z >= y となる a を選択します。このような a は常に存在します。たとえば、let a := 2^k with 2^k > max(x,y,z) を指定できます。b := ((x+a) XOR z) - y) を設定すると、解が得られます (*)

(*) これらが実際に解であることを確認するには、少し代数を適用する必要があります。たとえば、(1) の場合、a と b を代入すると、(x+(y XOR z)-x) XOR (y+0) が得られます。これは (y XOR z) XOR y と同一であり、したがって以下と同一です: zqed ケース (2) も同様に機能します。(3) の場合: (x+a) XOR (y+((x+a) XOR z)-y) = (x+a) XOR ((x+a) XOR z) = z.

これは、N >= 2 の場合、常に解が存在することを示しています。

それらの解決策が最小限であるかどうかはわかりません。(3) の場合、明らかに a の選択に依存するため、少なくとも a の最適な選択を把握する必要があります。また、単純化された問題よりも元の問題の方が小さな解が可能である可能性もあります。とにかく、この言い直しは誰かが完全な解決策を理解するのに役立つかもしれません.

ところで、元の問題が基本的に、修正値 ai を xi に「広げる」方法を完全に自由にできるという事実は、これがある種のナップザック問題と同等ではないかどうか疑問に思います。そうである場合、最小解を見つけることは NP 困難である可能性があります。

最小性に関する観察

次の問題を解いてください

(1+a1) XOR (3+a2) XOR (6+a3) = 0

バイナリでは、つまり

(001b+a1) XOR (011b+a2) XOR (110b+a3) = 0

a1=a2=a3=0 の剰余は 001b XOR 011b XOR 110b = 100b です。したがって、明らかな解は a1=4,a2=0,a3=0 です。または、a1=0、a2=4、a3=0。ただし、このソリューションは最小ではありません-次のソリューションはより小さくなります

a1=1, a2=1, a3=0

すべての小さなソリューションはゼロ以外の ai を 1 つしか持てず、すべての項 (2 XOR 3 XOR 6)、(1 XOR 4 XOR 6)、(1 XOR 3 XOR 7) は非ゼロであるため、これも最小限です。

これは、最初は剰余がゼロであるため、最初の 2 ビットをスキップするため、最下位 (最下位ビット) から上に向かって動作する gree アルゴリズムは機能しないことを示しています。

また、剰余から特定のゼロ以外のビットkを選択し、xi の1 つに2^kを追加してゼロにしようとすることはできないことも示しています。最小の解を見つけるために、複数の xi に追加する必要がある場合があります。

これは、最小の解決策を見つけることは比較的難しい問題であると信じる方向に私を少し押し進めます.

Answer 2

私のコメントを参照してください-まだ答えられていない質問で：

1. 負のaiが必要なようです。N=1の場合、a1=-x1が問題の解決策です。したがって、一般的な場合でも負のaiが許容されると思います。

2. 次に、N = 2の場合、コンピューターで表現できる（負の）数に制限があるという事実を除けば、解決策（ "min"）はまったくありません。

N = 2セットの場合：a1 = x2+Kおよびa2=x1+K。これにより、次のようになります。

（x1 + x2 + K）XOR（x2 + x1 + K）= 0、Kに関係なく

合計（a1 + a2）=（x1 + x2 + 2 * K）

最小の解決策はありません。Kをこれまで以上に負にすることができます。

同様に、N> 2の場合：Nが偶数の場合、N = 2の場合と同様にペアワイズの「解」を作成します（任意のKを使用）。Nが奇数の場合、単一の1つがN = 1の場合と同様に扱われ、残りのN-1は偶数のNの場合と同様に処理されます。

すべての場合で、ZERO XOR ZERO XOR ZERO ... = ZEROを作成します。ここで、ZEROは常にタイプのペア（am = xm + 1 + K; am + 1 = xm + K）です。ただし、Nが奇数の場合を除きます。もう1つの要素、つまりタイプ{am = -xm）があります。N = 1を除いて、解は好きなだけ大きな負の値になる可能性があります。

Answer 3

おそらく、最小値への最初の侵入 - N>1、すべての a(i) が正 - は、次の行に沿っています。最初にいくつかの用語を述べさせてください。

y(i) = x(i) を初期化します。y(i) は (x(i)+a(i)) を表すため、実際には a(i)=0 (i=1..N の場合) を初期化します。同様に、Q = y(1)^y(2)^...^y(N) (^ は XOR を表します); を定義します。最初は Q=P です。

y(i) を調整して Q をゼロにし、常に y(i)>=x(i) を維持します。つまり、a(i)>=0 です。

各数値 (x,y,a,P,Q) について、ビットを m=0,1,2,.. で番号付けするバイナリ (ビット) 展開を検討します。ビット m は、2**m の値部分を表します。数字。

0 以外の同じビットを持つ y(i) の数が奇数である場合にのみ、Q のビットが 0 ではないことに注意してください。

次の手順に従ってください。Q で問題のあるビット (値 1) をトップダウンでスキャンします。つまり、1 である最上位 (「現在残っている」) ビットから始めます。これをビット #m とします。

2 つのケースがあります。

ケース A. ビット m がゼロの y(i) が少なくとも 1 つある。そのようなすべての y(i) のコレクションとして C を定義します。

それらの 1 つを選択し (以下を参照)、その m ビットを 1 に設定します。

 y(i) = y(i)+(2**m). For the moment, just define INCREMENT=(2**m).

コレクション C の選択 y(i) を決定するために、できるだけ大きな DECREMENT によって INCREMENT (2**m) を部分的に補正しようとします。

(1.) Q が 1 (つまり、削除したい別の問題のあるビット) を持つビット #n になるまで、ビット m-1、m-2、... を繰り返します。 C の y(i) の少なくとも 1 つにも 1 があります。

これが成功した場合、(1.) 以下を設定します。

INCREMENT = INCREMENT - 2**n (note that this remains positive);

(2.) コレクション C を縮小して、ゼロ以外のビット #n を持つ y(i) のみを保持します。(3.) このプロセスを繰り返し、ビットをさらに下にスキャンします。

これ以上先に進めなくなったらすぐに、残りの y(i) の 1 つを C から任意に選び、INCREMENT だけ増やします。Q を更新します。これにより、Q からビット {m,n,...} が削除されます。

 (2**m - 2**n - ...)

選択された y(i) に、そのビット #m を 1 (0) に設定し、そのビット n,... を 0 (これらは 1) に設定します。

ケース B. y(i) のいずれもビット #m にゼロがありません。この場合：

少なくとも 2 つの y(i) のビットがゼロになるまで、ビット k=m+1、m+2、... を繰り返します。そのようなすべての y(i) のコレクションとして C1 を定義し、コレクション C2 にコピーを作成します。また定義する

INCREMENT1 as (2**k - 2**m) and set INCREMENT2 = 2**k.

ケース A で行ったように {C1, INCREMENT1} を処理します。

コレクション C2 から最後のピック y(i) を削除します。次に {C2, INCREMENT2} を同様に処理します。

Q のすべてのビットがゼロになるまで、これをすべて繰り返します。

この手順が真の最小値をもたらすことを証明しようとはしていませんが、このアプローチはそのような証明 (の構造) について考えるための良い出発点になると信じています.