Du bist nicht angemeldet.

Werbeanzeige

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 184

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

11

18.07.2011, 08:43

Da bin ich mir nicht so sicher.
Ich glaube, dass eine "greedy"-Lösung bzw. eine, die einzelne Spalten lokal optimiert, nicht unbedingt das optimale Ergebnis liefert.

BlueCobold

Community-Fossil

Beiträge: 10 870

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

12

18.07.2011, 09:24

Richtig. Aber eine, die sämtliche Flächen Pixelweise umschließt. Das lässt sich in O ( n*m ) machen.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Beiträge: 775

Beruf: Student

  • Private Nachricht senden

13

18.07.2011, 09:26

Ich vermute, dass optimales Ergebnis exponentielle Komplexität hat:
Um die optimale Punktzahl zu erreichen reicht es nicht für jede Vertikale das Optimum zu finden, sondern man muss ja auch die Sache mit den schwach steigenden Linien beachten - das kann auch zu "nicht-intuitiven" Ergebnissen führen, was für das Optimum einen Backtracing-Algorithmus naheliegen lässt. Tjo also muss man x Linien die Score ermitteln: x*Breite*Höhe
Wieviele Möglichkeiten gibt es also für Linien? Nunja also für jede Vertikale hat man soviel Möglichkeiten wie die Vertikalen hoch sind. Für jeden Höhenwert in einer Vertikalen können auch alle anderen anders sein - also Höhe ^ Breite (wie bei einem Zahlenschloss mit Breite Rädern und mit je Höhe Werten)
Alle Möglichkeiten durchgehen wäre also dann O(Breite * Höhe * Höhe ^ Breite) = O(Höhe ^ Breite) also exponentielle Komplexität auf die Breite betrachtet.

Eine Art greedy hab ich übrigens schon ausprobiert - ist eine Katastrophe so wie ich es angegangen bin ^^
Ich hatte für jede Linie an jeden Punkt die lokale Score nur auf die Linie betrachtet ausgerechnet einmal für den Fall, dass Land unten ist und einmal für den Fall dass Wasser unten ist. Je nach Summe der Optimalen Scores dann das bessere von beiden genommen (Optimierungsmöglichkeit: Je nach Gesamtscore entscheiden). Wenn man allerdings ein bischen drüber nachdenkt merkt man schon, dass das bei der Art wie die Punkte errechnet werden nicht gut gehn kann.

Hab mir aber schon was heuristisches überlegt, was ich bei Gelegenheit vielleicht mal ausprobier wenn ich dazu komme... ich muss zugeben, dass ich die Aufgabe erst unterschätzt hab ^^

Edit:
@ BlueCobold
Hmm aber dadurch, dass man die Grenze nur in vertikaler Richtung festlegen kann, kann man ja nicht alle Bereiche eindeutig umschließen. Außerdem wäre das "Glattheitskriterium" ja dann so oder so stark verletzt.

@ drakon
Zu der Header Sache: Mich hat folgendes verwundert: Solange ich die <string> nicht seperat eingebunden habe, hat der Compiler sich bei std::cout << std::string beschwert, nicht aber bei string selbst. Woran kann sowas liegen? Kann es sein, dass durch andere Header eine nicht vollständige Definition dessen, was <string> bietet im Umlauf ist?

BlueCobold

Community-Fossil

Beiträge: 10 870

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

14

18.07.2011, 09:54

Jo, kommt halt drauf an, was man will ;) Optimale Punktzahl oder optimale Ausnutzung. Letztere ist mit O ( n*m ) sicher drin. Ersteres natürlich nicht ;)
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Pinta

1x Contest-Sieger

  • Private Nachricht senden

15

18.07.2011, 11:36

n*m stellt wohl die untere Schranke dar -> Omega(n*m).
Begründung: Für eine optimale Lösung muss man sich die Inputdaten anschauen und das sind schon mal n*m viele.

drakon

Supermoderator

Beiträge: 6 526

Wohnort: Schweiz

Beruf: Entrepreneur

  • Private Nachricht senden

16

18.07.2011, 11:53

@ drakon
Zu der Header Sache: Mich hat folgendes verwundert: Solange ich die <string> nicht seperat eingebunden habe, hat der Compiler sich bei std::cout << std::string beschwert, nicht aber bei string selbst. Woran kann sowas liegen? Kann es sein, dass durch andere Header eine nicht vollständige Definition dessen, was <string> bietet im Umlauf ist?

Das kann gut sein. Wenn du mal nach der Definition von string suchst findest du die in dem Header <xstring> (zumindest bei mir bei VC++2010), welcher wahrscheinlich sonst wo bereits inkludiert wird.
In <string> selbst sind dann Operatoren und zusätzliche Funktionen definiert (unter anderem auch Ein/Ausgabeoperatoren). Es könnte aber genau so gut sein, dass es selbst bei string alleine nicht kompiliert (mit einer anderen Implementierung).

17

18.07.2011, 13:14

Mal ne Blöde Frag ich hoffe sie steht nicht im Text dann habe ich es überlesen.

Die Grenze wohin gehört die, wenn sie gezogen ist, zum Nord-Teil oder Süd-Teil ?
Wer aufhört besser werden zu wollen hört auf gut zu sein!

aktuelles Projekt:Rickety Racquet

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 184

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

18

18.07.2011, 13:36

Die Grenze wohin gehört die, wenn sie gezogen ist, zum Nord-Teil oder Süd-Teil ?

border[x] enthält die y-Koordinate, ab der die südliche Hälfte beginnt. Also die Grenze gehört zum südlichen Teil.

19

18.07.2011, 13:39

Oki Danke.
Wer aufhört besser werden zu wollen hört auf gut zu sein!

aktuelles Projekt:Rickety Racquet

20

18.07.2011, 16:43

Eine kleine Frage, was ist Nord-/Südpol in soner Karte?

Werbeanzeige