Gleichungssystem mit binären Variablen

Neue Frage »

08.11.2015, 14:07	avrrobot	Auf diesen Beitrag antworten »
Gleichungssystem mit binären Variablen Meine Frage: Hallo, ich habe ein Gleichungssystem von folgendem Typ, welches ich gerne (algorithmisch) lösen möchte: a0b4 + a1b3 + a2b2 + a3b1 + a4b0 = 4 a0b3 + a1b2 + a2b1 + a3b0 = 3 ..... wobei a0,a1,...,an und b0,b1,...,bn Element {0,1}. Dabei besitzt das System immer ein eindeutige Lösung. Außerdem kommt jede Kombination aus ax mit bx jeweils einmal vor. Welches Verfahren kann ich nutzen, um dies effizient zu lösen? Meine Ideen:* Da man durch Addition der Gleichungen wie in einem normalen linearen Gleichungssystem hier nichts erhält, wird man die Gleichungen multiplizieren müssen, das wird aber schnell unübersichtlich. Teilen von Gleichungen ist auch nicht wirklich praktisch.
08.11.2015, 17:57	Elvis	Auf diesen Beitrag antworten »
Wieso besitzt das System immer eine eindeutige Lösung ? Für $\begin{eqnarray} n=0 \end{eqnarray}$ haben wir $\begin{eqnarray} a_0b_0=0 \end{eqnarray}$ mit den drei Lösungen $\begin{eqnarray} (a_0=b_0=0), (a_0=0,b_0=1),(a_0=1,b_0=0) \end{eqnarray}$ .
08.11.2015, 19:39	avrrobot	Auf diesen Beitrag antworten »
Für den Fall n = 0 stimmt das, aber ich habe einen Anwendungsfall, der eine Eindeutige Lösung garantiert. Außerdem ist n immer größer als 0, mehr so wie 100 oder so (deshalb brauche ich ja auch einen Algorithmus, da ich das nicht von Hand lösen kann und will).
08.11.2015, 20:02	Elvis	Auf diesen Beitrag antworten »
Das glaube ich nicht. Wenn das schon für n=0 falsch ist, kann es nicht für n>0 richtig sein. Eventuell habe ich dein Gleichungssystem mit "..." falsch verstanden, dann musst Du erst einmal sauber definieren, wie es aussieht.
08.11.2015, 20:36	avrrobot	Auf diesen Beitrag antworten »
Ok, warscheinlich habe ich mich hier schlecht ausgedrückt (in mehreren Hinsichten): -Das ganze ist in der Hinsicht nicht eindeutig, dass die Lösung bezüglich a und b symmetrisch ist. Was ich damit meine ist folgendes: Man kann a und b auch als einen Vektor betrachten, dann hat das System eine Lösung und eine andere mit a und b vertauscht. Aber das ist ja eigentlich nur eine einzige Lösung, da es keine Rolle spielt, ob a nun den einen Vektor enthält oder den anderen. -Ich sage nicht, dass diese Art von Gleichungssystem prinzipiell nur eine (oder zwei) Lösungen hat, aber ich muss es eben nur in Fällen lösen, von denen ich weiß, dass nur eine (oder eben zwei, wie man es auch betrachtet) Lösungen existiert. Das meine ich mit dem Anwendungsfall Den Rest hast du glaube ich richtig verstanden.
08.11.2015, 22:04	Elvis	Auf diesen Beitrag antworten »
Ein Algorithmus ist nicht nötig, die beiden Lösungen findet man leicht durch Lösen der Gleichungen für n=0,1,2,...
Anzeige

