Angenommen, ich habe K-Arrays unterschiedlicher Größe:
%Vor%Alle Arrays enthalten Elemente desselben Datentyps.
Und dann habe ich eine Funktion, F = f(Xn, Ym,...K-2 more such elements) . Die Funktion benötigt grundsätzlich genau ein -Element von jedem Array, und mein Ziel ist es, einen maximalen Wert für diese Funktion zu finden. Und auch, was alle Elemente machen
maximal.
Wichtige Informationen
Art der Funktion: Alle Arrays sind sortiert (absteigend). Und das erste Element in jedem Array bietet die beste Lösung für die Funktion (maximiert die Funktion innerhalb ihrer Peer-Menge). Der ideale Fall wäre also, das erste Element von jedem Array aufzunehmen. Aber es gibt eine Einschränkung, die ich am besten beschreiben kann:
Wenn diese Elemente Zahlen sind, dann muss ich ihre Gesamtsumme weniger als einen konstanten Wert behalten. Die Einschränkung ist also:
%Vor%BEARBEITEN : Wie @Spekter gefragt hat, ist die Funktion exponentiell.
Wie kann ich das ohne rohe Gewalt lösen? Irgendwelche Hinweise auf Lösungen zu ähnlichen vorhandenen Problemen würden auch helfen!
Ich verstehe Divide & amp; erobern, dynamische Programmierung und lineare Programmierung bis zu dem in Einführung in Algorithmen-CLRS gelehrten Ausmaß. Wenn ich also etwas davon anwenden kann, kann ich das im Hinblick auf dieses Problem nicht herausfinden.
BEARBEITEN : Eine Beispielfunktion und ein Dataset für das obige Problem:
Maximiere: F = a x + b y + c z
Die obige Funktion war nicht sehr genaue Darstellung des ursprünglichen Problems.
UPDATE: Beispielfunktion aktualisiert
F = xh (x) g (x) + yh (y) g (y) + zh (z) g (z )
h und g sind nicht abnehmende lineare Funktion von x / y / z. Bereich von h variiert von 1 bis 2. Bereich von g variiert von 1 bis 50. Domain von x, y, z ist positive reelle Zahlen mit Durchschnittswert in Millionen (10 Millionen als Maximum für das Beispiel im voraus betrachten).
Beispieldatensatz (x, y, z sind in Millionen):
x is in [20,18,17,15,12,9,8,5]
y is in [26,21,16,13,6,3,2,1]
z is in [45,42,41,40,12,3,2,1,0]
Die Arrays enthalten also zufällige, aber sortierte Werte.
Und a,b,c > 1 Also nimm a = 2, b = 3 und c = 4, um zum Beispiel die Funktion wie folgt zu machen:
F = 2 x + 3 y + 4 z
Die Einschränkung: x + y + z <= 50
Ich habe die Beispielfunktion nach Spektres Lösung aktualisiert, aber dieser Algorithmus sollte immer noch gültig sein, da die Funktion immer noch eine ansteigende Funktion von x, y, z ist.
Beispielcode für h (), g () und Arrays (in JavaScript)
%Vor%Die Beispieldaten, die Sie bisher zur Verfügung gestellt haben, bieten einige Möglichkeiten zur Optimierung:
Verwenden Sie anstelle des Vergleichs von x , y und z die Zwischenberechnung x*h(x)^g(x) oder eine vorberechnete Tabellensuche dieser Werte. Betrachtet man die gerundete und proportional reduzierte Ausgabe für eine einfachere Darstellung, x / 100000 und Math.round(x * Math.pow(h(x), g(x)) / 100000) , sehen wir, dass einige Werte mehr als eine Größenordnung größer sind als andere.
Gruppieren Sie Variablen und deren funktionale Zwischenergebnisse als Tupel gemäß einer kalibrierten Auswahl von Bereichen der Größenordnung k . Wenn Sie zum Beispiel unsere reduzierte Übersicht verwenden, sagen wir k = 500 :
Es macht keinen Sinn, verschiedene Möglichkeiten für zs auszuprobieren, wenn wir einen Wert haben, der mehr als 150 mal größer ist als irgendein x oder y . Sobald wir die größere Variable entfernt haben, ist unsere Suche nun: maximize f'(x,y), where x + y <= 50 - 45) .
Wenn Sie Datenergebnisse mit extremen Unterschieden in der Größenordnung vorhersehen, weil f in der Zwischenberechnung tatsächlich linear ist, nennen Sie es i(x) , können Sie bei jeder Eliminierungsrunde eine Kalibrierung implementieren, bis Sie mit Optionen innerhalb derselben konfrontiert werden Größenordnung, wo Sie Brute-Force mit einem gierigen frühen Ausgang verwenden würden.
Nun, jetzt ist es viel klarer. Da die maximale Summe auf Eingabevariablen angewendet wird, nicht auf die Ausgabewerte von f , ist es viel einfacher. Also hier der erste einfache Ansatz in C ++ :
Ausgabe:
%Vor% Die Idee ist, nur solche Kombinationen zu testen, deren Summe in der Nähe von MaxSum constraint liegt. Wie Sie sehen können, sind die Loops fast identisch, so dass Sie beliebig viele verschachteln können. Wenn Sie eine variable Anzahl der Eingangsarrays erhalten haben, können Sie
Algorithmus:
Das Programm durchläuft grundsätzlich "alle Möglichkeiten" von der größten bis zur niedrigsten.
Testen Sie dann nur, wenn die Zielsumme kleiner oder gleich MaxSum ist.
danach, wenn die Partialsumme klein genug ist, dass, selbst wenn sie verwendet wird, die größten Werte von unbenutzten Arrays immer noch in die MaxSum -Stoppschleife passen, um unnötige Iterationen zu vermeiden. Dies reduziert effektiv die Komplexität von Brute-Force O(n^k) zu O(g(n)^k) wobei n die durchschnittliche Array-Größe ist, k ist die Anzahl der Arrays und g(n) ist die durchschnittliche Anzahl der getesteten Werte pro Array (abhängig von der MaxSum,n,k und Array-Werte In Ihrem Testfall g(n)=2 )
Verbesserungen:
Wenn Sie jetzt Hintergrundinformationen über die Funktion f erhalten und wissen, dass einige Variablen signifikanter sind als andere (in Ihrem Testfall das Z -Array), können Sie diese Variable auf die ersten paar größten Werte begrenzen, die noch passen in dieses Limit, wobei die kleinen Werte dieses Arrays ignoriert werden. Dies kann auch auf anderen Arrays rekursiv erfolgen, aber SEHR SORGFÄLTIG , damit Sie die eigentliche Lösung nicht verpassen.
Sie könnten an gierigen Algorithmen interessiert sein. Das ist eine einfache, aber nützliche Idee. Zuerst denke ich, wenn ich ein solches Problem sehe, versuche mich dieser Technik zu nähern.
Ein anderer Ansatz ist die Methode des Gradientenabfalls .
Dynamische Programmierung ist eine Technik, die in Ihrem Fall gut funktioniert. Da Sie etwas mehr über Ihre Daten wissen - nämlich, dass die Listen sortiert sind - können Sie die Suche so optimieren, dass sie nicht zu weit in einen suboptimalen Pfad führt.
Das ist keine schnelle Antwort mit Pseudocode. Ich empfehle dringend, den Algorithmuskurs des MIT in seiner Gesamtheit zu beobachten, aber die Vorlesungen 19-22 beziehen sich auf die dynamische Programmierung. Hier ist die Playlist auf youtube.