Frage Wie implementiere ich einen Superoptimierer?


[Bezüglich https://codegolf.stackexchange.com/questions/12664/implement-superoptimizer-for-addition vom 27. September 2013]

Ich bin daran interessiert, wie man schreibt Superoptimierer. Insbesondere, um kleine logische Formeln für Bitmengen zu finden. Dies wurde zuvor als eine Herausforderung für Codegolf festgelegt, aber es scheint viel schwieriger als man sich vorstellen kann.

Ich möchte Code schreiben, der die kleinstmögliche logische Aussageformel findet, um zu prüfen, ob die Summe von binären 0/1-Variablen gleich einem Wert x ist. Nennen wir die Variablen x1, x2, x3, x4 usw. Im einfachsten Fall sollte die logische Formel der Summe entsprechen. Das heißt, die logische Formel sollte genau dann wahr sein, wenn die Summe gleich x ist.

Hier ist eine naive Art, das zu tun. Sagen Sie y = 15 und x = 5. Wählen Sie alle 3003 verschiedenen Möglichkeiten zur Auswahl von 5 Variablen und für jede machen Sie eine neue Klausel mit dem UND dieser Variablen UND die UND der Negation der verbleibenden Variablen. Sie erhalten 3003 Klauseln mit einer Länge von jeweils genau 15 für Gesamtkosten von 45054.

Wenn Sie jedoch neue Variablen in Ihre Lösung einfügen dürfen, können Sie dies möglicherweise erheblich reduzieren, indem Sie allgemeine Teilformeln eliminieren. In diesem Fall besteht Ihre logische Formel aus den y-Binärvariablen x und einigen neuen Variablen. Die ganze Formel wäre genau dann erfüllbar, wenn die Summe der y-Variablen gleich x ist. Die einzigen erlaubten Betreiber sind and, or und not.

Es stellt sich heraus, dass es ein schlaue Methode zur Lösung dieses Problems, wenn x = 1, zumindest in der Theorie. Ich suche jedoch nach einer rechenintensiven Methode zur Suche nach kleinen Lösungen.

How can you make a superoptimizer for this problem?

Beispiele. Nehmen wir als Beispiel zwei Variablen, bei denen wir eine logische Formel haben wollen, die genau wahr ist, wenn sie auf 1 summiert. Eine mögliche Antwort ist:

(((not y0) and (y1)) or ((y0) and (not y1)))

Um eine neue Variable in eine Formel wie z z0 zu repräsentieren y0 and not y1 dann können wir eine neue Klausel einführen (y0 and not y1) or not z0 und ersetzen y0 and not y1 durch z0 im ganzen Rest der Formel. Natürlich ist das in diesem Beispiel sinnlos, da es den Ausdruck länger macht.


5
2017-10-08 10:43


Ursprung


Antworten:


Schreiben Sie Ihre gewünschte Summe in Binärform. Schauen Sie sich zuerst das unwichtigste Bit an, y0. Deutlich, x1 xor x2 xor ... xor xn = y0 - das ist deine erste Formel. Die endgültige Formel wird eine Konjunktion von Formeln für jedes Bit der gewünschten Summe sein.

Weißt du nun, wie ein Addierer implementiert ist? http://en.wikipedia.org/wiki/Adder_(electronics) . Lassen Sie sich davon inspirieren, gruppieren Sie Ihre Eingabe in Paare / Tripel von Bits, berechnen Sie die Übertragsbits und verwenden Sie sie, um Formeln für y1 ... yk zu erstellen. Wenn Sie weitere Hinweise benötigen, lassen Sie es mich wissen.


2
2017-10-15 20:45



Wenn ich verstehe, was Sie fragen, sollten Sie sich die allgemeinen Themen von Logikminimierung und / oder Boolesche Funktionsvereinfachung. Die Referenzen beziehen sich hauptsächlich auf allgemeine Methoden zum Eliminieren von Redundanz in booleschen Formeln, die Disjunktionen ("oder" s) von Termen sind, die Konjunktionen ("und" s) sind.

Mit der Hand wird die Standardmethode eine Karnaugh-Karte genannt. Der äquivalente Algorithmus, der auf eine Weise ausgedrückt wird, die der Computerimplementierung zugänglicher ist, ist Quine-McKlosky (auch die Methode der Primimplikanten genannt). Das Minimierungsproblem ist NP-schwer und QM löst es genau.

Daher denke ich, dass QM das ist, was man für den "Super-Optimizer", den man bauen möchte, braucht.

Aber die Kombination von NP-harter und exakter Lösung bedeutet, dass QM für große Probleme, zumindest nicht-triviale, unpraktisch ist.

Das QM-Algorithmus legt in einer Tabelle die konjunktiven Begriffe (in diesem Zusammenhang minterms genannt) an und führt Suchen nach 1-Bit-Unterschieden zwischen Begriffspaaren durch. Diese Terme können kombiniert werden und der Faktor für das abweichende Bit in weiteren Kombinationen als "egal" bezeichnet werden. Dies wird mit 2-Bit-, 4-Bit- usw. Teilmengen von Bits wiederholt. Das exponentielle Verhalten ergibt sich daraus, dass für die Kombinationen größerer Bitmengen Auswahlmöglichkeiten vorhanden sind: Wählen Sie ein anderes aus. Daher ist es im Wesentlichen ein Suchproblem.

Es gibt eine enorme Literatur über Heuristiken, um den Suchraum zu trimmen und dennoch "gute" Lösungen zu finden, die nicht unbedingt optimal sind. Ein berühmter ist Espresso. Da sich Verbesserungen des Algorithmus jedoch direkt in Dollars bei der Herstellung von Halbleitern niederschlagen, ist es durchaus möglich, dass das Beste proprietär und eng gehalten wird.


1
2017-10-16 23:38