09.11.2015, 07:13	avrrobot	Auf diesen Beitrag antworten »
Ok, ich muss zugeben, dass ich nicht genau weiß, was du meinst. Deshalb hier mal ein einfaches Beispiel (ich hoffe ich habe es richtig zusammengestellt): $\begin{eqnarray} a_0b_0 = 1 \end{eqnarray}$ $\begin{eqnarray} a_0b_1 + a_1b_0 = 2 \end{eqnarray}$ $\begin{eqnarray} a_0b_2 + a_1b_1 + a_2b_0 = 2 \end{eqnarray}$ $\begin{eqnarray} a_0b_3 + a_1b_2 + a_2b_1 + a_3b_0 = 2 \end{eqnarray}$ $\begin{eqnarray} a_0b_4 + a_1b_3 + a_2b_2 + a_3b_1 + a_4b_0 = 3 \end{eqnarray}$ $\begin{eqnarray} a_1b_4 + a_2b_3 + a_3b_2 + a_4b_1 = 3 \end{eqnarray}$ $\begin{eqnarray} a_2b_4 + a_3b_3 + a_4b_2 = 1 \end{eqnarray}$ $\begin{eqnarray} a_3b_4 + a_4b_3 = 1 \end{eqnarray}$ $\begin{eqnarray} a_4b_4 = 1 \end{eqnarray}$ Was wäre dann also die Lösung (natürlich kann man das hier noch relativ leicht von Hand lösen mit etwas nachdenken, aber ich brauche eine generelle Lösung).
09.11.2015, 12:56	Elvis	Auf diesen Beitrag antworten »
Wenn ich eine Lösung Deines Problems finde, veränderst Du das Problem. Jetzt hast Du auf der linken Seite mehr und weniger Summanden und die rechte Seite wächst nicht mehr streng monoton. Wenn Du in der Lage bist, das generelle Problem zu formulieren, hast Du wesentlich bessere Aussichten, die generelle Lösung zu finden.
09.11.2015, 16:08	avrrobot	Auf diesen Beitrag antworten »
Ich bin mir zwar nicht sicher, wie man zu dieser Interpretation kommen kann, aber ich nahm an, dass die exakte Form des Problemes nicht nötig sei, da es unter Umständen eine generelle Lösung für diese Art gibt (jeweils zwei Variablen multiplizieren und das ganze dann zusammenaddieren). Da es aber anscheinend nötig ist, hier die genaue Form meines Problemes für beliebige Größen: Es werden immer $\begin{eqnarray} 2n-1 \end{eqnarray}$ Gleichungen betrachtet. Wie in dem Beispiel gezeigt werden die Gleichungen jeweils immer um ein Variablenpaar länger bis zur mittleren Glechung, dann wieder kürzer. Zur Generalisierung verwende ich erst einmal eine Darstellung, bei der die Gleichungen nur länger werden: $\begin{eqnarray} G_n : s_n = \sum\limits_{p = 0}^n a_pb_{n-p} \end{eqnarray}$ Wobei die Lösung aus $\begin{eqnarray} a_0 \end{eqnarray}$ bis $\begin{eqnarray} a_{n-1} \end{eqnarray}$ und b äquivalent besteht. Alle a und b mit einem höheren Index werden als 0 definiert, daher fallen diese Faktoren dann weg und die Gleichungen werden ab der Mitte kürzer. $\begin{eqnarray} s_n \end{eqnarray*}$ ist dabei immer der Wert der Einzelnen Gleichungen, diese sind immer bekannt, es kann aber keine Aussage getroffen werden, außer dass der Wert der ersten und der letzten Gleichung immer 1 ist. (Es kann sein, dass hier drin irgendwo eine kleine inkonsistenz mit n existiert, aber ich denke man versteht es zusammen mit dem Beispiel)
11.11.2015, 08:52	Elvis	Auf diesen Beitrag antworten »
Wenn Du das Problem nicht allgemein aufschreiben kannst oder willst, dann kannst Du auch keine allgemeine Lösung und keinen Algorithmus dafür finden. Jedes solche Problem ist leicht lösbar, falls Deine "Zweideutigkeitsbedingung" (bzw. "symmetrische Eindeutigkeitsbedingung") gilt. Als Programm zur Lösung kannst Du jedes Optimiersystem benutzen, das binäre Probleme lösen kann.

Neue Frage »

Antworten »

Gleichungssystem mit binären Variablen

Verwandte Themen