Durchschnittlicher Abstand zum nächstgelegenen Punkt |
14.12.2005, 17:58 | well | Auf diesen Beitrag antworten » | ||||||||||
Durchschnittlicher Abstand zum nächstgelegenen Punkt ich habe einen Kreis mit n Punkten, die im Kreis gleichverteilt sind. Nennen wir die Punkte Adressen. Die mittlere Entfernung zwischen zwei Adressen ist: r ist der Kreisradius. Ausgerechnet wurde dies von Arthur Dent in diesem thread. Frage: Wenn nach dem Zufallsprinzip drei Adressen gezogen werden, wie ist mittlere Entfernung der erstgezogenen Adresse zu der jeweils nächstgelegenen Adresse aus zweit- und drittgezogener Adresse. Klingt sehr theoretisch; ich mache mal einen praktischen Anwendungsfall daraus (mit starren idealisierten Rahmenbedingungen). Es gibt eine Stadt, deren Fläche ein Kreis mit dem Radius r ist und gleichverteilt über den Kreis gibt es Adressen. In der Stadt gibt es einen Taxifahrer, der sobald er einen Auftrag ausgeführt hat zwischen zwei zwischenzeitlich eingegangenen neuen Aufträgen wählen kann. Er nimmt immer den Auftrag mit der nächstgelegenen Adresse. Wie weit ist durchschnittlich die Anfahrtstrecke zu dieser nächstgelegenen Adresse (als Luftlinie, geometrisch gesprochen als Gerade). Zur Verdeutlichung: Gäbe es für den Taxifahrer keine Auswahl zwischen zwei Adresse, sondern nur eine Adresse, die er anfahren muss, so wäre die Anfahrtstrecke für ihn (siehe Formel und Link oben): Ich habe schon -vergebens - verschiedene Ansätze probiert, will diese hier zu Beginn des Threads nicht sofort darstellen, weil das verwirren könnte. Ich erwarte auch nicht unbedingt den großen Lösungswurf, sondern bin auch für jede Lösungsfährte und jeden Ansatz dankbar. :-) |
||||||||||||
14.12.2005, 19:02 | AD | Auf diesen Beitrag antworten » | ||||||||||
Ehrlich, das wird in exakter Rechnung der reinste Horror. Da kommen zu dem oben noch zwei Integrale in der Schachtelung hinzu, also ein Fünffachintegral (!). Hier ist wohl der Zeitpunkt gekommen, das eher über Monte-Carlo-Simulation auszurechnen, das spart Zeit und Nerven. Und ist überdies exakter als (wie gesehen) unzulässige Annahmen wie "Adressen auf Kreislinie mit mittleren Mittelpunktabstand". |
||||||||||||
14.12.2005, 20:10 | well | Auf diesen Beitrag antworten » | ||||||||||
Vielen Dank Arthur!!! "Monte-Carlo-Simulation". Nie gehört ... Der Begriff gefällt mir. :-) O.K., meine Monte-Carlo-Simulation sieht so aus: Excel genutzt. Spalten angelegt: - Startpunkt - Zielpunkt 1 - Zielpunkt 2 Zufallszahlen zwischen 0 und 100 für jeden der drei Punkte. Spalten, die berechnen: - Differenz zw. Start- und Zielpunkt 1 - Differenz zw. Start- und Zielpunkt 2 Spalte mit: - Minimum aus "Differenz zw. Start- und Zielpunkt 1" und "Differenz zw. Start- und Zielpunkt 1" 10.000 mal diese Konstellation gerechnet (natürlich mit wechselnden Zufallszahlen). Mittelwerte berechnet für: - Differenzen zw. Start- und Zielpunkt 1 - die Minimums (aus "Differenz zw. Start- und Zielpunkt 1" und "Differenz zw. Start- und Zielpunkt 1") Ergebnis: Mittelwert für Differenz zw. Start- und Zielpunkt 1 beträgt 33,7 Mittelwert der Minimums ist 21,2 Das Verhältnis von 21,2 zu 33,7 beträgt 63%. Das bedeutet, dass die Strecke zum nächstgelegenen Zielpunkt bei zwei Zielpunkten nur 63% der Länge hat, wie der Abstand, wenn nur ein Zielpunkt vorgegeben ist. Ich habe bei der Gelegenheit gleich simuliert, wieviel Strecke man sich einspart bei 3, 4, ... bis 10 Zielpunkten. Bezogen auf 100 % Strecke bei einem Zielpunkt sehen die Ergebnisse für die Strecke zum nächstgelegenen Zielpunkt so aus: - 2 Zielpunkte: 63 % - 3 Zielpunkte: 45 % - 4 Zielpunkte: 35 % - 5 Zielpunkte: 29 % - 6 Zielpunkte: 24 % - 7 Zielpunkte: 21 % - 8 Zielpunkte: 18 % - 9 Zielpunkte: 16 % - 10 Zielpunkte: 15 % Ich kann gerne erklären, warum ich so vorgegangen bin. Will es nicht gleich hier darlegen, um den Beitrag nicht weiter zu sprengen. Ich erhoffe mir aber kritische Frage, die mich dazu zwingen. ;-) Eins fällt glaube ich gleich ins Auge. Ich bin nämlich der Ansicht, dass es für die Ermittlung der relativen Streckenabweichungen keine Rolle spielt, ob die Fläche ein Kreis, ein Rechteck, ein Dreieck oder sonst was ist. Ich hoffe ich liege damit nicht daneben. |
||||||||||||
14.12.2005, 21:07 | AD | Auf diesen Beitrag antworten » | ||||||||||
Mit modernen Rechnern nimmt man aber ein paar mehr als nur 10000 Simulationen. Hier mal mein schnell programmiertes Ergebnis deines Problems: Jeweils drei gleichverteilte Punkte im Einheitskreis, und dann Minimum von 1-2, 1-3 erfasst Insgesamt habe ich das 1000 x 1000000 = 1 Milliarde mal wiederholt, dabei aus jeweils 1 Million Werte einen Mittelwert gebildet und diese 1000 Mittelwerte statistisch analysiert, um den Simulationsfehler abschätzen zu können. Hier die Resultate:
Ach ja: Ich komme somit auf . Das weicht beträchtlich von deinen 63% ab - hast du wirklich gleichverteilte Punkte im Kreis simuliert? |
||||||||||||
14.12.2005, 21:13 | well | Auf diesen Beitrag antworten » | ||||||||||
Sind die 0,90543 die durchschnittliche Strecke bei einem Radius r=1? Also das amtliche Endergebnis für das, was bisher in der Formel gekleidet war? Und 0,67670 ist die Strecke, wenn von zwei Zielpunkten der nächstgelegene genommen wird? Das wären 74,7 % der Strecke im Vergleich zur Strecke bei einem Zielpunkt. Und ich habe 63 % rausgekriegt. Wo liegt der Denkfehler bei meinem Lösungsweg? |
||||||||||||
14.12.2005, 21:13 | AD | Auf diesen Beitrag antworten » | ||||||||||
Verschoben Angefangen hat's mit Geometrie, aber jetzt ist es doch eher Stochastik. |
||||||||||||
Anzeige | ||||||||||||
|
||||||||||||
14.12.2005, 21:15 | well | Auf diesen Beitrag antworten » | ||||||||||
|
||||||||||||
14.12.2005, 21:31 | AD | Auf diesen Beitrag antworten » | ||||||||||
|
||||||||||||
14.12.2005, 21:45 | well | Auf diesen Beitrag antworten » | ||||||||||
Ich habe gleichverteilte Abstände simuliert. Wie hast Du operiert? |
||||||||||||
14.12.2005, 21:53 | AD | Auf diesen Beitrag antworten » | ||||||||||
Wo? Auf der Strecke, im Quadrat, im Kreis...
Na wie ich hier erläutert habe:
Simuliert wird also der zufällige Abstand vom Mittelpunkt gemäß dieser Verteilungsfunktion mit Inversionsmethode. Dazu noch ein im Vollkreis gleichverteilter Winkel. Das jeweils für jeden Punkt (also bis zu 11 Punkte pro Einzelsimulation, wenn man das Minimum von bis zu 10 Abständen ermitteln will). |
||||||||||||
14.12.2005, 22:08 | well | Auf diesen Beitrag antworten » | ||||||||||
Na ja, wie ich schon sagte:
|
||||||||||||
14.12.2005, 22:16 | AD | Auf diesen Beitrag antworten » | ||||||||||
Doch, damit liegst du daneben. Quantitativ kann ich das aber nicht beurteilen, müsste man durch entsprechende Simulationen mal vergleichen. Jetzt erstmal die Ergebnisse für bis zu 10 Adressen gleichverteilt im Kreis (diesmal nur 100 Millionen Durchläufe):
EDIT: Und hier mal eine kleine Formabhängigkeitsuntersuchung der relativen Abstände:
Wie ersichtlich, gibt es zwischen Kreis und Quadrat kaum Unterschiede, jedenfalls nicht im Rahmen der Genauigkeit dieser Simulation. Bei nichtquadratischen Rechtecken (hier 1:3 und 1:10) sieht man dann aber schon immer größere Abweichungen. Und wenn ich mir die letzte Spalte so ansehe, dann weiß ich auch wie du simuliert hast: nur eindimensional Das kann man nun aber auch wieder theoretisch ausrechnen, mit etwas Mühe. |
||||||||||||
14.12.2005, 23:00 | well | Auf diesen Beitrag antworten » | ||||||||||
Ups, da habe ich also die Strecken auf der Linie simuliert,... Danke für die Aufklärung und die Simulationen für verschiedene Flächen. Hm, ...., kann es sein, dass meine Annahme - neben der Linie - auch gelten würde, wenn die Fläche unendlich ist? In Excel würde ich lange rum machen müssen, um eine kritische Anzahl von Simulationen hinzukriegen. Wenn ich trotzdem mal rum simulieren will, müsste ich dann diese Formel von Dir nehmen und mir per Zufallsgenerator für und Variable zwischen 0 und 1 und für den cos Werte zwischen 0 und 180 Grad geben lassen? |
||||||||||||
14.12.2005, 23:12 | AD | Auf diesen Beitrag antworten » | ||||||||||
Richtig.
So einfach ist es nicht: Ich hatte doch oben schon geschrieben, wie es geht:
Im Endeffekt bedeutet das für in Excel für diesen Mittelpunktsabstand: =WURZEL(ZUFALLSZAHL())
Das ist wieder richtig. Aber Obacht: Exel rechnet bei Winkelfunktionen gewöhnlich im Bogenmaß! |
||||||||||||
14.12.2005, 23:27 | well | Auf diesen Beitrag antworten » | ||||||||||
Herzlichen Dank Arthur, wenn es solche Menschen wie Dich nicht gäbe, wäre ich ein wenig dümmer geblieben und hätte einen haufen Zeit verloren. Morgen werde ich gemäß Deinen Vorgaben in Excel rumsimulieren. Jetzt gehe ich Ähm, nur interessehalber: Kann es Deiner Ansicht nach stimmen, dass mein Vorgehen für die relativen Streckenabweichungen nicht nur für die Linie, sondern auch für eine unendliche Fläche Geltung hat? |
||||||||||||
14.12.2005, 23:41 | AD | Auf diesen Beitrag antworten » | ||||||||||
Ich muss meine vorschnell geäußerte Meinung revidieren: Im unendlichen könntest du tatsächlich recht haben mit den Werten von der Linie. Allerdings muss da erstmal das Problem genau definiert werden, denn eine Gleichverteilung in der unendlichen Ebene gibt es nicht. Für die dich interessierenden Abstandsverhältnisse gibt es da aber ein Ersatzmodell, was dem von dir gewünschten Sachverhalt entspricht. Aber das dann erst morgen... |
||||||||||||
15.12.2005, 10:09 | AD | Auf diesen Beitrag antworten » | ||||||||||
Ok, zum Problem der "Gleichverteilung" in der unendlichen Ebene. Wie oben erwähnt, gibt es die eigentlich nicht. Was du machen kannst, ist die Betrachtung eines Poisson-Punktprozesses in der Ebene. Viel bekannter ist der eindimensionale Poissonprozess , wo der Parameter in der Regel die eindimensionale Zeit darstellt (siehe z.B. Wikipedia-Beitrag). Hier meine ich aber wie gesagt den in der Ebene, oder allgemeiner im (Suchbegriff "spatial poisson process"). Der ist charakterisiert durch folgende Eigenschaften
Dieses Modell hier für die Ebene (also n=2) angesetzt, lässt sich die Verteilungsfunktion des Abstand eines Punktes zum nächsten Nachbarn einfach berechnen: Dabei ist die n-dimensionale Kugel um den Ursprung mit Radius , im zweidimensionalen einfach ein Kreis mit Flächeninhalt . Dann lässt sich auch der mittlere Abstand bestimmen: Das Minimum von Abständen entspricht dann der -fachen Intensität des Poisson-Prozesses, d.h., . Hier ergibt sich für das Verhältnis der mittleren Abstände dann ganz einfach , also hinsichtlich der obigen Listen dann
|
||||||||||||
15.12.2005, 11:45 | well | Auf diesen Beitrag antworten » | ||||||||||
Guten Morgen Arthur, das mit dem Abstand in der unendlichen Ebene ist interessant. Intiutiv und unmathematisch ausgedrückt würde ich sagen, dass es gerechnet wird ein "Kreis ohne äußeren Rand" (bzw. "unendlicher Kreis"). Die mittlere Entfernung beim "unendlichen Kreis" ist deshalb kleiner als beim Kreis, weil beim Kreis für Startpunkte, die im Randgebiet liegen, Zielpunkte ausserhalb dem Randgebiet nicht da sind, mit der Konsequenz, dass weitentfernte Zielpunkte weniger häufig vorkommen als bei dem "unendlichen Kreis". Klingt möglicherweise seltsam, aber ich kann mich nicht gut mathematisch klar ausdrücken. :-/ Ich habe heute morgen in Excel mit Hilfe Deiner Vorgaben simuliert. Bei einem Ziel stimmt meine mittlere Strecke mit Deinem Simulationsergebnis überein, bei 2 und mehr Zielen jedoch leider nicht. Irgendwo muss ich bei meinem Vorgehen einen Denkfehler drinhaben. Ich erklär meine Schritte mal anhand einer einzelnen Simulation bei 3 Zielpunkten (x2, x3 und x4 sind die Zielpunkte; der Startpunkt heißt x1): Folgende Zahlen simulierte ich mit dem Zufallsgenerator: - =157,9 - r für x1 = 0,61 - r für x2 = 0,15 - r für x3 = 0,07 - r für x4 = 0,44 Die Wurzel daraus ist jeweils: - x1 = 0,78 - x2 = 0,38 - x3 = 0,27 - x4 = 0,66 Mit der Formel kriege ich den Abstand zwischen x1 und x2. Die Formel nutze ich genauso für die Abstandsermittlung zwischen x1 und x3 sowie zwischen x1 und x4. Ich erhalte - Strecke x1 nach x2: 1,15 - Strecke x1 nach x3: 1,04 - Strecke x1 nach x4: 1,42 Ergebnis: Die minimale Enfernung besteht zwischen x1 und x3, nämlich 1,04*r. 1000 mal habe ich so simuliert und den Mittelwert gebildet: Er beträgt 0,76*r (für den nächstgelegenen Zielpunkt bei 3 Zielpunkten). Bei einem Zielpunkt komme ich auf 0,8955, also sehr nahe an Deinem Simulationsergebnis. Bei den anderen Simulationsergebnisse liege ich jedoch weit daneben: - 2 Zielpunkte: 0,80 - 3 Zielpunkte: 0,76 - 4 Zielpunkte: 0,73 - 5 Zielpunkte: 0,71 - 6 Zielpunkte: 0,69 - 7 Zielpunkte: 0,68 Wo steckt bei mir der Wurm drin? :-( Dann noch eine Bitte: Kannst Du Deine Höllenmaschine anwerfen, und auch die Ergebnisse für 11 bis 20 Zielpunkte ausspucken lassen? |
||||||||||||
15.12.2005, 11:48 | AD | Auf diesen Beitrag antworten » | ||||||||||
Wenn du drei Entfernungen 1-2, 1-3, 1-4 berechnest, brauchst du auch drei alphas, und nicht nur eins. Sonst liegen die drei Punkte 2, 3 und 4 auf einer Linie mit dem Mittelpunkt, und das ist ja keine allgemeine Lage! EDIT: Das ist keine Höllenmaschine, sondern ein schnöder Athlon-XP 2600+. Aber eben kompilierte C-Software, und da schafft man pro Sekunde zig-Millionen Schleifen.
|
||||||||||||
15.12.2005, 12:48 | well | Auf diesen Beitrag antworten » | ||||||||||
Jaaaa, jetzt bin ich mit meiner Simulation nah an Deinen Ergebissen. Ich wäre wahrscheinlich nie darauf gestossen, dass der Wurm an den Alphas liegt. Vielen Dank dafür, für die weiteren Sim-Ergebnisse und noch mal für alles andere Hilf- u. Lehrreiche!!!! |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|