Punkteverteilung im Raum < Sonstiges < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich stehe momentan vor einem geometrischen Problem. Sagen wir, es sei ein abgegrenzter zweidimensionaler Raum gegeben (x [-1,1]; y [-1,1]). In diesem Raum soll nun eine Anzahl von n-Punkten so verteilt werden, dass die Summe der Abstände der Punkte zueinander maximal ist.
Ein Beispiel soll mein Problem verdeutlichen: Im gegeben Raum ist die Summe der Abstände von n=4 Punkten maximal, wenn diese in den Ecken des Raums liegen (dies erklärt sich mir bislang rein intutiv). Für n=5 Punkte wird die Summe der Abstände dann maximal, wenn der 5. Punkt in der Mitte des Raums (0/0) liegt.
Meine Frage lautet: Existiert eine Software, Formel oder möglichweise ein Algorithmus, welche/r mir berechnet, wo eine beliebige Anzahl von Punkten im begrenzten Raum zu liegen haben, damit der summierte Abstand maximal wird?
Ich habe bereits selber versucht dieses Problem zu lösen. Ich meine ein Verteilungsmuster zu erkennen, welches sich wiederholt. Ab n=16 wird es jedoch zunehmend kompliziert und rechenaufwendig.
Über Hilfe oder einen Hinweis würde ich mich freuen.
Gruss,
Boris
PS: "Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt."
|
|
| |
|
Bist du dir sicher, was n=5 angeht? Wenn ich das richtig sehe, dann kommen zu den 4 Seiten des Quadrats die beiden Diagonalen hinzu, wenn ich den 5. Punkt in die Mitte lege. Lege ich ihn aber in eine der Ecken, dann kommen 1 Diagonale und 2 Seiten dazu - und das ist in der Summe mehr!
Allgemein betrachtet, suchst du eine Lösung für ein Polynom zweiten Grades in 2(n-1) Unbekannten (pro Punkt 2 Variablen, 1 Punkt kannst du oBdA in eine Ecke legen), mit der Nebenbedingung, dass nur ein bestimmter Wertebereich zugelassen ist. Man könnte die Gleichung aufstellen, ableiten und den Gradient gleich 0 setzen.
Der Einfachheit halber würde ich aber im Gebiet [0, 1]x[0, 1] arbeiten, mit [mm] P_1=(0, [/mm] 0).
Beispiel für n=2, [mm] P_2=(x, [/mm] y): Maximiere [mm]f[/mm] mit
[mm]f(x, y)=(x-0)^2 + (y-0)^2[/mm]
[mm]grad f = (2x, 2y)[/mm]
Offensichtlich findet man mit [mm]grad f =0[/mm] nur das Minimum bei (0, 0).
Versuchen wir es mit n=3 und setzen [mm] P_i=(x_i, y_i):
[/mm]
[mm]f(x_2, y_2, x_3, y_3)=x_2^2 + y_2^2 + x_3^2 + y_3^2 + (x_2 - x_3)^2 + (y_2 - y_3)^2[/mm]
[mm]grad f = (4x_2 - 2x_3, 4y_2 - 2y_3, 4x_3 - 2x_2, 4y_3 - 2y_2)[/mm]
Auch hier findet man mit [mm]grad f =0[/mm] nur das Minimum bei (0, 0).
Muss man also noch mal darüber nachdenken.
|
|
|
| |
|
> Bist du dir sicher, was n=5 angeht? Wenn ich das richtig
> sehe, dann kommen zu den 4 Seiten des Quadrats die beiden
> Diagonalen hinzu, wenn ich den 5. Punkt in die Mitte lege.
> Lege ich ihn aber in eine der Ecken, dann kommen 1
> Diagonale und 2 Seiten dazu - und das ist in der Summe
> mehr!
Da gebe ich Dir Recht.
Ich habe es bereits ebenso mit dem Bilden des Gradienten versucht. Auch ich bin erstmal von n=2 ausgegangen und habe im Koordinatensystem (0;1) den ersten Punk auf (0/0) gelegt.
Ich habe erhalten:
grad f = ( 2x * 0,5 (x² + [mm] y²)^{-0,5},2y [/mm] * 0,5 (x² + [mm] y²)^{-0,5})
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Fr 05.12.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:20 Mi 03.12.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
