Noch ein mathematisches Problem

Hallo Leute,

ich habe mal wieder ein mathematisches Problemchen...


Folgende Situation:
Ich habe eine Menge von n Punkten in einem dreidimensionalen Raum, welche sich an bestimmten (jedoch unbekannten) Positionen anhäufen. Sie bilden also eine Anzahl von m Gruppen (m ist bekannt), irgendwo in diesem dreidimensionalen Raum. Jede Gruppe muss dabei aus mindestens k_min und höchstens k_max Punkten bestehen.

Was ich brauche ist ein Algorithmus mit dem ich bestimmen kann welcher Punkt zu welcher Gruppe gehört.

Momentan suche ich speziell eine Lösung für n=9, m=4, k_min=2 und k_max=3, aber eine allgemeine Lösung wäre mir natürlich lieber (ich halte es eh für unwahrscheinlich, daß es ausgerechnet für diese Werte eine Lösung gibt die ganz besonders einfach ist).


Ich weiß, daß ein derartiges Problem geradezu nach einem Neuronalen Netz schreit, aber darauf würde ich in diesem Fall gerne verzichten.

Nehme an, die Position einer Gruppe ist durch ein x, y, z gegeben. Aber das mußt du ja auch erstmal haben ?
Die Einschränkung auf k_max versteh ich nicht. Da gibt es ja dann (überzählige) Punkte, die "Waisenkinder" sind ?

Tja, die Positionen der Gruppen sind unbekannt, aber im wesentlichen genau das was ich am Ende als Ergebnis brauche (also die Zentren jeder Gruppe, welche sich durch den Schwerpunkt aller zugehörigen Punkte ergeben).

Um diese Ergebnisse zu erhalten muss ich also wissen, welche Punkte zu welcher Gruppe gehören.


Was k_max betrifft, das ist nicht wirklich unabhängig von den anderen Werten, sondern ergibt sich mehr oder weniger zwangsläufig aus der Anzahl der Punkte, der Anzahl der Gruppen und k_min. Bei meinem Beispiel gibt es 9 Punkte, die in 4 Gruppen eingeteilt werden sollen, dabei muss jede Gruppe mindestens 2 Punkte enthalten => 4*2=8 => es muss eine Gruppe mit 3 Punkten geben.

Allgemein ergibt sich das aus der Anforderung, daß alle Gruppen nahezu gleich viele Punkte enthalten sollten (was bei 9 Punkten aber natürlich nicht möglich ist).

versteh ich das richtig:
du hast n punkte (von denen du die positionen kennst)
und möchtest die in m gruppen aufteilen (deren mittelpunkt du finden willst),
so das die punkte einer gruppe möglichst dicht zusammen sind
und in jeder gruppe möglichst gleich viele punkte landen

das problem ist zunächst mal nicht eindeutig lösbar:
nimm an, 4 punkte seien an den ecken eines quadrates plaziert und du willst 2 gruppen bilden. dann gibt es schon mal 2 völlig gleichwertige lösungen.

ich würde damit beginnen die aufgabe weiter zu präzisieren.
z.b. die eigenschaften einer gruppe (mittelpunkt, radius) mathematisch festzulegen
also:
mittelpunkt: x_m=(sum_i=1..k x_i )/k ; y_m=(sum_i=1..k y_i )/k
beim radius wirds schon schwieriger: man könnte den mittleren abstand zum mittelpunkt bestimmen. oder aber den maximalen abstand vom mittelpunkt. allgemein must du also ein maß festlegen, mit dem du den radius der gruppe misst. je nach dem wie du dieses maß wählst bekommst du unter umständen unterschiedliche ergebnisse bei gleichen punktkoordinaten. auserdem wird der berechnungsaufwand unterschiedlich sein.
wenn deine punkte immer sehr stark gruppiert sind (also enge häufchen von punkten mit großen abständen zwischen den gruppen) wirds einfach, aber wenn die gruppen nicht so eindeutig plaziert sind (abstand der gruppen etwa gleich groß wie radius der gruppen) wirds schwieriger und das ergebnis weniger eindeutig.
ok - jetzt mal konkret. ich würde den radius als maximum von maximalem x-abstand und maximalem y-abstand zum zentrum definieren. das läßt sich am einfachsten berechnen und funktioniert gut, wenn die gruppen gut zu unterscheiden sind:
radius=max( max_k=1..kmax(abs(x_k-x_m)) , max_k=1..kmax(abs(y_k-y_m)) )

