Algorithmus gesucht...

WebFritzi

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.

WebFritzi

[Blödsinn]

volkard

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.

WebFritzi

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!

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

Gregor

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.

Jester

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

AdHa

Hallo zusammen,

@Gregor:
Danke für die Erklärung und Formel zu 'Faltung'.
Tatsächlich ist es nicht wirklich das, was ich suche,
allerdings muß ich zugeben, das ich den Tip in einer alternativen Version berücksichtigt habe, zumal die Inplementation sehr einfach war
und meine erste kleine Demo sehr speicher- und zeitsparend ist.
Ich wäre allerdings auch an dem Java-Code interessiert,
könntest Du ihn mir bitte zusenden?
(1. Vielleicht kann man da noch einiges an 'mehr Power' rausholen...
2. Ich bin mittlerweile Mitglied, meine EMail-Adresse ist also hinterlegt...)

@Jester:

Aber zusammenhängend sollen sie doch schon bleiben, oder?

Nicht notwendigerweise!

@All:
Ersteinmal Danke-schön für die vielen Tips und Anregungen.
Da meine erste Ausführung zu Abstrakt war, möchte ich die Anwendung ein bischen erklären...

Ich habe den Grundriß eines Hauses, präziser: einer Etage.
Nun kann es sein, daß eine Personen sich in einem der Räume befindet oder bewegt.
Diesen Ort gilt es zu lokalisieren.

Ich bekomme von einem Server die Wahrscheinlichkeitswerte in Form eines
1000x1000 Feldes.
D.h. überall dort wo Wände sind, ist die Wahrscheinlichkeit 0%,
und da sich die Mauern nicht bewegen werde ich in dieser Karte viele feste 0% Werte haben.
Nun habe ich "nur" noch Räume, in denen sich eine Person aufhalten kann.
Und da die Wahrscheinlichkeitswerte VORAUSSSAGEN des Servers sind,
wo sich eine Person befindet oder befinden kann, besteht die Möglichkeit,
daß ich in diesem Grundriß mehrere "Flecken" mit hoher Wahrscheinlichkeit.

Und diesen Mittelpunkt der Flecken geht es zu errechnen. (Obwohl dies das einfachste ist: diese Bereiche/Formen/Flecken zu bilden ist schwer...)

Grüße
Adrian

Gregor

Ich habe dich gewarnt: Es ist ganz ganz mieser Code!

...Zusammenhangskomponenten...

package image;

import java.util.*;

import image.valueSeparator.ValueSeparator;
import image.regionVerifier.RegionVerifier;
import plugin.SimpleThreadableProcess;

public final strictfp class ComponentCreator extends SimpleThreadableProcess
{
   private ValueSeparator separator;
   private RegionVerifier verifier;
   private static final int [][] neighbors = {{-1,-1},{-1,0},{-1,1},{0,-1}};

   public ComponentCreator (ValueSeparator separator, RegionVerifier verifier)
   {
      super ("Komponenten finden");
      this.separator = separator;
      this.verifier = verifier;
      setProcessNumber(5);
   }

   public final int [][] getComponents (final int [][] values)
   {
      final int width = values.length;
      final int height = values[0].length;
      final int [][] tempArray = new int [width][height];
      final int [][] outArray = new int [width][height];
      setEndValue(width);
      setCurrentProcess(1);
      for (int x = 0 ; x < width ; ++x)
      {
         setCurrentValue (x);
         for (int y = 0 ; y < height ; ++y)
         {
            tempArray [x][y] = separator.getComponent (values[x][y]);
            outArray [x][y] = -1;
         }
      }
      final Hashtable assoziation = new Hashtable (300);

      int regionNumber = 0;
      final int [] neighborAssoziation = new int [4];
      setCurrentProcess (2);
      for (int x = 0 ; x < width ; ++x)
      {
         setCurrentValue (x);
         for (int y = 0 ; y < height ; ++y)
         {
            if (tempArray [x][y] == -1)
            {
               outArray [x][y] = -1;
            }
            else
            {
               for (int i = 0 ; i < 4 ; ++i)
               {
                  final int currentX = x + neighbors[i][0];
                  final int currentY = y + neighbors[i][1];
                  if ((currentX >= 0) && (currentY >= 0) && (currentY < height) &&
                      (tempArray [currentX][currentY] == tempArray [x][y]))
                  {
                     neighborAssoziation [i] = ((Integer)assoziation.get(
                                               new Integer (outArray[currentX][currentY]))).intValue ();
                  }
                  else
                  {
                     neighborAssoziation [i] = Integer.MAX_VALUE;
                  }
               }
               Arrays.sort(neighborAssoziation);
               if (neighborAssoziation [0] == Integer.MAX_VALUE)
               {
                  outArray [x][y] = regionNumber;
                  assoziation.put(new Integer (regionNumber), new Integer (regionNumber));
                  ++regionNumber;
               }
               else
               {
                  outArray [x][y] = neighborAssoziation [0];
                  for (int i = 0 ; i < 4 ; ++i)
                  {
                     final int currentX = x + neighbors[i][0];
                     final int currentY = y + neighbors[i][1];
                     if ((currentX >= 0) && (currentY >= 0) && (currentY < height) &&
                         (tempArray [currentX][currentY] == tempArray [x][y]))
                     {
                        assoziation.put (new Integer (outArray [currentX][currentY]),
                                         new Integer (neighborAssoziation [0]));
                     }
                  }
               }
            }
         }
      }
      int currentAssoziation, newAssoziation;
      int maxRegion = 0;
      setCurrentProcess (3);
      setEndValue (regionNumber);
      for (int i = 0 ; i < regionNumber ; ++i)
      {
         setCurrentValue (i);
         currentAssoziation = i;
         newAssoziation = ((Integer)assoziation.get(new Integer (i))).intValue ();
         while (currentAssoziation != newAssoziation)
         {
            currentAssoziation = newAssoziation;
            newAssoziation = ((Integer)assoziation.get(new Integer (currentAssoziation))).intValue ();
         }
         if (currentAssoziation > maxRegion) maxRegion = currentAssoziation;
         assoziation.put (new Integer (i),new Integer (currentAssoziation));
      }
      setCurrentProcess (4);
      setEndValue (width);
      verifier.init(maxRegion+1);
      for (int x = 0 ; x < width ; ++x)
      {
         setCurrentValue (x);
         for (int y = 0 ; y < height ; ++y)
         {
            if (outArray[x][y] != -1)
            {
               outArray[x][y] = ((Integer)assoziation.get(new Integer (outArray[x][y]))).intValue ();
               verifier.add(values[x][y],outArray[x][y]);
            }
         }
      }
      final int [] newRegionNumbers = verifier.getNewRegionNumbers ();
      setCurrentProcess (5);
      for (int x = 0 ; x < width ; ++x)
      {
         setCurrentValue (x);
         for (int y = 0 ; y < height ; ++y)
         {
            if (outArray[x][y] != -1)
            {
               outArray [x][y] = newRegionNumbers[outArray [x][y]];
            }
         }
      }
      return outArray;
   }
}

