Noch ein mathematisches Problem

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.