Pytanie minimalna suma wymagana, aby xor niektórych liczb całkowitych wynosił zero


Oto pytanie dotyczące algorytmu i bitowego działania xor. Jesteśmy nam dane x1*x2*x3*....*xn=P, gdzie gwiazda (*) operacja reprezentuje działanie XOR (bitowe) i x1 do xn są dodatnimi liczbami całkowitymi. P jest także dodatnią liczbą całkowitą. Musimy znajdź min (a1 + a2 + a3 + ..... an)  takie, że ta relacja utrzymuje -> (x1+a1)*(x2+a2)*(x3+a3)*....*(xn+an)=0. "+" oznacza normalną operację dodawania.


12
2017-09-29 19:01


pochodzenie


Są xi dodatnie liczby całkowite, czy też mogą być ujemne? - IVlad
@IVlad Wszystkie liczby całkowite są dodatnie. - halkujabra
Myślę, że potrzeba więcej szczegółów. Jakie są ograniczenia ai? Czy one również muszą być pozytywne? Jak duże mogą być? - IVlad
@IVlad Wszystkie liczby całkowite są nieujemne! A więc wszystkie ai to> = 0 - halkujabra
@ user1708762 Czy udało ci się rozwiązać problem w warunkach minimalnych? - mayank


Odpowiedzi:


Przekształcenie jako problem programowania liniowego z ograniczoną liczbą całkowitą

Problem można przekształcić w następujący ograniczony problem ILP (całkowite programowanie liniowe).

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] jest po prostu k-tym bitem binarnej reprezentacji (xi + ai) tutaj (Warunki (A) i (C)). Aby uzyskać całkowite XOR zero, parzysta liczba b [k, i] musi wynosić 1 dla każdego k. Jest to reprezentowane przez warunki (B) i (D). (Zauważ, że suma lewostronna w (D) musi być równa, jeśli jest równa 2 * s [k], a s [k] jest liczbą całkowitą).

K, tj. Liczba bitów (plus jeden, faktycznie) potrzebna do reprezentacji wszystkich (xi + ai) musi być wcześniej określona. Pobranie K tak, że wszystkie xi są <2 ^ K powinno wystarczyć, tj. Ai są o jeden bit większe niż największe xi. Ale wybieranie większego K nie ma znaczenia, górne bity wyjdą po prostu jako zero. Jeśli K zostanie wybrane na małe, ILP nie będzie miało rozwiązania.

Istnienie rozwiązania

Ignorując warunek minimalności, problem można przekształcić jako

Biorąc pod uwagę x, y z z x <= y, znajdź aib takie, że (x + a) XOR (y + b) = z

Biorąc pod uwagę instancję twojego oryginalnego problemu, z N> = 2. Niech x = x1, y = x2, z = (x3 XOR x4 XOR ... xn). Jeśli znajdziesz odpowiednie aib, ustaw a1 = a, a2 = b, a3 = ... = an = 0, aby uzyskać rozwiązanie pierwotnego problemu.

Uproszczony problem został rozwiązany (ponownie ignorowanie minimalność) wg

  1. Jeśli (y XOR z)> = x to a: = ((y XOR z) - x), b: = 0 jest rozwiązaniem (*)
  2. Jeśli (x XOR z)> = y wtedy a: = 0, b: = ((x XOR z) - y) jest rozwiązaniem (*)
  3. W przeciwnym razie wybierz a (X + a) XOR z> = y. Taka zawsze istnieje, możesz na przykład pozwolić: = 2 ^ k z 2 ^ k> max (x, y, z). Ustawienie b: = ((x + a) XOR z) - y) daje rozwiązanie (*)

(*) Aby zobaczyć, że naprawdę są to rozwiązania, wystarczy zastosować nieco algebry. Na przykład w przypadku (1) po podstawieniu a i b otrzymasz: (x + (y XOR z) -x) XOR (y + 0). Który jest identyczny do: (y XOR z) XOR y, a tym samym do: z. co było do okazania. Przypadek (2) działa podobnie. W przypadku (3) otrzymasz: (x + a) XOR (y + ((x + a) XOR z) -y) = (x + a) XOR ((x + a) XOR z) = z.

Pokazuje to, że dla N> = 2 rozwiązanie zawsze istnieje.

Niezależnie od tego, czy te rozwiązania są minimalne, nie wiem. W przypadku (3), to oczywiście zależy od wyboru a, więc przynajmniej musiałbyś wybrać optymalny wybór dla a. Możliwe, że pierwotny problem pozwala na mniejsze rozwiązania niż uproszczony problem. Anway, może to przekształcenie pomaga komuś w znalezieniu kompletnego rozwiązania.

