spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Zitat von »Mastermind«

Jedenfalls, dass es sich hier um ein Optimierungsproblem handelt ist ja wohl eindeutig. Die Frage ist, wie ich oben schon sagte ob es sich als Quadratisches Programm darstellen lässt (linear wohl eher nicht). Dann wäre es nämlich "einfach".

Du hast vergessen, dass es sich hier um ein ganzzahliges Optimierungsproblem handelt.
Das heißt: Selbst wenn es linear wäre (was es nicht ist), wäre es dadurch immer noch NP-schwer, womit eine exakte Lösung in der Praxis nicht durchführbar ist.

(Ich weiß allerdings nicht, wie gut/schlecht die Lösungen zu erwarten wären, wenn man die Ganzzahligkeit ignoriert und die Lösung dann einfach "rundet")

Zitat von »Lifter«

Wenn ich mir das so angucke, dann müsste man dem Problem doch relativ schnell mit einer linearen Optimierung beikommen können.

Dann würde mich aber mal interessieren, wie Du die nicht-lineare Zielfunktion als lineare Funktion darstellen willst ...
Weder die Länge der Grenze noch die Qualität der Aufteilung kannst Du als lineare Funktion des Grenzverlaufs ausdrücken.
Hast Du die Diskussion hier überhaupt verfolgt?

Würde mich doch sehr wundern, wenn das ginge.

Zum Beispiel das mit der Grenze, wo die Bewertung vom Betrag der Differenzen zwischen benachbarten Grenzpunkten abhängt. Das kriegst Du prinzipbedingt niemals in ein lineares Optimierungsproblem verwandelt, weil Du die Betragsfunktion dort gar nicht darstellen kannst. Approximieren kann man da auch nichts.

Gut gemacht! Das ist genau das gleiche Ergebnis wie meins. Ich glaube auch nicht, dass es noch besser werden kann.
Habe auch noch einige Ideen, wie ich vom Zufall wegkommen kann, um das Ergebnis konstant hinzukriegen.

Idee umgesetzt, funktioniert
Damit es spannend bleibt, sollten wir aber keine weiteren Planeten mehr diskutieren!

Wow, ich habe gerade bemerkt, wie furchtbar langsam der vom GCC erzeugte Code im Vergleich zu dem von Visual C++ ist (ich hatte die ganze Zeit mit Visual C++ entwickelt, weil ich die IDE lieber mag).
Aktiviert man jedoch prozessorspezifische Optimierungen, so wird das Ganze etwas besser.
Kann das jemand bestätigen? Sollen wir die Auswertung mit prozessorspezifischen Optimierungen machen? (MMX, SSE - kann heute eigentlich jeder Prozessor, man muss es aber explizit aktivieren)