Gibt es einen effizienteren Algorithmus?

Wissenschaft Mathematik
1

Aloha

Die Frage passt wohl auch gut in die Informatik, aber ich denke mal hier geht das auch! ;D

Ich habe folgendes Problem:
Ich habe eine Reihe von Zahlen in Binärdarstellung. Alle Zahlen haben gleich viele Ziffern und sind voneinander verschieden. Also zB 1001, 1100, 1010, 0001, 0011.

Ich möchte jetzt herausfinden, welche dieser Zahlen ich mit XOR verknüpfen muss, damit eine ganz bestimmt Zahl herauskommt. Meistens eine, die nur eine einzige 1 an einer vorgegebenen Stelle enthält. Also zB 1000, 0100, 0010 oder 0001. Oder gegebenenfalls soll gesagt werden, dass keine Lösung existiert.

Wenn ich beispielsweise alle oben genannten Zahlen verknüpfe erhalte ich: 1100 XOR 1010 XOR 0001 XOR 0011 = 0100

Das Ganze mit einem Gleichungssystem zu lösen ist eine dumme Idee, da das beschriebene Problem gerade bei dem Versuch ein Gleichungssystem zu lösen auftritt.
Ich komme auf keine andere Idee als alles durchzuprobieren :confused:
Gibt es eine schnellere Variante oder gehört das hier zu den NP-Problemen?

Danke für Antworten
MfG IGnow

2

hallo.

Ich komme auf keine andere Idee als alles durchzuprobieren :confused:

naja… ein erster schritt wäre das:
wenn nur eine 1 drin sein soll, brauchst du eine ungerade anzahl von zahlen, die an dieser stelle eine 1 haben.
welche zahlen dafür in frage kommen, müßte sich relativ einfach ergeben, wenn sie sortierst vorliegen.

damit reduzieren sich schon mal die möglichkeiten.
aus diesen zahlen müßte man mit der entsprechenden methodik auch auf die zahlen schließen können, die durch xor-verknüpfung ihre einsen verlieren.

gruß

michael

der jetzt leider keine zeit hat, das weiterzudenken

3

Hm… is vielleicht ein Ansatz

Aber das Problem ist, dass wenn ich nun nach der zweiten Stelle schaue dann wieder alle Zahlen, die ich vorher aussortiert hatte wieder mit einbezogen werden müssen.
Hm ich kann mir da irgendwie noch keinen konkreten Algorithmus zusammenreimen :confused:

MfG IGnow

4

Ich habe eine Reihe von Zahlen in Binärdarstellung. Alle
Zahlen haben gleich viele Ziffern und sind voneinander
verschieden. Also zB 1001, 1100, 1010, 0001, 0011.

Ich möchte jetzt herausfinden, welche dieser Zahlen ich mit
XOR verknüpfen muss, damit eine ganz bestimmt Zahl
herauskommt.

Moin,

ich denke, das Problem ist aquivalent zum Knapsack-Problem, wo eine Kombination verschieden großer Klötze gesucht wird, die ein vorgegebenes Gesamtvolumen erreicht werden soll.

Ein ineffizienter Algorithmus würde ja auch locker reichen, wenn deine „Reihe“ überschaubar ist.

Wenn die Reihe n Elemente hat, gibt es 2^n Kombinationen, weil jedes Element benutzt werden kann oder nicht, das ist für brute force schon für moderat große n erst einmal zu unhandlich.
(Weil die Operation XOR selbst-invertierend ist, macht es ja keinen Sinn, ein Element öfter als einmal zu verwenden.)
Wenn die Elemente nicht speziell ausgewählt sind, gibt es sicher mehr als eine Lösung. Reicht dir irgend eine oder soll es die kürzeste sein (also eine mit möglichst wenig Elementen) oder im Extremfall welche von den kürzesten, wenn es selbst da mehrere gibt?

Ein sinnvolles Vorgehen, das aber nur zu irgendeiner Lösung führt, ist das Aufstellen eines Baumes, ähnlich wie bei einem Schachprogramm: Fange mit der Null an, kombiniere sie mit jedem (noch nicht verwendeten) Element und bewerte die jeweiligen Ergebnisse danach, wie dicht sie am gewünschten Resultat liegen und wähle danach aus, welchen Zweig du zuerst weiter verfolgst.
Bei einer geschickten Kodierung (man benötigt nur eine binäre Zahl mit so vielen Bits, wie es Elemente gibt, zur Buchhaltung, was schon verwendet wurde), könnte das reichen…

hth, guidot

5

Hey

Danke fürs Kopf-machen über mein Problem :wink:

Also Brute-Force wird definitive zu aufwändig. Ich versuche eine Lösungsstrategie für ein Spiel auf einem quadratischen Brett zu finden. Die Anzahl der Felder ist also immer eine Quadratzahl. Es gibt also 2^(n^2) Varianten. Und ich würde es zumindest gern für 5 x 5 Felder lösen. Das bedeutet aber schon 33554432 Möglichkeiten. Mehr Felder sind noch wesentlich aufwendiger.

Mir kommt es nicht auf die kürzeste Kombination an, denn es gibt tatsächlich mehrere.
Das mit dem Baum werde ich versuchen. Im Grunde ist das aber auch nur ein geschicktes Ausprobieren, wobei man immer dem aussichtreichsten Weg weiterverfolgt. Im schlechtesten Fall endet es wieder bei 2^(n^2) Versuchen.

Das Problem ist zu beurteilen, wie weit ich am gewünschten Ergebnis dran bin. Das XOR-Verknüpfen mit der nächsten Zahl wird das mit hoher Wahrscheinlichkeit schon wieder komplett verändern.

MfG IGnow