3. Algorithmus gesucht...

Algorithmus gesucht...

  • ?

    Hallo zusammen,

    ich habe ein Problem gegeben und suche nun einen geeigneten Algorithmus,
    zumal meine herangehensweise bischen zeitaufwendig und speicherlastig ist...
    Vielleicht kennt der eine oder andere von Euch einen passenden Algorithmus...

    Es geht um folgendes: ich habe ein zwei dimensionales Feld der Größe 100 x 100,
    das Prozentzahlen in jeder Zelle beinhaltet. Diese geben die Wahrscheinlichkeit
    an, mit welcher sich ein Objekt mit beliebiger Größe (sagen wir 5 x 5 Zellen groß) befinden kann. Ich möchte nun 'Bereiche' mit der größten Wahrscheinlichkeit erkennen bzw. markieren um dann den Mittelpunkt dieses Bereichs zu bestimmen (nicht notwendigerweise die höchste Prozentzahl).

    Wie bereits gesagt sind meine Algorithmen eine naive Umsetzung dessen,
    was ich tun würde, wenn ich voraussagen sollte wo sich ein Objekt mit höchster Wahrscheinlichkeit bedindet. Allerdings sind diese nicht sehr effizient.

    Wie bereits gesagt kennt vielleicht jemand von Euch geeignete Algorithmen,
    oder weiß wo ich fündig werden könnte!?
    Ich würde mich freuen, wenn ich Anregungen und Tipps von Euch hören würde.
    (Es gibt mit Sicherheit 😉 Algorithmen in der Topologie/KI/Computergrafik,
    allerdings ist es sher mühsam die richtigen zu finden...)

    Danke schön und Grüße
    Adrian

    0
  • J

    Hab mal in Programming-Pearls von Bentley sowas ähnliches gelesen, da ging es um ein Zellraster mit Zahlen und darum ein Rechteck mit möglichst großer Summe zu finden. Aber das war ziemlich heftig. Auf so ein Problem würde ich glaub im Zweifelsfall eher mit Optimierung losgehen, als mit nem "richtigen" Algorithmus.

    Aber vielleicht findest Du ja auch was dolles!

    0
  • G

    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?

    0
  • ?

    Ist das nicht simpel, oder habe ich was verkehrt verstanden?!?
    In Deinem 100x100-Feld gibt es 96² = 9216 5x5-Bereiche. Die klapperst Du alle der Reihe nach ab, wobei Du jedesmal die Summe aller 25 Prozentzahlen bildest. Der wahrscheinlichste Bereich hat die höchste Summe.

    0
  • C

    In der c´t war mal ein Artikel über ein Würfelpuzzel, wozu es auch einen Programmierwettbewerb gab. Vielleicht kannst Du ja einige Ansätze auf 2D übertragen.
    Den ersten Artikel findest Du hier. Die Auflösung des Programmierwettbewerbs (Programmierwettbewerb: Die schnellsten c't-Puzzler, S. 92 ) habe ich nicht auf den heise-Server entdecken können.

    PS: AFAIR gab´s auch ein Forum auf dem heise-Server für den Wettbewerb.

    0
  • G

    Kroe schrieb:

    Ist das nicht simpel, oder habe ich was verkehrt verstanden?!?
    In Deinem 100x100-Feld gibt es 96² = 9216 5x5-Bereiche. Die klapperst Du alle der Reihe nach ab, wobei Du jedesmal die Summe aller 25 Prozentzahlen bildest. Der wahrscheinlichste Bereich hat die höchste Summe.

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

    Ich glaube aber, das war anders gemeint.

    0
  • V

    Kroe schrieb:

    Ist das nicht simpel, oder habe ich was verkehrt verstanden?!?
    In Deinem 100x100-Feld gibt es 96² = 9216 5x5-Bereiche. Die klapperst Du alle der Reihe nach ab, wobei Du jedesmal die Summe aller 25 Prozentzahlen bildest. Der wahrscheinlichste Bereich hat die höchste Summe.

    gut.
    und jetzt noch das abklapern bis 25 beschleunigen, damit nicht 96^2*25 lesungen nötig sind.
    ich bau mir erstmal ein array mit den 96 summen der obersten reihe.
    dann bau ich mir ein array mit 96 spaltenmaxima.
    dann geh ich zeile für zeile tiefer, wobei ich jedesmal für jedes quadrat dir 5 unteren neuen zahlen draufaddiere und die 5 oberen wegfallenden subtrahiere.
    und vergleiche mit dem maximum und setz das ggf neu.
    hmm, macht nur noch 10 lesungen statt 25. ist scheiße.

    also erstmal die tabelle vorbereiten und über jede zeile laufen und aus jeweils 5 zahlen ein 5er-summe machen. aufwand ca 100^2 lesungen. dann idee von oben nehmen, wieder ca 100^2 lesungen. jo, damit könnt ich leben.

    0
  • 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
Anmelden zum Antworten