BTW, fakt, że pierwotne problemy zasadniczo pozostawiają całkowitą swobodę, jak "rozłożyć" wartości korekty ai na xi, sprawia, że ​​zastanawiam się, czy to nie jest odpowiednik jakiegoś problemu z plecakiem. Jeśli tak, znalezienie minimalnego rozwiązania może być bardzo trudne.

Obserwacje dotyczące minimalności

Weź następujący problem

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

W wersji binarnej

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

Pozostałość dla a1 = a2 = a3 = 0 to 001b XOR 011b XOR 110b = 100b. Oczywistym rozwiązaniem jest więc a1 = 4, a2 = 0, a3 = 0. Lub alternatywnie a1 = 0, a2 = 4, a3 = 0. To rozwiązanie jest nie minimalna - poniższe rozwiązanie jest mniejsze

a1=1, a2=1, a3=0

Jest również minimalny, ponieważ wszystkie mniejsze rozwiązania mogą mieć tylko jedną niezerową ai, a wszystkie terminy (2 XOR 3 XOR 6), (1 XOR 4 XOR 6), (1 XOR 3 XOR 7) są niezerowe.

Pokazuje to, że żaden algorytm gree, który działa od dołu (to jest od najniższego bitu) w górę, może działać, ponieważ taki algorytm pomijałby pierwsze dwa bity, ponieważ ich początkowa pozostałość wynosi zero.

Pokazuje także, że nie można wybrać określonego niezerowego bitu k z pozostałości i spróbuj ją wyzerować, dodając 2 ^ k do jeden z Xi. Czasami musisz dodać go do wielu xi, aby znaleźć minimalne rozwiązanie.

To popycha mnie nieco dalej w przekonanie, że znalezienie minimalnego rozwiązania jest stosunkowo trudnym problemem.


4
2017-09-30 10:47



Wszystkie liczby całkowite są nieujemne! A więc wszystkie ai to> = 0 - halkujabra
@ user1708762 tak, pomyślałem. Moja odpowiedź produkuje tylko ai> = 0. W przeciwnym razie łatwo zauważyć, że rozwiązanie zawsze istnieje, wystarczy ustawić ai = -xi. - fgp


Nawiązując do mojego komentarza - z jeszcze nie udzielonym pytaniem:

  1. negatywny ai wydaje się konieczny: dla przypadku N = 1, a1 = -x1 jest rozwiązaniem problemu. Zakładam zatem, że ujemne ai są również dopuszczalne w ogólnym przypadku.

  2. Wówczas dla N = 2 w ogóle nie ma rozwiązania ("min"), poza tym, że istnieje ograniczenie na to, jakie liczby (ujemne) mogą być reprezentowane w komputerze:

Dla N = 2 zestaw: a1 = x2 + K i a2 = x1 + K. Daje to:

(x1 + x2 + K) XOR (x2 + x1 + K) = 0, niezależnie od K

Suma (a1 + a2) = (x1 + x2 + 2 * K)

Nie ma minimalnego rozwiązania: możemy sprawić, by K było jeszcze bardziej negatywne.

Podobnie dla N> 2: Dla N parzystego, twórz parami "rozwiązania" jak dla N = 2 (z dowolnymi K); dla N nieparzystego, pojedynczego wyjścia - traktuj to jak dla N = 1 - a pozostałe N-1 są traktowane jak dla parzystego N.

We wszystkich przypadkach konstruujesz ZERO XOR ZERO XOR ZERO ... = ZERO, gdzie ZERO jest zawsze parą typu (am = xm + 1 + K; am + 1 = xm + K), z wyjątkiem sytuacji, gdy N jest nieparzyste, gdzie masz jeszcze jeden czynnik, tj. typ {am = -xm) . Z wyjątkiem N = 1, rozwiązania mogą stać się tak duże, jak chcesz.


1
2017-09-30 07:07



