3. Algorithmus gesucht...

Algorithmus gesucht...

  • V

    Gregor schrieb:

    Wenn das wirklich so gemeint war, dann geht das schneller! 🙂 -> Eigenschaften der Faltung

    ? was heißt das?

    0
  • W

    Ich gehe mal davon aus, dass dein Prob so gemeint ist: du hast ein 100x100-Feld von Zahlen, die kleiner als 1 sind. Nennen wir diese mal p(x,y), x die Zeile, y die Spalte. p(x,y) ist die Wahrscheinlichkeit dafür, dass sich das Objekt (was auch immer es ist) an Stelle (x,y) befindet. Und jetzt willst du sowas wie einen Mittelwert bilden. ???
    Wenn das so ist, würde ich folgendes vorschlagen: Wir wollen zunächst mal den wahrscheinlichsten x-Wert ermitteln. Dazu gewichten wir jede x-Koordinate mit den Wahrscheinlichkeiten in der x-ten Zeile:

    x * p(x,1) + x * p(x,2) + ... + x * p(x,100)

    Also

    x * ( p(x,1) + p(x,2) + ... + p(x,100) )

    Nennen wir diesen Wert mal PX(x). Dann ist die wahrscheinlichste x-Koordinate:

    X = Sum(PX(x), für x=1 bis 100)

    Der wahrscheinlichste y-Wert ist dann analog

    Y = Sum(PY(y), für y=1 bis 100),

    wobei

    PY(y) = y * ( p(1,y) + p(2,y) + ... + p(100,y) ).

    Der Punkt (X,Y) ist dann dein "Wahrscheinlichkeitsschwerpunkt". Auf ebendiese Weise berechnet man übrigens auch den geometrischen Schwerpunkt von Objekten - bloß, dass dort die Summen zu Integralen werden.

    0
  • V

    aber die wahrscheinlichste x-koordinate und die wahrscheinlichste y-koordinate sagen mit gar nichts über die wahrscheinlichste xy-position.

    0
  • W

    volkard schrieb:

    aber die wahrscheinlichste x-koordinate und die wahrscheinlichste y-koordinate sagen mit gar nichts über die wahrscheinlichste xy-position.

    Doch! Schau dir nochmal meinen editierten Beitrag an.

    0
  • V

    WebFritzi schrieb:

    volkard schrieb:

    aber die wahrscheinlichste x-koordinate und die wahrscheinlichste y-koordinate sagen mit gar nichts über die wahrscheinlichste xy-position.

    Doch! Schau dir nochmal meinen editierten Beitrag an.

    ok, der hat ein fachwort drin. dennoch nonsense.

    0
  • W

    volkard schrieb:

    ok, der hat ein fachwort drin. dennoch nonsense.

    Du benimmst dich wie Frau Merkel! Begründe doch bitte deinen Einwand und sag, wie du dir das vorstellst. Es funktioniert jedenfalls, wenn du alle Felder bis auf eines auf 0 setzt (das eine natürlich auf 1).

    0
  • V

    WebFritzi schrieb:

    Du benimmst dich wie Frau Merkel! Begründe doch bitte deinen Einwand und sag, wie du dir das vorstellst. Es funktioniert jedenfalls, wenn du alle Felder bis auf eines auf 0 setzt (das eine natürlich auf 1).

    dachte, der fehler sei so naheliegend, daß es reicht, ihn anzuzeigen. dadurch, daß ich den schwerpunkt einer großen ungleich dicken platte berechne, bereichne ich nicht im entferntesten den ort der größten dicke.

    .9 .1 .1
.1 .8 .8
.1 .8 .8

PX(1)=1*1.7
PX(2)=2*1.7
PX(3)=3*.9
X=(1*1.1+2*1.7+3*1.7)/3==3.2
PY(1)=1*1.7
PY(2)=2*1.7
PY(3)=3*.9
Y=(1*1.1+2*1.7+3*1.7)/3==3.2
Der Punkt (X,Y) ist dann dein "Wahrscheinlichkeitsschwerpunkt". Und der
liegt _außerhalb_! Und überhaupt liegt er verdammt weit vom Feld mit 
der höchsten Warscheinlichkeit weg.
    0
  • W

    Ist doch auch klar, dass er außerhalb liegt. Dein Wahrscheinlichkeitsschema ist auch nicht der Aufgabe angepasst. Die Summe deiner Wahrscheinlichkeiten ergibt ja garnicht 1. Dann mal ein Beispiel von mir:

    .1 .1 .1
.1 .2 .1
.1 .1 .1

    So, das ergibt 1. Jetzt mal die Berechnungen:

    PX(1) = PY(1) = 0.3
