spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Ich habe auch 2 Phasen.
in der erste schafft er immerhin schonmal 0,733irgendwas in 0 ms;
bei der 2ten hälfte bin ich noch am tüfteln bzw debuggen da es noch nicht richtig geht.

Zitat von »xTr1m«

Zuerst versucht er eine möglichst gute Approximation der Lösung zu finden (dauert bei mir ca. 60ms im schnitt), und dann wird er iterativ solang es noch Zeit gibt versuchen, diese zu verbessern. Bin gerade eben mit Phase 1 fertig, diese erzeugt eine Qualität von 0,8229 aber eine gewichtete Punktzahl von 0,51898.

Genau das gleiche hab ich auch vor; und bin sogar gleich weit wie du
Bei mir habe ich jetzt in 1ms geschafft die Qualität auf 0,84341 zu kriegen (gewichtet: 0,57041), und muss jetzt auch noch die Grenze etwas schöner ziehen. Wobei meine bisherigen Versuche noch nicht geglückt sind :/ Naja, vielleicht bekomm ich ja noch was her.

0,78044 bei Planet00.png.... grr, sehr sehr knapp, aber ich kriege euch!

Wenn mich nicht alles täuscht, ist das eigentlich ein Fall von Lagrangian ermitteln. Keine Ahnung ob ein solcher Ansatz schnell genug ist, aber ggf. sind Lagrange-Multiplikator und Virtuelle Verrückung hilfreiche Begriffe, wobei ich keinerlei Garantien übernehme. Vorallem bei letzteren müsste man wohl noch die "Länge des Weges" irgendwie als "Arbeit" berücksichtigen, was wohl nicht ganz trivial ist. Alternativ könnte ein "Kräfte" Ansatz, der solange er Zeit hat, die Kraft (bzw. die Potenzial- aka Punkteänderung) auf jedes "Schnurrglied" ermittelt und dann einen Zeitschritt weiter propagiert eine weitere Imitation der Physik sein.

Vielleicht willst du das ja mal genauer erklären? Die Erklärungen zu den genannten Begriffen auf Wikipedia sind mir nämlich alle zu hoch...

Zitat von »Nox«

Wenn mich nicht alles täuscht, ist das eigentlich ein Fall von Lagrangian ermitteln. Keine Ahnung ob ein solcher Ansatz schnell genug ist, aber ggf. sind Lagrange-Multiplikator und Virtuelle Verrückung hilfreiche Begriffe, wobei ich keinerlei Garantien übernehme.

Ich denke so kann man das Problem auch betrachten, allerdings ist ja das Ziel vom Contest das globale Minimum (Maximum aus Sicht der Punktzahl) zu finden, möglichst schnell versteht sich.
Die einzig spannende mathematische Frage in dem Zusammenhang wäre doch: "Gibt es eine rein analytische Lösung für gewisse/alle Arten von Flächen?"

Wenn man das als Problem der Informationstheorie mit der Brute-Force-Brille betrachtet, muss man halt x^y Bits, Daten, Pixel, ... verarbeiten.

@Mastermind mir sagt ehrlich gesagt der Begriff "duales Programm" nichts. Daher kann ich nicht sagen ob und wie da ein Zusammenhang existiert.

@FalkT würden Physiker immer den kompletten Phasenraum durchtesten (was ungefähr deiner Annahme entspricht), dann wäre wohl nur ein und zweiteilchen Problem bisher gelöst .

Alles aus dem Gedächtnis und ohne Garantien auf Korrektheit:
Der Lagrangian im Sinne der Physik beschreibt den "Pfad" dein ein Objekt wirklich nehmen würde. Eine Methode diesen zu ermitteln ist über die virtuellen Verrückungen in welche im Endeffekt die Annahme eingeht, dass der "reale" Pfad der energetisch korrekte/günstigste ist.
Lagrange-Multiplikatoren bieten sich immer dann an, wenn man neben einer "primitiven" Gleichung noch "Zwangsbedingungen" als Gleichungen formulieren kann. Wenn es also gelingt beide Teilbedingungen als analytische Formel zu beschreiben, wäre das Extrema schnell zu ermitteln. Oder falls es möglich sein sollte das Konzept der Lagrange-Multiplikatoren auf Distributionen/diskrete "Funktionen zu übertragen, könnte es auch klappen. Für das Prinzip der Lagrange-Multiplikatoren bietet es sich eig an die physikalischen Beispiele anzuschauen.
An dieser Stelle möchte ich nochmal betonen, dass das nur so "Blitzgedanken" waren, die mir bei dem Thema kamen. Keine Ahnung in wiefern sie wirklich anwendbar sind. Im Prinzip laufen aber alle meine Ideen auf ein "Finde den optimalen Pfad auf einem Potenzial und der gegeben Umständen" hinaus.

Im meinen Umfeld werden Lagrange-Multiplikationen hauptsächlich im Rahmen des Lagrangeformalismus genutzt, somit sprechen die meisten Menschen (die ich kenne) von Lagrangefunktion und Zwangskräfte bzw. Zwangsbedingungen.

Mir ging es eig nur darum mal ein paar Gedanken, die mir zu der Problemstellung kamen einfach mal in den Raum zustellen ungeachtet dessen, ob und wie es im Endeffekt anwendbar ist, aber mit der Hoffnung, dass es vielleicht hilfreich sein könnte.

EDIT: *murmelt was von lieber doch nicht diesen anderen Ansatz posten*