Hm, więc nawet dla N, tam jest rozwiązanie - fgp
W pewnym sensie, masz rację oczywiście (dotyczy to również nieparzystej N> 2, dostosowujesz K's, aby wypchnąć ujemną sumę do limitu, który jest reprezentowalny), ale zakładam, że to nie jest typ rozwiązania pytający szukał ... - Bert te Velde
Hm, więc nawet dla N, rozwiązanie zawsze istnieje, nawet jeśli a [i] muszą być pozytywne. Pytanie staje się zatem (nawet tylko N!), Czy [i] = x [1] + ... + x [i-1] + x [i] + ... + x [n] jest minimalnym rozwiązaniem . Dla N = 1 zgadzam się, że nie ma rozwiązania z a1> = 0, chyba że dopuszczasz przepełnienie. Nie jestem jednak przekonany, że to samo dotyczy N> 1, N nieparzyste. Kto powiedział, że nie możesz znaleźć dziwny liczba liczb całkowitych yi z yi> = xi i y1 * ... * yn = 0? - fgp
Właśnie zdałem sobie sprawę, że [i] = x [1] + ... + x [i-1] + x [i] + ... + x [n] to zdecydowanie nie minimalne rozwiązanie dla nieparzystych N. Dokonywanie dwóch sąsiednich pary (x [i] + a [i]) znoszą się nawzajem, tj. [i] = {x [i-1], jeśli i jest nieparzysty, x [i + 1], jeśli i jest równy}, generalnie produkuje mniejsze rozwiązanie. Nawet dla N, x0 + ... + xn jest więc wiązaniem dla a0 + ... + an. - fgp
Dla N nawet, narzucając wymóg pozytywnego ai, dostajesz niższe minimum niż twój ogólny {a (i) = suma (wszystkie x (j)) - x (i)}, parując, wzdłuż linii w mojej odpowiedzi. Pierwszym strzałem byłoby posortowanie zestawu x (i), a następnie parowania {a (i) = (x (j) - (x (i)); a (j) = 0}. Wynik jest sumą różnice par (x (j) - (x (i)) Btw, uważam, że powinniśmy również poczekać na odpowiedź od osoby, która zadała pytanie, aby wyjaśnić, co jest wymagane / dozwolone. - Bert te Velde


Być może pierwsze wejście do minimum - N> 1, wszystko (i) pozytywne - jest wzdłuż następujących linii. Pozwól mi najpierw podać jakąś terminologię.

Inicjalizuj y (i) = x (i); y (i) oznacza (x (i) + a (i)), więc zainicjujemy w rzeczywistości a (i) = 0 (dla i = 1..N). Podobnie, zdefiniuj Q = y (1) ^ y (2) ^ ... ^ y (N) (^ oznacza XOR); początkowo Q = P.

Dostosujemy y (i), aby uzyskać Q zero, zawsze zachowując y (i)> = x (i) - tj .: a (i)> = 0.

Rozważmy dla każdego numeru (x, y, a, P, Q) jego binarne (bitowe) rozszerzenie, numerując bity o m = 0,1,2, ..: bit m reprezentuje część wartości 2 ** m w numer.

Zauważ, że bit jest niezerowy w Q wtedy i tylko wtedy, gdy liczba y (i), które mają ten sam bit niezerowy jest nieparzysta.

Postępować w następujący sposób. Zeskanuj bity naruszające (wartość 1) w Q, z góry na dół, tzn .: zaczynając od najwyższego ("aktualnie pozostającego") bitu, który wynosi 1. Niech to będzie bit #m.

Mamy dwa przypadki:

Przypadek A. Istnieje co najmniej jeden y (i), który ma zero w bitach m. Zdefiniuj C jako zbiór wszystkich takich y (i).

Wybieramy jedną z nich (patrz poniżej) i ustawiamy jej m-bit na 1, czyli zmieniając

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

Aby określić nasz wybór y (i) w kolekcji C, staramy się częściowo zrekompensować WZROK (2 ** m) OSTATECZNOŚCIą tak dużą, jak to możliwe:

Iteruj po bitach m-1, m-2, ... aż otrzymamy bit #n gdzie (1.) Q ma 1 (tj. Inny bit, który chcemy usunąć) i (2) najmniej jeden z y (i) w C ma także 1.

Jeśli to się uda, wtedy (1.) ustaw:

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

(2.) zredukować kolekcję C, aby zachować tylko te y (i), które mają bit #n niezerowy; i (3.) powtórzyć proces, skanując bity jeszcze bardziej w dół.

Jak tylko nie będziemy mogli dalej działać, wybierz arbitralnie jedną z pozostałych y (i) z C i zwiększ ją przez INCREMENT. Update Q. Usuwa bity {m, n, ...} z Q przez dodanie

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

do wybranego y (i), ustawia jego bit #m na 1 (wynosił 0), a jego bity n, ... na 0 (były to 1).

Przypadek B. Żadne z y (i) nie ma zera w bitach #m. W tym przypadku:

Iteracja bitów k = m + 1, m + 2, ... aż przynajmniej DWÓCH y (i) będzie miało zero w tym bicie. Zdefiniuj C1 jako kolekcję wszystkich takich y (i) i zrób kopię do kolekcji C2. Określ także

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

Przetwórz {C1, INCREMENT1}, tak jak w przypadku A.

Usuń ostatni pick y (i) z kolekcji C2. Następnie wykonaj proces {C2, INCREMENT2}.

Powtórz to wszystko, aż wszystkie bity w Q będą zerowe.

Nie próbowałem udowodnić, że ta procedura daje prawdziwe minimum, ale uważam, że to podejście może być dobrym punktem wyjścia do rozważenia (struktury) takiego dowodu.


1
2017-09-30 15:34