PX(3) = PY(3) = 0.9
PX(2) = PY(2) = 0.8
==> X = Y = 2

    Zufrieden?

    0
  • ?

    👍 Webbi rulz 🕶 👍 😋

    0
  • B

    WebFritzi schrieb:

    Ist doch auch klar, dass er außerhalb liegt. Dein Wahrscheinlichkeitsschema ist auch nicht der Aufgabe angepasst. Die Summe deiner Wahrscheinlichkeiten ergibt ja garnicht 1.

    Dann teilst du halt jeden Wert durch die Summe aller Werte. Ändert am Argument überhaupt nichts.

    0
  • W

    OK, damit ihr's noch eher glaubt, hier noch ein nicht ganz so simples Beispiel:

    .0 .1 .3
.0 .1 .4
.0 .0 .1

    Hier wäre es zu erwarten, dass der berechnete Wert nahe bei (2,3) liegt. Und das stimmt auch:

    PX(1) = 0.4
PX(2) = 1.0
PX(3) = 0.3
==> X = 1.7

PY(1) = 0.0
PY(2) = 0.4
PY(3) = 2.4
==> Y = 2.8
    0
  • V

    was nutzen mir 3 beispiel von dir, die klappen?
    ich hab ein beispiel gegeben, was nicht klappt. damit ist deine these kaputt.

    0
  • V

    WebFritzi schrieb:

    OK, damit ihr's noch eher glaubt, hier noch ein nicht ganz so simples Beispiel:

    .0 .1 .3
.0 .1 .4
.0 .0 .1

    zu unschief.
    rechne mir mal das hier vor.

    .4 .0 .0 
.0 .1 .1
.0 .1 .3
    0
  • W

    Ah, ich verstehe, was du meinst. Naja, das beste Beispiel dafür wäre ja

    .5 .0 .0 ... .0
.0  .        .0
.0    .      .0
...     .    .0
...       .  .0    
...         ..0
.0 .0 .0 ... .5

    Das soll das 100x100-Feld sein. Mein Punkt wäre genau in der Mitte. Dabei stellt sich aber natürlich die Frage, was nun als "wahrscheinlichste Koordinaten" angesehen werden sollen. Mir fällt dabei nichts anderes ein als mein Vorschlag. Ich würde mir wünschen, man hätte weitere Informationen, woher die Daten kommen.

    0
  • W

    [Blödsinn]

    0
  • V

    WebFritzi schrieb:

    Ah, ich verstehe, was du meinst. Naja...

    ok. und das mächste mal werd ich wieder merkeln.
    aufgabe war, wenn ich die richtig verstanden hab, das 5*5-kästchen mit der größten summe zu finden. gegeben ist ein 100*100-kästchen voller werte.

    ne, eher nicht.
    er hat in den 100^2 feldern die wahrscheinlichkeiten, daß dort jeweils der mittelpunkt eines 5^2 großen objekts ist.
    was er sucht, ist völlig unklar. es könnte zum beispiel die position maximaler wirkung sein, auf die man eine nuke werfen müßte, die als wirkung summe(feldinhalt/abstand^2) hat. ist dir formel aber summe(feldinhalt/abstand), kommt was ganz anderes raus.
    also aufgabe wegen uneindeutigkeit abgelehnt. *g*

    es gibt sogar eine wirksamkeitsformel, wo der wahrscheinlichkeitsschwerpunkt die lösung ist.

    0
  • W

    volkard schrieb:

    er hat in den 100^2 feldern die wahrscheinlichkeiten, daß dort jeweils der mittelpunkt eines 5^2 großen objekts ist.

    Genau das dachte ich mir auch!

    also aufgabe wegen uneindeutigkeit abgelehnt. *g*

    Find ich auch!

    es gibt sogar eine wirksamkeitsformel, wo der wahrscheinlichkeitsschwerpunkt die lösung ist.

    Oh, vielen Dank! 😉

    0
  • ?

    Hallo zusammen,

    Gregor:
    Was verstehst du unter diesen Bereichen? Gehören da alle Punkte zu, die über einem bestimmten Schwellenwert liegen? ...und willst du jeweils die Mittelpunkte von den zusammenhängenden Bereichen finden?

    1. JA! Genau das ist es was ich will! Zu beachten ist,
    daß die Bereiche NICHT notwendigerweise Quadratisch oder Rechteckig sind,
    sondern auch unformig sein können!

    2. Was bitte ist FALTUNG! Könntest Du mir bitte einige Links nennen? Danke!

    Kroe:
    Ist das nicht simpel, oder habe ich was verkehrt verstanden?!?

    1. Das tatsächliche Feld hat eine Größe von 1000 x 1000!
    2. Die Größe des Objekts ist NICHT vorgegeben!
    (Meine Ausführung war nur ein Beispiel!)
    Dein Lösungsansatz ist SEHR naiv (und ich dachte meiner sei es...!).
    Du weißt, daß Speicher und Zeit kostbar sind, gell?
    Allenvoran sollte es NICHT zeitaufwändig sein!!!

    @c++==d:
    Danke, den Wettbewerb kenne ich! Tatsächlich eine Herausforderung...!
    Ich bin c't-Abonnent 😉 kenne die Artikel sehr gut ;-))

    @WebFritzi:
    Tut mir Leid, hab heute bisserl zu viel gearbeitet, aber Dein Ansatz ist interessant...
    Ich werde ihn mir zu einem späteren Zeitpunkt noch mal genauer ansehen!
    Danke schön!

    Adrian

    0
  • G

    Anonymous schrieb:

    1. JA! Genau das ist es was ich will! Zu beachten ist,
    daß die Bereiche NICHT notwendigerweise Quadratisch oder Rechteckig sind,
    sondern auch unformig sein können!

    2. Was bitte ist FALTUNG! Könntest Du mir bitte einige Links nennen? Danke!

    2. Eine Faltung ist eine mathematische Operation, die im 2-Dimensionalen, diskreten durch folgendes gegeben ist: http://mrl.nyu.edu/~dzorin/intro-graphics/handouts/filtering/img97.gif

    Wenn du jetzt die 5*5 Felder betrachtest, die um einen Punkt herum liegen, dabei alle Felder gleich gewichtest und das ganze in einer Zahl zusammenfaßt, dann machst du eigentlich nichts anderes, als mit folgendem Faltungskern dein 2-dimensionales Array zu falten:

    0.04  0.04  0.04  0.04  0.04