entscheidend für das weitere vorgehen ist nun die mutmaßliche verteilung der punkte:
also sind die punkte üblicherweise schon gruppiert (d.h. würde ich sie offensichtlich als gruppen erkennen, wenn ich sie sehe) oder sind die punkte eher gleichmäßig verteilt und die gruppen können/sollen insofern willkürlich gebildet werden?

Zitat:

---

versteh ich das richtig:
du hast n punkte (von denen du die positionen kennst)
und möchtest die in m gruppen aufteilen (deren mittelpunkt du finden willst),
so das die punkte einer gruppe möglichst dicht zusammen sind
und in jeder gruppe möglichst gleich viele punkte landen

---

Ja, das verstehst du richtig

Zitat:

---

entscheidend für das weitere vorgehen ist nun die mutmaßliche verteilung der punkte:
also sind die punkte üblicherweise schon gruppiert (d.h. würde ich sie offensichtlich als gruppen erkennen, wenn ich sie sehe) oder sind die punkte eher gleichmäßig verteilt und die gruppen können/sollen insofern willkürlich gebildet werden?

---

Gleichmäßig verteilt sind sie nicht, und sie sollten im Normalfall bereits relativ gut als Gruppen zu erkennen sein. Es kann allerdings unter Umständen auch vorkommen daß mehrere Gruppen sehr dicht nebeneinander liegen, oder sogar an nahezu der gleichen Stelle im Raum. Falls dieser Fall eintritt, z.B. wenn 4 Punkte auf einem Haufen liegen, dann müssen eben je 2 davon willkürlich in eine Gruppe gesteckt werden. Das ist aber nicht so schlimm, da das Ergebnis - also die Positionen der Gruppen - dadurch ja nicht verfälscht wird.


Die Berechnung von Mittelpunkt und Radius ist soweit klar, aber wenn die zu verwendenden Formeln feststehen, bleibt ja immernoch das Problem wie ich denn die Punkte konkret sortieren kann. Irgendwo muss ich ja anfangen, und am Anfang habe ich außer einem Haufen Punkte nurnoch die Information wieviele Gruppen am Ende rauskommen sollen, und wieviele Punkte in jede Gruppe müssen

nur geduld, da kommen wir schon noch hin :-)

wenn die gruppen in der regel bereits als gruppen zu erkennen ist, dann hat man folgenden konflikt: wen man die situation nach minimalem abstand optimiert wird man unter umständen nicht den wunsch nach gleichmäßiger verteilung der punkte in die gruppen erfüllen können und umgekehrt. da müßte man die prioritäten mal näher spezifizieren/quantifizieren.

wäre nicht schlecht mal den hintergrund der aufgabe noch etwas genauer zu erläutern.

so, nun mal ein erster lösungsvorschlag:
1- nimm die ersten beiden punkte und betrachte sie als jeweils eine gruppe mit einem punkt.
2- nimm den nächsten punkt dazu und ordne ihn je nach abstand einer der beiden gruppen zu
3- berechne mittelpunkt der erweiterten gruppe neu
4- weiter bei 2- bis alle punkte in eine der zwei gruppen eingeordnet sind.
5 - behandle nun jede der zwei gruppen nach schema 1-4 um vier gruppen zu erhalten
6- lass dir noch was schlaues einfallen um eine gruppenanzahl zu handhaben, die keine 2er potenz ist :-)
dieser vorschlag ist wohl noch verbesserungsfähig, aber das prinzip teile und herrsche sollte man im auge behalten.