Hierbei gibt der "ValueSeparator" darüber Auskunft, ob ein Punkt nun dazugehört oder nicht. Wenn der Punkt nicht zu einem gesuchten Bereich gehört, gibt der ValueSeparator bei "getComponent" -1 zurück. Ansonsten einen positiven Wert. Da du keine dazugehörigen Bereiche unterscheidest sollte dann also immer 0 zurückgegeben werden.

Der RegionVerifier überprüft am Schluss, ob die einzelnen Regionen auch noch bestimmte zusätzliche Eigenschaften erfüllen, z.B. mehr als eine bestimmte Anzahl von Punkten beinhalten, wenn nicht, wird die betreffende Region aussortiert.

Man kriegt insgesamt ein zweidimensionales Array zurück, welches die gleiche Größe wie das Eingabearray hat und für jede zusammenhängende Komponente einen anderen Wert anzeigt. Wenn ein Punkt zu keiner Zusammenhangskomponente gehört, ist sein Wert -1.

volkard

AdHa schrieb:

Nun habe ich "nur" noch Räume, in denen sich eine Person aufhalten kann.
Und da die Wahrscheinlichkeitswerte VORAUSSSAGEN des Servers sind,
wo sich eine Person befindet oder befinden kann, besteht die Möglichkeit,
daß ich in diesem Grundriß mehrere "Flecken" mit hoher Wahrscheinlichkeit.
Und diesen Mittelpunkt der Flecken geht es zu errechnen. (Obwohl dies das einfachste ist: diese Bereiche/Formen/Flecken zu bilden ist schwer...)

bleibt unscharf.
also nehmen wir mal an, der rechner hätte über ein jahr lang jede minute einmal gemessen, wo der mensch in der wohnung ist und im entsprechende feld inkrementiert. von diesem feld gehe ich dann mal aus.
annahme: er war am zu 30% im bett (unruhiger schläfer, daher ganzes bett genutzt, 120x220. er war zu 20% in seinem fernsehsessel (im ohrensessel gefangen und aufrechter, 40x120).

und jetzt fehlt da ne zielfunktion. will ich ne bombe werfen, die im umkreis von 20cm lethal wirkt, dann hab ich auf dem fehnsehsessel wohl ne deitlich höhere siegwahrscheinlichkeit. ne dickere, mindestens die, die das ganze bett abdecken kann, wirkt aber im bett besser, nämlich zu 30% und auf den fernsehsessel könnte sie nur mit 20% gewinnen.

Du weißt also nicht, was "Und diesen Mittelpunkt der Flecken geht es zu errechnen." bedeutet. Finde mal raus, was du willst. Oder sag, was Du mit den Werten dann anfangen willst. Bisher haste nur verraten, woher sie kommen, also nix wichtiges.

Übrigens wäre es hier schlecht, auf den Warscheinlichkeitsschwerpunkt oder sonst irgend einen Mittelwert zu werfen, solange die Bombe nicht beide Orte vom Schwerpunkt aus ereichen kann.