0.04  0.04  0.04  0.04  0.04
0.04  0.04  0.04  0.04  0.04
0.04  0.04  0.04  0.04  0.04
0.04  0.04  0.04  0.04  0.04

    Diese Faltung kannst du aber in 2 einfachere Faltungen "aufspalten". Du kannst dein Array erst mit folgendem Faltungskern falten:

    0.2  0.2  0.2  0.2  0.2

    und dann mit folgendem:

    0.2
0.2
0.2
0.2
0.2

    Damit hast du dann die Zeitdauer auf etwa 10/25 verringert. Aber so weit und sogar noch weiter war Volkard ja auch schon.

    1. Wenn du das so gemeint hast, dann brauchst du aber natürlich keine Faltung, sondern einen Algorithmus, der Zusammenhangskomponenten findet. ...und vielleicht einen Algorithmus, der dir automatisch einen Schwellenwert generiert. (Soll das automatisch laufen, oder willst du einen vorgeben?)

    Ich kann dir für beides Code in Java zeigen, der ist aber nicht sehr schön, wie ich gerade gesehen habe. Ist ne ziemlich lange Methode. 😕

    0
  • J

    Die Blöcke dürfen auch unförmig sein? Aber zusammenhängend sollen sie doch schon bleiben, oder?

    Versteh ich das jetzt richtig?
    Du hast so ein riesiges Feld und willst zusammenhängende Bereiche finden, bei denen der Wert jedes Feldes einen gewissen Mindestwert hat? Das ist viel leichter als Rechtecke drüberzulegen! Weil bei Rechtecken kann man sich auch ungünstige Felder einfangen, die kann man hier aber einfach weglassen.

    Also falls ich das so richtig verstanden hab würd ich's so machen:

    Links oben anfangen und rechts unten aufhören, von jedem Punkt aus das Gebiet bestimmen (zu kleine Felder sind nach einem Schritt aussortiert), dabei trägste in ein zweites Feld immer ein, ob ein bestimmtes Feld schon benutzt wurde oder nicht. Nebenbei erstellste eine Liste mit diesen Gebieten (einfach die Koordinaten anhängen). Ein bißchen optimieren kann man noch, zum Beispiel könnte man nur jedes zweite Feld überhaupt als Anfangsfeld benutzen...
    Das ändert aber nix dran, daß Du bei O(n^2) rauskommst. Das ist für eine solche Problemstellung aber auch klar, da Du ja n^2 Felder hast und wohl jedes mal anschauen mußt. Ne exakte Lösung wirst Du also schneller nicht finden können. (Was die Komplexität angeht). An Speicher und konstanten Faktoren kannste natürlich noch arbeiten. Zum Speichern der verwendeten Felder reicht ja zum Beispiel ein Feld aus bools und sowas.

    MfG Jester

    0
Anmelden zum Antworten