ein zweiter vorschlag:
1- teile das gesamtgebiet in ein raster/schachbrett auf und berechne die punktanzahl für jede teilfläche
2- such die m felder mit den meisten punkten
3- ordne diesen feldern jeweils eine gruppe zu, berechne mittelpunkt.
4- ordne restliche punkte nacheinander (nach abstand) diesen gruppen zu
auch dieser vorschlag ist nicht viel mehr als ne erste skizze.

wenn ich mal zeit habe, lass ich mir noch was besseres einfallen :-)

Geh in die nächste Bibliothek/ technische Bibliothek und borg Dir ein Buch über Statistik aus. Das könnte helfen.
Hat was mit Standardabweichung und so zu tun.

@shakespear
glaub ich nicht, erklär mal!

Wie wäre es mit der Verwendung des Mahalanobisabstands?
http://de.wikipedia.org/wiki/Mahalanobis-Distanz

skaleninvariant und translationsinvariant
Wer bietet mehr?

-------------
Nachtrag:
Ja, harter Stoff.
Es gibt auch einfachere Abstandsklassifikatoren, aber dann wahrscheinlich weniger invariant.

Wirklich harter Stoff...

Zitat:

---

skaleninvariant und translationsinvariant

---

ist das bei meinem Problem überhaupt notwendig? (ok, Translationsinvarianz wäre wohl durchaus sinnvoll, aber Skaleninvarianz?)
Es geht doch nur darum eine bestimmte Anzahl an Punkten in Gruppen einzuteilen.


@fumir
Dein erster Lösungsansatz klingt schonmal recht vielversprechend, es stellt sich nur die Frage ob und welche Probleme auftauchen können.

Es ist natürlich so, daß ein einmal falsch zugeordneter Punkt nie mehr in der richtigen Gruppe landen kann, z.B. wenn man ganz am Anfang zwei Punkte wählt die eigentlich zu einer Gruppe gehören. Andererseits könnte dieses Problem wohl umgangen werden, indem man zu Beginn jedes Schrittes grundsätzlich die am weitesten voneinander entfernten Punkte als Basis für die neuen Gruppen wählt.

edit:
das Verfahren scheint mir eigentlich auch für andere Anzahlen von Gruppen geeignet zu sein. Ich meine prinzipiell geht es ja darum eine Gruppe immer weiter zu teilen, so lange bis sie nicht mehr teilbar ist (bei meinem Fall wäre das bei Gruppen mit weniger als 4 Punkten der Fall). Und dieser "atomare" Zustand kann bei den Gruppen ja durchaus zu unterschiedlichen Zeitpunkten eintreten oder?

eine spezielle wahl des abstandbegriffes wäre nur nötig, wenn die punkte relativ gleichmäßig verteilt wären. das scheint hier aber nicht der fall. deshalb geht die mahalanobis-distanz erst mal am problem vorbei. man könnte sich das aber noch mal anschauen, wenn man die gruppen schon mal erkannt hat, und ihnen dann einen möglichst sinnvollen mittelpunkt zuordnen will (der muss ja nicht unbedingt der schwerpunkt der punkte sein, das ist ne frage der aufgabenstellung)

ja, wenn man die punkte ungünstig erwischt hat man erst mal ein problem.

es gibt ne methode die wohl gut funktioniert, aber lange rechnet (was bedeutungslos wäre, wenn es um relativ wenige punkte (<100) geht):
1- nimm den ersten punkt
2- berechne die abstände aller anderen punkte zu diesem und sortiere die punkte nach diesem abstand
3- nimm die ersten (incl. dem ausgangspunkt) n/m punkte in der sortierten liste als erste gruppe
4- mach mit den restlichen punkten bei 1- weiter bis du alle gruppen hast
problem: wenn zwei gruppen dicht benachbart sind, und du erwischst als ersten punkt einen der in der mitte zwischen den beiden gruppen liegt, dann bekommst du eine gruppe im zentrum dieses gruppenhaufens und eine weitere die nicht mehr zusammenhängend ist und sozusagen die erste gruppe umschließt. das könnte man aber erkennen, da die mittelpunkte dieser beiden gruppen dann dicht beieinander sind und insbesondere jeweils innerhalb der anderen gruppe liegen. dann kann man diese beiden problemgruppen einfach wieder zusammenwerfen und neu trennen.

