Ganzzahlige Optimierung oder so ^^
-
Jester schrieb:
Gregor schrieb:
"NP hart".
NP-schwer, es heißt NP-schwer. "hart" ist einfach nur eine schlechte Übersetzung von "hard".
Hmmm... da habe ich mich wohl der Fehlübersetzung schuldig gemacht. Wird nicht wieder vorkommen.
Jester schrieb:
@Topic:
Dummerweise ist sein Problem auch nicht linear.
Andererseits hat er keine Nebenbedingungen. Sofern die Funktion konvex ist, sollte sich da doch auch eine gute Lösung in der Nähe der reellen Lösung finden...Ja, habe ich im Nachhinein auch realisiert. Das macht das ganze natürlich wesentlich problematischer.
-
a^2 + b^2 +a = 2400
Das Problem sieht so freundlich (bzw. konvex) aus, dass du einfach die reelle Lösung hernehmen kannst und viermal alle möglichen Rundungen ausprobierst, um zum Minimum zu kommen.
f(a,b)= k * Q(a) * Q(b)
Das sieht aber anders aus als dein zweites Problem - hier werden die quadratischen Terme multipliziert, nicht addiert.
Prüfe doch mal, ob deine Zielfuktion immer konvex ist!
-
was ist denn die reelle Lösung? die Lösungsmenge ist eine Kurve im R^2 ...
wenndu die 2400 gegen eine 2401 tauschst, finde ich zwei ganzzahlige Lösungen im Kopf:
a=0, b=49
a=-1, b=49
-
Sorry, habe im Beispiel addiert statt zu multiplizieren.
Eine geeignete Aufgabe wäre :
a^2 * b^2 * a = 2400
Ich schau mir das mit dem "konvex-Sein" nochmal genauer an.
Danke soweit
-
buchstaben schrieb:
was ist denn die reelle Lösung? die Lösungsmenge ist eine Kurve im R^2 ...
Ache auf mein Haupt - du hast natürlich recht
-
shisha schrieb:
a^2 * b^2 * a = 2400
Das ist aber nicht mehr so recht quadratisch
a^2 * b^2 * a = a^3 * b^2
-
Die erste Problemstellung lautete ja "f(a,b)-K = min". Wenn das konvex ist, dann ist das ne relativ kleine Kurve.
@OP: wenn da ein Problem zugrunde liegt, das Du glaubst auf diese Weise gut formalisiert zu haben, wäre jetzt der richtige Zeitpunkt mit der echten Problemstellung rauszurücken. -- In der Allgemeinheits wirds ansonsten schwierig.
-
shisha schrieb:
Diese Gleichung würde ich gerne lösen.
Loesen oder ueber a,b minimieren? Fuers Minimieren sollte nur nach a bzw. b abzuleiten sein. Da keine Nebenbedingungen erfuellt warden muessen, ist das Problem trivial. Dann suchst du einfach im Bereich der ganzen Zahlen um der reellen Loesung herum, nach dem optimalen Wert.
-
a^3 * b^2 = 2400 hat keine ganzzahlige Lösung, weil der Primfaktor 3 in der 2400 nur 1-fach vorkommt.
-
buchstaben schrieb:
a^3 * b^2 = 2400 hat keine ganzzahlige Lösung, weil der Primfaktor 3 in der 2400 nur 1-fach vorkommt.
Interessanter Ansatz. Kann man die Problemstellung so formulieren, dass man eine moeglichst kleine Zahl groesser gleich 2400 sucht, deren Primfaktorzerlegung bestimmte Eigenschaften hat, was die Anzahl identischer Primfakoren betrifft?
-
Das Thema ist "ganzzahlige Optimierung" und im Anfangsposting steht "f(a,b) - K = min". Das lässt nur den Schluss zu, dass es um ein Minimierungsproblem geht, nicht um Gleichunglösen.
-
| a^3 * b^2 - 2400 | = min löse ich auch noch im Kopf:
b = 49 ergibt a^3 - 2400/2401 = min
also a = 1, b = +/- 49, und | a^3 * b^2 - 2400 | = 2401 - 2400 = 1
besser als mit einer Abweichung von 1 kann man's ganzzahlig nicht hinbekommen, da Abweichung 0 wegfällt, weil es als Gleichung nicht ganzzahlig lösbar ist (wegen Primfaktor 3 in 2400) also gelöst.
nächstes Problem ?
-
ALso das genaue Problem ist in diesem Falle:
a*(a+1) * b*(b+1) = 8000000
-
a*(a+1) * b*(b+1) = 8000000
Schritt 1: Gleichung nach b umstellen, gibt für jedes a zwei Lösungen für b.
Für -1 <= a <= 0 gibt es gar keine Lösung.
Schritt 2: Tabelle aufstellen für -400 <= a <= 400, passendes b ausrechnen und runden.Beste Lösungen:
a b 36 -78 36 77 77 -37 77 36 -37 -78 -37 77 -78 -37 -78 36Dafür ist | a*(a+1) * b*(b+1) - 8000000 | = 8, und etwas besseres habe ich nicht geraten. Falls es etwas tolleres gibt, vermutlich nur für a > 400.
Leider nicht sehr mathematisch. Geht es hübscher?!
-
Also geht es gar nicht um ein Optimierungsproblem in erster Linie sondern um das Loesen impliziter Funktionen. Schaue dir mal an, wie man in der Computergrafik effizient implizite Funktionen im 2D zeichnet. Oder Contourlines oder Isolines oder ...
Was hindert dich daran, a=1 zu setzen und b ausrechnen? Ausgehend von diesem Punkt kannst du die Kurve verfolgen. Marching Squares sei als Stichwort genannt. Aus der Loesungsmenge wird dann das Element mit dem kleinsten Fehler herausgenommen.
Demnach muss ich mich korrigieren:
Gibt es da ein Standardvorgehen, das unabhängig von f ist?
Ja!