Ansatz für Problemlösung gesucht

Hallo,

mein Problem lässt sich wie folgt beschreiben:

Gegeben eine Menge von Punkten (~ 30).
Jeder Punkt gehört entweder zur Gruppe A oder zur Gruppe B. Die Gruppen A und B können als gleich groß angesehen werden.

Wenn ich mir fünf Punkte herausgreife, kann ich herausfinden, ob diese fünf Punkte zur selben Gruppe gehören oder nicht (aber nicht zu welcher). Es geht nur für fünf. Nicht für weniger oder mehr.

Nun möchte ich mit Hilfe dieser Abfrage, ob fünf Punkte zur selben Gruppe gehören, die Einteilung der Punkte in Gruppen rekonstruieren. Ob am Ende die Gruppe A immer noch A ist oder B, das ist mir egal. Hauptsache ist, dass diejenigen Punkte zusammenkommen, die auch ursprünglich zur selben Gruppe gehören.

Hat jemand eine Idee, wie ich das lösen könnte?

Wichtiger Nachtrag!
Ich kann nur mit einer gewissen Fehlerwahrscheinlichkeit feststellen, ob 5 Punkte zur selben Gruppe gehören oder nicht. Diese ist gering, aber es kann halt schon passieren (insbesondere könnte die Funktion "ja" sagen, obwohl die Punkte NICHT zur selben Gruppe gehören).

Gesucht ist also eine Gruppenaufteilung, die "maximal wahrscheinlich" ist.

Worauf ich bisher schon gekommen bin:

1. Ich versuche durch zufälliges Ausprobieren 5 Punkte zu finden, die zur selben Gruppe gehören.
2. Ich nehme einen davon raus und setze dafür der Reihe nach alle anderen Punkte ein. Wenn ich "ja" rauskriege, weiß ich, dass dieser Punkte ebenfalls zur Gruppe gehört. Ansonsten gehört er zur anderen.

Das Problem damit ist, dass sich die Fehlerwahrscheinlichkeit des Einzeltests sozusagen auf das Gesamtergebnis überträgt, das dann komplett falsch wäre.

Christoph

spezifritz schrieb:

Gesucht ist also eine Gruppenaufteilung, die "maximal wahrscheinlich" ist.

Ich denke, du müsstest genauer formulieren, was du mit "maximal wahrscheinlicher Gruppenaufteilung" exakt meinst.

Ich beschreib mal, was man machen könnte, wenn der Algorithmus keine Fehlerwahrscheinlichkeit hat.

Wenn du erstmal eine 5er-Menge von Punkten gefunden hast, die alle zur selben Gruppe gehören, ist das Problem sehr einfach: Prüfe für jeden nicht enthaltenen Punkt, ob du ihn hinzufügen kannst, Laufzeit O(n).

Eine 5er-Menge von Punkten zu finden, die alle in derselben Gruppe liegen, dafür gibt es sicherlich mehrere Möglichkeiten. Die simpelste wäre wohl stupides Durchprobieren und einfach zufällige 5er-Mengen von Punkten herauszugreifen, bis man eine findet, bei der der Algorithmus sagt "ja, die 5 Punkte liegen in derselben Gruppe". Es gibt (30 über 5) Möglichkeiten, 5 Punkte herauszugreifen. Es gibt (15 über 5) Möglichkeiten, dabei erfolgreich zu sein. Im Schnitt wird man also mit Wahrscheinlichkeit (15 über 5) / (30 über 5) einen Treffer landen, das sind etwas über 2%. Macht knapp 500 erwartete Versuche, das ist vermutlich schnell genug.

edit: Ich hab diesen Post geschrieben bevor ich deinen 3. Beitrag gesehen hab.

Christoph

spezifritz schrieb:

Worauf ich bisher schon gekommen bin:

1. Ich versuche durch zufälliges Ausprobieren 5 Punkte zu finden, die zur selben Gruppe gehören.
2. Ich nehme einen davon raus und setze dafür der Reihe nach alle anderen Punkte ein. Wenn ich "ja" rauskriege, weiß ich, dass dieser Punkte ebenfalls zur Gruppe gehört. Ansonsten gehört er zur anderen.

Das Problem damit ist, dass sich die Fehlerwahrscheinlichkeit des Einzeltests sozusagen auf das Gesamtergebnis überträgt, das dann komplett falsch wäre.

Was genau bedeutet "der Algorithmus macht Fehler"? Ist der Algorithmus deterministisch, d.h. wenn er Fehler macht, macht er sie reproduzierbar immer wieder?

50 Versuche im Schnitt meinst du, oder (bei 2%)?
Ich denke das ginge noch von der Anzahl der Tests her. So ein Test geht recht schnell.
Das Problem dabei ist halt, dass wenn ein fehlerhafter Test zu diesen 5 Ausgangspunkten geführt hat, dann die ganze Lösung "Mist" ist.
Es wäre super, wenn man den Fehler irgendwie verteilen könnte.

Der Test ist deterministisch, aber er baut auf einem Kriterium auf, aus dem nicht zwingend folgt, dass die Punkte zur selben Gruppe gehören.

Christoph

spezifritz schrieb:

50 Versuche im Schnitt meinst du, oder (bei 2%)?

Oh, natürlich. Dann ist das sogar noch besser.

spezifritz schrieb:

Ich denke das ginge noch von der Anzahl der Tests her. So ein Test geht recht schnell.
Das Problem dabei ist halt, dass wenn ein fehlerhafter Test zu diesen 5 Ausgangspunkten geführt hat, dann die ganze Lösung "Mist" ist.

Nein, das wäre nicht unbedingt der Fall, weil du ja noch nach und nach ~10 Punkte hinzufügst zu deiner Lösung. Wenn die ursprünglichen 5 Punkte schon falsch gewählt waren, wird das in diesem Schritt vermutlich auffallen.

Danke.
Ich glaube ich werde es so mal probieren.
Vielleicht auch noch mehrmals das mit den 5 Punkten machen (könnte man gut parallelisieren) und am Ende irgendwie abstimmen.

volkard

Ich würde es so versuchen: Es gibt nur 142506 Fünfermengen aus 30 Punkten. Die erstmal alle Testen und geeignet speichern. Und dann das Punktepaar finden, das am wahrscheinlichsten in einer Gruppe ist, weil möglichst viele Fünfermengen in der gleichen Gruppe bleiben, wenn man die Punkte des Paars auswechselt. Die beiden Paarpunkte zusammenfassen zu einem Punkt. Und weiter bis es nur noch zwei Punkte gibt.