vermutlich wird man am ende ohnehin bei einem algorithmus landen, der ne erste lösung bestimmt, diese verifiziert und gegebenenfalls verbessert.

in nem buch bin ich auf den begriff "zuordnungsproblem" gestoßen. das scheint unserer sache ziemlich nahe zu kommen. kannst ja mal weiter in diese richtung recherchieren.

ich würde vermutlich eher die zweite von mir angedeutete methode weiter verfolgen. etwas in der art: raster verfeinern und geometrisch nachbarn suchen. das kommt unserem auge wohl näher. schau dazu mal unter dem stichwort "bereichssuche"

ich glaube nicht das dass funktioniert, da nicht alle möglichkeiten des punktehaufens nicht besetzt sein müssen.
vl solltest du die plätze in einer gruppe nur besetzen bis der schwerpunkt einen merklichen sprung macht. ( dabei stellt sich aber die frage was ein merklicher sprung ist).

mfg clemens

ich hab noch was gefunden:
ein minimal spannender baum hat als knoten die punkte und verbindet sie durch kanten, so dass die gesamtlänge der kanten minimal ist. daraus ergibt sich, das es zwischen zwei gruppen nur eine kante geben wird und die punkte einer gruppe im baum eng benachbart sein müssen. damit könnte man die gruppen also finden.
die berechnung erfordert NlogN zeit.

das finden der zwei dichtest benachbarten punkte kostet ebenfalls NlogN zeit.

die lösung deines problems sollte wohl etwas zwischen N^2 und NlogN zeit benötigen.

wieviele punkte hast du denn?

Moin auch!
Mal ganz was anderes: wie wäre es mit einer Dichteverteilung?
Man berechnet die Punktdichte im Raum für Punkte auf einem Raster festgelegten Abstandes.
Dabei gibt es mehrere Möglichkeiten.
1. Man berechnet die Dichte als Anzahl der Punkte pro Kugelvolumen, wobei der Radius der Kugel viel größer ist als das Raster aber viel kleiner als der Raum.
2. Man berechnet die Dichte für das unter 1 beschriebene Kugelvolumen in jedem Punkt auf dem Raster, wobei der Beitrag eines Punktes mit dem (zb) Quadrat der Entfernung abnimmt: D(x,y,z)=(1/r1²+1/r2²+...)/V mit rP<Kugelradius. (rP: Entfernung eines Rasterpunktes zum Punkt P, V: Kugelvolumen)
Ich schlage spontan Variante 2 vor. Man erhält dadurch eine Dichteverteilung, bei der es keine abrupten Spünge gibt. Dadurch sollte es möglich sein die Hochpunkte dieser Verteilung durch Berechnung der Gradienten zu bestimmen. An diesen Orten, nämlich Orten hoher Dichte lässt sich anschließend die Auflösung erhöhen, um die Gruppenmittelpunkte genauer festzulegen.
Anschließend wählt man diejenigen Punkte aus, die den höchsten Beitrag zur Dichte in den Hochpunkten gegeben haben, wobei man eine "schwammige" Grenze der Mitgliederanzahl ziehen kann, weil man die Punktzahl durch die Anzahl der gefundenen Gruppen teilen kann.
Erhält man Orte überdurchschnittlich hoher Dichte, ist dies ein Hinweis darauf, dass 2 Gruppen dicht beieinander liegen.
Es ist sicherlich möglich, Verfahren zur Abschätzung des Mindestrastermaßes und des Kugelradius zu definieren, aber das wäre mir im Moment zu viel. ;-)
Gruß

