spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Zitat von »David Scherfgen«

Ich bin jetzt nicht der Fachmann in Sachen dynamische Programmierung.
Bei Wikipedia steht:

Zitat

"Dynamische Programmierung kann dann erfolgreich eingesetzt werden, wenn das Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht, und eine optimale Lösung des Problems sich aus optimalen Lösungen der Teilprobleme zusammensetzt"

Ist dies denn hier der Fall?

Ich denke nicht! Denn wenn ich z.B. die Karte in zwei Hälften teile und jede davon optimal aufteile, dann kann ich beim Zusammensetzen immer noch durch die Nahtstelle und den damit verbundenen Punktabzug suboptimal werden. Außerdem könnte es sein, dass ich bei einer der beiden Lösungen gezwungenermaßen eine der beiden Zivilisationen benachteilige. Das könnte ich in der anderen Hälfte wieder ausgleichen. Löse ich jedoch beide getrennt, weiß ich davon garnichts und kann das nicht berücksichtigen.

An den oben genannten O(n²)-Algorithmus glaube ich jedenfalls nicht.
Zumal da "n" die Anzahl der Zeilen sein soll - und die Anzahl der Spalten ist dann völlig irrelevant, was die Komplexität angeht?

Ich kenn ne ganze Menge Algorithmen die auf Dynamic Programming basieren, aber ist z.T. schon lange her. Tatsache ist dass DP nicht Divide&Conquer ist (dein Argument richtet sich gegen D&C) und das Otze O(n²*m) behaupten hat (dein Argument richtet sich gegen O(n²)). Davon abgesehen komm ich aber auch nicht drauf. Ich denk noch ein wenig drüber nach...

Da ich es wirklich nicht hier zum laufen bringen mag könnte vielleicht jemand angeben, wie die Karten aussehen? Handelt es sich um ein zufälliges Bitmuster der Länge 512² oder gibt es (wie das Bespiel suggeriert) eine Struktur?

For what its worth, das Worst-Case Muster bezüglich der einen Bedingung ist ein Schachbrett, (ggf. 2*2) da man immer mindestens die Hälfte der Punkte falsch klassifiziert, dafür ist dy=0. Das Worst-Case Muster bezüglich der anderen Bedingung sind senkrechte durchgehende Streifen. Perfekte Klassifikation möglich aber dy in jedem schritt maximal.

Was noch relativ spannend ist, ist dass die Zielfunktion recht komisch gewichtet(wenn ich sie nicht falsch verstehe). Eine waagerechte Linie durch WorstCase 2 ergibt eine Punktzahl von 1/2 * 1/2 * 2/3 + 1/3 = 5/12. Die "perfekte" Klassifikation dagegen ergibt 2/3 + (1-(512*512)/2048 )*1/3 = -500/12

Man kann also relativ viel Fehlklassifikation in Kauf nehmen um eine glattere Grenze zu bekommen. Bin nun zu faul das Optimum in Bezug auf die genannte Karte zu bestimmen, die Information wo der "break even" liegt könnte jedoch hilfreich sein.