spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Er meint damit: Ein Thema in seiner KI-Vorlesung.
Vermutlich zum Thema Backtracking und NP-Vollständigkeit.

Und ja, das meinte ich. Wobei mir natürlich klar ist, das es nicht erlaubt ist. Nur interessant zu sehen was der "maximal" erreichbare Faktor ist. Da geht nicht viel im Vergleich zum Greedy-Ansatz.

Das wohl größte Problem dabei ist, das die Greedy-Funktion zeitlich kaum zu schlagen sein dürfte. Einige Ansätze benötigen zB eine sortierte Liste, diese oder andere Vorbearbeitungen sorgen für einen an sich schnelleren Algorithmus kosten dafür aber wieder für zuviel Zeit.

Einfach die Bedeutung des Faktors Zeit runterzuschrauben wäre natürlich eine Möglichkeit.

ehrlich gesagt fand ich bei der bewertung den greedy-algorithmus zu schlagen auf den erstenblick auch ziemlich schwierig, aber anderer seits, bekommt der contest damit eine bisschen andere entwicklung. anstatt, dass alle versuchen fertige algorithmen aus dem netz möglichst gewinn bringend umzusetzen, muss man eher n bisschen kreativ sein, oder so. dann gewinnen nicht immer die, die die größten performance künstler sind.. ich finds ganz witzig so..
gruß

Ich fänd's auch ok, wenn der Zeitfaktor nicht ganz so stark in's Gewicht fallen würde. Allerdings habe ich und - ich bin mir ganz sich - ihr auch den einfachen greedy bereits geschlagen.

Der Punkt ist jetzt ja nur wie viel besser sind wir als greedy. In meinem ersten Versuch war es bei mir nur ~1.5 - aber immerhin besser!

Also, wieso nicht einfach die Aufgabe so lassen und etwas kreativ werden??!!

mfg,
Atlan

Momentan bin ich bei ~1.6126. Ohne Optimierungen... Mal schauen...

EDIT: Erhöhe auf ~1.98995 ohne Optimierungen.
EDIT2: Jetzt bei ~2.29 festgefahren. Naja, mache ich mich mal an's Optimieren...

Ich hab einen exakten Algo, der allerdings nur 0.65 schafft, vielleicht schaff ich es, da noch was mit einer besseren Sortierung zu erreichen.
Mein zweiter Algo schafft unoptimiert einen Faktor von >1,2, mal schaun, wie viel ich da noch rausholen kann.

EDIT: 1,4 mit Optimierung

Erhöhe auf ~2 ohne Optimierungen.