@fumir, naja hat schon was mit Statistik zu tun, das andere Beispiel oben kommt auch aus der Statistik. Kann, und will mich jetzt nicht viel damit beschäftigen, aber wollt einfach einen Tip geben, wo die Lösung zu suchen ist. Du kannst ja wie beim vorigen Beispiel einen Raster machen, für jeden Punkt einen Wert ermitteln, der die Dichte der Punkte beschreibt(Funktion vom Abstand) und dann die Mittelpunkte der Gruppen als jene Punkte mit den 4 höchsten Dichten festlegen. Dann musst du nur noch die Punkte zuteilen, indem du den Abstand der Punkte zu deinen Gruppenmittelpunkten vergleichst und dann aufteilst. Das wird wahrscheinlich für Dich ausreichen.
Wenn du dann Punkte hast, die eigentlich möglicherweise zu keiner Gruppe gehören, kannst du jene Punkte mit einer Mehrfachen Standardabweichung vom Mittelpunkt aussortieren. Irgendwie auf die Art.
Viel Glück beim Umsetzen. mfg

Zitat:

---

wieviele punkte hast du denn?

---

Pro Berechnung: je 9 die in 4 Gruppen eingeteilt werden müssen (bzw. allgemein eben eher wenige Punkte)
Insgesamt: unterschiedlich, im Normalfall jedoch mehrere tausend

Das Problem, das ich bei allen vorgestellten Verfahren (außer dem ersten) sehe, liegt in k_min und k_max...
Die Gruppen dürfen ja nicht mehr als 3 Punkte enthalten, aber auch nicht weniger als 2.

Zitat:

---

Wenn du dann Punkte hast, die eigentlich möglicherweise zu keiner Gruppe gehören

---

Gibt es nicht...
jeder Punkt muss in eine der Gruppen sortiert werden

@user529 verstehe nicht ganz was du meinst. möglicherweise hast du auch mich falsch verstanden :-)

3- nimm die ersten (incl. dem ausgangspunkt) n/m punkte in der sortierten liste als erste gruppe.

aber in der gruppe sind drei plätze, bei 4 gruppen und maximal 3 plätzen heißt dass dass die letzte gruppe durch die finger schaut. oder ich habe dich wirklich falsch verstanden.

@gock
@shakespaer
die vorschläge zum thema dichte gehen in die selbe richtung wie mein zweiter lösungsvorschlag. da kann man sich natürlich diverse varianten vorstellen.
prinzipiell würde ich aber nach möglichkeit fließkommaberechnungen vermeiden.
deshalb auch mein vorschlag für die definition des abstandsbegriffs mittels max.
wer will schon ständig irgend ne wurzel für den euklidschen abstand berechnen!
wenn man mit solchen dichten rumrechnet, wird man aber ne menge rechnen müssen.

@user529
ach so.
ich bin nicht von ner festen anzahl von plätzen ausgegangen, sondern hab erst mal eine lösung für das allgemeinere problem gesucht (viele punkte, viele gruppen, viele punkte je gruppe) da felix eine allgemeine lösung des problems bevorzugt (siehe ganz oben)

das spezielle problem ist auf jeden fall viel einfacher als der allgemeine fall.
ich würde erst mal nen beliebigen punkt weglassen, und die restlichen 8 punkte zu paaren gruppieren, dann den 9ten punkt zur nächstgelegenen gruppe hinzufügen. bei so wenigen punkten braucht man sich auch kaum gedanken zur performance zu machen.

das problem 8 punkte auf 4 gruppen zu verteilen ist ein zuordungsproblem (wie oben schon erwähnt) für das es fertige algorithmen in entsprechenden büchern zu finden gibt.
allerdings gehts da eigentlich um graphen, d.h. die geometrische seite unseres problems würde dabei ziemlich unter den tisch fallen (und nur als kantengewichtung entsprechend dem abstand der punkte eingehen). damit wird man auf diese weise wohl keinen optimalen algorithmus bekommen.

