effiziente Methoden zur Summierung

Für einige Teilmengen gibt es Möglichkeiten, die Berechnung zu beschleunigen, wenn es Ihnen nichts ausmacht, eine (möglicherweise teure) Vorberechnung durchzuführen, aber nicht für alle. Angenommen, Ihre Teilmengen sind {1,2}, {2,3}, {3,4}, {4,5}, ..., {n-1, n}, {n, 1}; dann verwendet der naive Ansatz eine arithmetische Operation pro Teilmenge, und Sie können offensichtlich nicht besser als das tun. Auf der anderen Seite, wenn Ihre Teilmengen {1}, {1,2}, {1,2,3}, {1,2,3,4}, ..., {1,2, ... sind, n} dann können Sie mit n-1 arithmetischen Ops auskommen, während der naive Ansatz viel schlechter ist.

Hier ist eine Möglichkeit, die Vorberechnung durchzuführen. Es wird nicht immer optimale Ergebnisse finden. Definieren Sie für jedes Paar von Teilmengen die Übergangskosten als min (Größe der symmetrischen Differenz, Größe von Y - 1). (Die symmetrische Differenz von X und Y ist die Menge von Dingen, die in X oder Y sind, aber nicht beides.) Die Übergangskosten sind also die Anzahl der arithmetischen Operationen, die Sie zur Berechnung der Summe der Elemente von Y berechnen müssen Xs. Fügen Sie der Liste der Teilmengen den leeren Satz hinzu und berechnen Sie einen aufspannenden Baum mit minimalem Aufwand mit dem Edmonds-Algorithmus (http://en.wikipedia.org/wiki/Edmonds%27_algorithm) oder einer der schnelleren, aber komplizierteren Varianten dieses Thema. Stellen Sie jetzt sicher, dass, wenn Ihr Spannbaum eine Kante X hat - & gt; Y Sie berechnen X vor Y. (Dies ist eine "topologische Sortierung" und kann effizient durchgeführt werden.)

Dies führt zu deutlich suboptimalen Ergebnissen, wenn Sie zB {1,2}, {3,4}, {1,2,3,4}, {5,6}, {7,8}, { 5,6,7,8}. Nachdem Sie Ihre Reihenfolge der Vorgänge mit dem oben beschriebenen Verfahren festgelegt haben, können Sie dann einen Optimierungspass durchführen, bei dem Sie billigere Wege finden, die Summe jedes Satzes anhand der bereits berechneten Beträge zu bewerten. Dies wird wahrscheinlich in der Praxis ziemlich gute Ergebnisse liefern.

Ich vermute, aber habe nicht versucht zu beweisen, dass das Finden einer optimalen Prozedur für eine gegebene Menge von Teilmengen NP-schwer oder schlechter ist. (Es ist sicherlich berechenbar ; die Menge möglicher Berechnungen, die Sie machen können, ist endlich. Aber auf den ersten Blick mag es sehr teuer sein; möglicherweise können Sie etwa 2 ^ n partielle verfolgen summiert, addiert bei jedem Schritt einen von ihnen zu jedem anderen und hat bis zu etwa n ^ 2 Schritte, für einen übernatürlichen Preis von (2 ^ 2n) ^ (n ^ 2) = 2 ^ (2n ^ 3 ) Operationen, um jede Möglichkeit zu versuchen.)

Wenn angenommen wird, dass 'addition' nicht einfach eine ADD -Operation ist, sondern eine sehr intensive Funktion mit zwei ganzzahligen Operanden, dann wäre ein naheliegender Ansatz, die Ergebnisse zwischenzuspeichern.

Das erreichen Sie über eine geeignete Datenstruktur, zum Beispiel ein Schlüsselwertwörterbuch mit den Schlüsseln der beiden Operanden und den Antworten als Wert.

Aber wie Sie C in der Frage angegeben haben, wäre der einfachste Ansatz ein n by n Array von ganzen Zahlen, wobei die Lösung für x + y bei array[x][y] gespeichert wird.

Sie können dann wiederholt über die Teilmengen iterieren und für jedes Operandenpaar die entsprechende Position im Array überprüfen. Wenn kein Wert vorhanden ist, muss er berechnet und in das Array platziert werden. Der Wert ersetzt dann die beiden Operanden in der Teilmenge und du iterierst.

Wenn die Operation kommutativ ist, sollten die Operanden sortiert werden, bevor das Array nachgeschlagen wird (d. h. so dass der erste Index immer der kleinste der beiden Operanden ist), da dies "Cache" -Hits maximiert.

Eine übliche Optimierungstechnik besteht darin, Zwischenergebnisse vorzuberechnen. In Ihrem Fall könnten Sie alle Summen mit 2 Summanden aus A vorberechnen und in einer Nachschlagetabelle speichern. Dies ergibt |A|*|A+1|/2 Tabelleneinträge, wobei |A| die Kardinalität von A ist.

Um die Elementsumme von Ai zu berechnen, müssen Sie:

• suche die Summe der ersten beiden Elemente von Ai und speichere sie in tmp
• solange noch ein Element x in Ai übrig ist:
• suche die Summe von tmp und x

Um die Elementsumme von A1 = {1,3,4,5} aus Ihrem Beispiel zu berechnen, gehen Sie folgendermaßen vor:

• lookup (1,3) = 4
• lookup (4,4) = 8
• Nachschlagen (8,5) = 13

Beachten Sie, dass die Berechnung der Summe eines gegebenen Ai keine Summierung erfordert, da die gesamte Arbeit bereits durchgeführt wurde, während die Nachschlagetabelle vorberechnet wurde.

Wenn Sie die Nachschlagetabelle in einer Hash-Tabelle speichern, ist lookup() in O (1).

Mögliche Optimierungen für diesen Ansatz:

• konstruiert die Nachschlagetabelle während der Berechnung der Summierungsergebnisse; daher berechnen Sie nur die Summierungen, die Sie tatsächlich benötigen. Ihre Nachschlagetabelle ist jetzt ein Cache.
• Wenn Ihre Additionsoperation kommutativ ist, können Sie die Hälfte Ihrer Cachegröße speichern, indem Sie nur die Summierungen speichern, bei denen der kleinere Summand zuerst kommt. Dann ändern Sie lookup() so, dass lookup(a,b) = lookup(b,a) if a > b .

Wenn angenommen wird, dass die Summierung zeitaufwändig ist, finden Sie LCS für jedes Paar von Teilmengen (unter der Annahme, dass sie als sortiert sind) in Kommentaren erwähnt, oder, wenn sie nicht sortiert sind, sortiere sie), danach Summe der LCS der maximalen Länge (über alle LCS in Paaren), dann ersetze ihren Wert in verwandten Arrays mit verwandten Zahlen, ihre LCS aktualisieren und diesen Weg bis fortsetzen Es gibt keine LCS mit mehr als einer Nummer. Sicher ist das nicht optimal, aber es ist besser als naive Algorithmus (kleinere Anzahl von Summierung). Sie können jedoch Backtracking durchführen, um die beste Lösung zu finden.

z. B. für Ihre Beispieleingabe:

Sie können es immer noch verbessern, indem Sie die Summe zweier Zufallszahlen berechnen und dann wieder LCS nehmen, ...

NEIN. Es gibt keine effiziente Technik.

Weil es ein NP-vollständiges Problem ist. und es gibt keine effizienten Lösungen für ein solches Problem

Warum ist es NP-vollständig? Wir könnten den Algorithmus für dieses Problem verwenden, um das Cover-Problem zu lösen , indem wir einfach ein Set setzen, das alle Elemente enthält.

Beispiel: Wir haben Sätze von Elementen A1 = {1,2}, A2 = {2,3}, A3 = {3,4} Wir wollen das Set-Cover-Problem lösen.

Wir fügen zu diesem Satz eine Menge von Zahlen hinzu, die alle Elemente enthalten A4 = {1,2,3,4}

Wir verwenden algorhitm, für das John Smith anfragt, und wir prüfen, ob die Lösung A4 mit whit dargestellt wird. Wir haben NP-Complete Problem gelöst.