Optimierung der Reihenfolge eines binären Nachrichtenarrays
Gegeben ist eine Liste von binären Strings, die eine Nachricht bilden, jedoch in zufälliger Reihenfolge vorliegen. Sie ist durch eine gegebene Permutation \(w\) definiert. Unser Ziel ist es, ein Optimierungsmodell zu formulieren, das die Reihenfolge wiederherstellt.
Mathematische Modellierung
Sei \( n \) die Anzahl der Wörter. Definiere binäre Entscheidungsvariablen:
\[
x_{ij} =
\begin{cases}
1, & \text{wenn das } j\text{-te Wort an Position } i \text{ steht,} \\
0, & \text{sonst.}
\end{cases}
\]
Nebenbedingungen
Jede Position wird mit genau einem Wort besetzt:
\[
\sum_{j=0}^{n-1} x_{ij} = 1, \quad \forall i \in \{0, \dots, n-1\}
\]
Jedes Wort kann nur an einer Position stehen:
\[
\sum_{i=0}^{n-1} x_{ij} = 1, \quad \forall j \in \{0, \dots, n-1\}
\]
Zielfunktion
Um die Reihenfolge optimal zu rekonstruieren, minimieren wir die absolute Abweichung:
\[
\min \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} | w_j – i | \cdot x_{ij}
\]
Lösung mit OR-Tools
Die Lösung wird mithilfe des Constraint-Programming-Ansatzes in OR-Tools berechnet. Nach der Bestimmung der richtigen Reihenfolge werden die binären Strings in Klartext umgewandelt.
from typing import List
from ortools.sat.python import cp_model
INPUT = [
'01110110011010010110010101101100', '01110110011010010110010101101100', '010101110110100101110010',
'011101010110111001100100', '01101000011000010111001101110100',
'01000101011011100110011101100001011001110110010101101101011001010110111001110100',
'011100110110111101110111011011110110100001101100', '010101110110010101100111', '011101010110111001110011',
'010001000110010101101001011011100110010101110010', '010001000110010101101001011011100110010101101101',
'01010011011001010110001001100001011100110111010001101001011000010110111000101100', '0100010001110101',
'01101101011010010111010001100111011001010110010001100001011000110110100001110100', '011000010110110001110011',
'010001000110100101110010', '0111011111111100011011100111001101100011011010000110010101101110',
'01000101011100100110011001101111011011000110011100100001', '011101010110111001100100',
'01110000011001010111001001110011111101100110111001101100011010010110001101101000', '011001101111110001110010',
'01101101011010010111010001100111011001010111001101110100011000010110110001110100011001010111010000101110',
'010011000110100101100101011000100110010101110010',
'0111011101100101011010010111010001100101011100100110010101101110',
'0110100101101110', '011000100110010101101001',
'011000100110010101110010011101010110011001101100011010010110001101101000',
'011101110110010101101001011101000110010101110010011010000110100101101110',
'011001000110000101101110011010110110010101101110',
'01100001011101010110001101101000', '01011010011001010110100101110100', '011000010111010101100110',
'01000100011001010110100101101110', '010001000110100101110010',
'01100010011001010111011101100101011001110111010000101100'
]
WEIGHTS = [9, 33, 14, 12, 3, 19, 27, 26, 8, 5, 24, 1, 2, 11, 29, 16, 21, 34, 20, 31, 17, 13, 0, 25, 4, 7, 28, 32, 15, 30, 6, 23, 18, 22, 10]
def binary_to_text(binary_string: str) -> str:
chars = [binary_string[i:i + 8] for i in range(0, len(binary_string), 8)]
return "".join(chr(int(c, 2)) for c in chars)
def solve_message(input_: List[str], weights: List[int]):
n = len(weights)
model = cp_model.CpModel()
x = [[model.NewBoolVar(f'x_{i}_{j}') for j in range(n)] for i in range(n)]
for i in range(n):
model.Add(sum(x[i][j] for j in range(n)) == 1)
for j in range(n):
model.Add(sum(x[i][j] for i in range(n)) == 1)
model.Minimize(sum(sum(abs(weights[j] - i) * x[i][j] for j in range(n)) for i in range(n)))
solver = cp_model.CpSolver()
print('Suche nach einer optimalen Lösung ...')
status = solver.Solve(model)
if status in (cp_model.FEASIBLE, cp_model.OPTIMAL):
if status == cp_model.OPTIMAL:
print('Optimale Lösung gefunden!')
sorted_binaries = [input_[next(j for j in range(n) if solver.Value(x[i][j]))] for i in range(n)]
decoded_text = " ".join(binary_to_text(b) for b in sorted_binaries)
print(decoded_text)
else:
print("Keine Lösung gefunden.")
if __name__ == '__main__':
solve_message(INPUT, WEIGHTS)