es gibt natürlich immer ne brute force methode. in dem fall:
1- wähle eine beliebige zulässige zuordnung von punkten zu gruppen
2- berechne für diese konfiguration den maximalen radius der gruppen und den minimalen abstand der gruppen
3- mache 1- und 2- für jede mögliche konfiguration
4- such dir die konfiguration mit kleinstem maximalen gruppenradius und maximalem minimalen gruppenabstand heraus.

bei 8 punkten und 4 gruppen gibts ja nur 840 mögliche konfigurationen, also recht überschaubar. bei mehr punkten wirds aber einfach zu rechenintensiv.

Zitat:

---

Zitat von fumir

ich würde erst mal nen beliebigen punkt weglassen, und die restlichen 8 punkte zu paaren gruppieren, dann den 9ten punkt zur nächstgelegenen gruppe hinzufügen. bei so wenigen punkten braucht man sich auch kaum gedanken zur performance zu machen.

---

Auf die Idee war ich auch schon gekommen...

aaaber:
das geht nur wenn man zufällig den Punkt weglässt, der zur 3er Gruppe gehört. Fehlt ein Punkt einer 2er Gruppe, dann ist die Zuordnung zwangsläufig falsch

@fumir
Ne, das ist schon anders:
1. Wie soll man denn im 3D Raum Punkte auf Flächen suchen? Man müsste es mindestens von 3 Seiten betrachten.
2. Je nach Wahl der "Fläche" ergeben sich Sprünge, je nachdem, ob man ein oder mehrere Punkte noch reinnimmt oder nicht. Das ist ein Problem.
3. Jede "Fläche" muss relativ groß sein, damit überhaupt mehrere Punkte drinnen sind. Dadurch lässt sich aber schwer unterscheiden, ob 2 Gruppen nah beieinander liegen. Gerade bei weinigen Punkten (zb 3) ist der Fehler groß.
4. Wurzeln ziehen musst Du auch bei genauen Abstandsberechnungen auf einer Fläche. Wenn Przission nicht wichtig ist, kommt man auch im 3D drum herum.
5. Von Aufwandsoptimierung war keine Rede in der AUfgabenstellung.
6. Deine Formulierungen sind zwar umfangreich, aber nicht überall sehr präzise.
7. Warum bombadierst Du uns mit tausend Posts? Schreib einen und gut iss!
@Felix
Dein Problem mit k_min und max kann ich nicht nachvollziehen.
Gute Nacht!

wie wärs mit folgendem:

du kannst die gesamtgröße des gebietes bestimmen (max min der koordinaten, lineare laufzeit)
du kennst die anzahl der gruppen, daher kannst du den wahrscheinlich durchschnittlichen abstand der gruppen abschätzen (bei nem quadratischen gebiet und 4 gruppen zb. etwa halbe kantenlänge)
wenn du nun zwei beliebige punkte betrachtest, dann kannst du ihren abstand mit diesem mittleren gruppenabstand vergleichen und so raten, ob die zwei punkte zu einer gruppe (abstand viel kleiner als gruppenabstand) oder zu verschiedenen gruppen (abstand in größenordnung des gruppenabstandes) gehören.
wenn du auf diese weise eine einteilung gefunden hast, kannst du diese noch mal verifizieren und gegebenfalls koorigieren.

so macht das vielleicht auch unser hirn: schauen wie groß das ganze ist und daraus schätzen was man als nah und was als weit entfernt betrachtet. dann lokal prüfen (innerhalb einer gefundenen gruppe), obs passt.

wenn man erst einmal eine gruppe identifiziert hat (abstand innerhalb der gruppe klein, zu allen anderen punkten groß) dann kann man sie im weiteren ausklammern und hat das problem reduziert. am ende bleibt dann womöglich ein rest der ne spezialsituation darstellt (z.b. zwei eng benachbarte gruppen) für die man eine andere strategie einsetzt.

deshalb wäre es vielleicht hilfreich mal ein paar fallbeispiele (typische punktmengen) festzulegen. zum einen, um etwas handfestes zu haben, über das man reden kann. und zum anderen um testdaten zu haben, um die algorithmen im geiste und später als programm zu testen.

Zitat:

---

@Felix
Dein Problem mit k_min und max kann ich nicht nachvollziehen.

---

Naja, bei den bisherigen Varianten sehe ich halt ein Problem darin, daß eventuell die Anzahl der Punkte pro Gruppe nicht korrekt ist. Etwa wenn zwei Gruppen nah beieinander (oder gar an der selben Stelle, auch das ist denkbar) liegen, oder wenn ein Punkt genau zwischen zwei Gruppen liegt etc.

Aber vielleicht habe ich ja auch irgendwo einen Denkfehler, und solche Situationen würden bei den angesprochenen Verfahren kein Problem darstellen.

Zitat:

---

du kannst die gesamtgröße des gebietes bestimmen

---

Ok, soweit kein Problem, ich normiere die Daten einfach auf einen Bereich von 0...1.

Zitat:

---

du kennst die anzahl der gruppen, daher kannst du den wahrscheinlich durchschnittlichen abstand der gruppen abschätzen (bei nem quadratischen gebiet und 4 gruppen zb. etwa halbe kantenlänge)

---

hmm, aber es kann ja durchaus vorkommen, daß zwei Gruppen extrem nah benachbart sind, die anderen hingegen weit voneinander entfernt

Zitat:

---

wenn du auf diese weise eine einteilung gefunden hast, kannst du diese noch mal verifizieren und gegebenfalls koorigieren.

---

nur wie soll ich diese Einteilung verifizieren? Wie kann ich herausfinden ob ich einen Punkt falsch zugeordnet habe?

Zitat:

---

am ende bleibt dann womöglich ein rest der ne spezialsituation darstellt (z.b. zwei eng benachbarte gruppen) für die man eine andere strategie einsetzt.

---

Wobei du voraussetzt, daß man überhaupt erstmal erkennt daß es zwei oder mehrere eng benachbarte Gruppen gibt, denn sonst könnte man für diese ja dann keine andere Strategie einsetzen.

Zitat:

---

deshalb wäre es vielleicht hilfreich mal ein paar fallbeispiele (typische punktmengen) festzulegen. zum einen, um etwas handfestes zu haben, über das man reden kann. und zum anderen um testdaten zu haben, um die algorithmen im geiste und später als programm zu testen.

---

Naja, setz 9 Punkte in 3 2er und einer 3er Gruppe an beliebige Stellen in einen Würfel mit einer Kantenlänge von 1.

Es gibt da eigentlich keine wirklich "typischen" Szenarios, denn die Gruppen können so ziemlich überall innerhalb des Wertebereichs (=des Würfels) liegen. (theoretisch wäre es sogar denkbar - wenn auch recht unwahrscheinlich - daß alle 9 Punkte an der gleichen Position liegen)


Um konkrete Testdaten zu haben würde ich also dazu tendieren einige worst-case Szenarien zu definieren...
z.B. zwei Gruppen die so eng beieinander liegen, daß sie nicht mehr unterscheidbar sind, oder eine 3er Gruppe bei der ein zugehöriger Punkt auf halbem Weg zu einer benachbarten 2er Gruppe liegt, oder irgendwie sowas.

@gock
jo, ich hab das 3d wohl überlesen, bzw. nicht ernst genommen, weils vermutlich auch nicht wichtig ist. in 3d sinds dann eben kuben statt rechtecken, wenn man das gebiet aufteilt.
ich denke mal, alle meine vorschläge lassen sich ohne weiteres auch in 3d betrachten.

felix hat ausdrücklich nach ner allgemeinen lösung gefragt. diese beinhaltet dann auch viele punkte und das bedingt überlegungen zur effizienz. viele methoden die im kleinen anwendbar sind, werden völlig unbrauchbar, wenn es um größere probleme geht.

meine posts spiegeln zum einen meine einarbeitung in die thematik wieder und zum anderen reaktionen auf hinweise anderer. wenns dich stört, brauchst du es ja nicht zu lesen. war mir nicht bewußt, das die anzahl oder länge der posts beschränkungen unterliegt.

im übrigen habe ich völlig verschiedene ansätze vorgestellt, was sollen die denn zusammen in einem post. das trenn ich lieber nach thema. dieses problem hast du natürlich nicht, da du bisher nur in richtung statistik gedacht hast. man kann das problem aber unter völlig unterschiedlichen gesichtspunkten untersuchen.

wenn du in ein paar wochen ne fertige lösung hast, kannst du die ja dann gerne posten.
bis dahin versuche ich hinweise zu geben, in welche richtung man weiter recherchieren könnte, und überlass das lösen dem threadautor.

@felix
nehmen wir mal an, wir haben die punkte irgendwie eingeteilt und wollen das nun prüfen:
- wir können für jede gruppe erst mal mittelpunkt und radius bestimmen
damit können wir schon mal prüfen, ob sich die gruppen überlappen
- dann können wir noch für jeden punkt prüfen, ob es ne andere gruppe gibt, zu der er nen kleineren abstand hat, als zum mittelpunkt der eigenen.

Ok, also mal angenommen ich nehme die einfache Variante, die jedoch prinzipiell erstmal ein fehlerhaftes Ergebnis produzieren kann...

Ich sortiere also 8 der 9 Punkte jeweils zu 2er Gruppen, und den letzten ordne ich der Gruppe zu, zu der er den kleinsten Abstand hat. Falls dieser letzte Punkt jedoch eigentlich zu einer 2er Gruppe gehört hätte, werden sicherlich mindestens 2 der 4 Gruppen falsch sein.

Ich berechne also zu jeder Gruppe erstmal den Radius und den Mittelpunkt, und überprüfe ob es Gruppen gibt die sich überlappen (was ja prinzipiell erstmal nicht bedeuten muss, daß sie falsch sind).

Und dann wird für jeden Punkt der potentiell falschen Gruppen nochmal überprüft, ob er in einer anderen Gruppe vielleicht besser aufgehoben wäre.

so weit so gut...
nur daß dabei natürlich Punkte aus einer Gruppe entfernt, und zu einer anderen hinzugefügt werden, wodurch die Anzahl der Punkte pro Gruppe möglicherweise nicht mehr stimmt. Es stellt sich also die Frage, ob dieses Verfahren, wenn man es solange durchführt bis keine Punkte mehr umsortiert werden, am Ende in jedem Fall ein richtiges Ergebnis liefert.

vielleicht sollte man sich darauf konzentrieren erst mal zwei punkte zu finden die sehr wahrscheinlich zu einer gruppe gehören (weil sie eng benachbart sind, und alle anderen weit weg sind)
findet man zwei solche punkte kann man sie vom weiteren ausschliesen.
findet man keine, dann müssen alle punkte eine einzige mehr oder weniger gleichmäßige wolke bilden. für diesen fall müßte man dann wohl ganz anders vorgehen.

ich denke inzwischen, dass es keine so gute idee ist, erst 8 zu sortieren und dann den letzten dazu zunehmen.

mal sehen - wenn wir mit irgendeinem punkt anfangen und den punkt suchen der am nächsten dran ist (linearer aufwand) dann müßten diese beiden auf jeden fall zu einer gruppe gehören, oder?

dann würde ich mit dem zweitnächsten punkt weitermachen. wieder den nächsten punkt suchen. dann aber prüfen, ob der dritte punkt besser zum vierten punkt oder besser zur ersten gruppe passt.

und dann irgendwie in der art weiter.

bei manchen optimierungsproblemen findet man das optimum nur, indem man alle konfigurationen ausprobiert. wenn dein problem zu dieser sorte gehört, dann kann man nur noch versuchen, das vergleichen aller konfigurationen so optimal wie möglich durchzuführen (nur für wenige punkte, z.b. 9 möglich) oder man sucht nach einem verfahren, das statistisch gesehen meistens eine gute, wenn auch nicht optimale lösung findet. da hat man natürlich dann ein problem, wenn die zweitbeste lösung schon zu schlecht ist, um noch akzebtabel zu sein.