Partitionierung, Auszeichnungsfunktion, Graphentheorie

15.11.2022, 10:23

GMath

Auf diesen Beitrag antworten »

Partitionierung, Auszeichnungsfunktion, Graphentheorie

Hallo!
Ich bin kürzlich auf ein Problem gekommen, das ich nicht
recht fassen und einordnen kann - vielleicht Graphentheorie?

Gegeben
Eine Grundmenge G mit n Elementen (n ca. 1e6) sowie
t Funktionen die jedes der obigen Elemente auf 0 oder 1 abbilden
(t ca. 1e3, "Auszeichnungs-Funktionen" o.ä.?)

Jede Untermenge der t Funktionen legt eine Menge von Elementen aus G fest
(diejenigen, den von mindestens einer der Funktionen auf 1 abgebildet werden).

Gesucht
Alle Untermengen von Funktionen mit der Eigenschaft,
dass keine Erweiterung von ihr
die Anzahl der auf 1 gesetzten ("ausgezeichneten") Elemente verringert
(= ... dass keine Verkleinerung von ihr
die Anzahl der "ausgezeichneten" Elemente vergrößert?).
Letztlich interessieren mich nur diejenigen Untermengen,
die die größten Anzahlen von "ausgezeichneten" Elemente erzeugen.

Mit meinem (ziemlich) beschränkten Wissen habe ich versucht
eine Verbindung zu den typischen bekannten Problemen/ Alg.
in dem Bereich zu finden. Leider ohne Erfolg.

Hat jemand einen Hinweis für mich:

Wohin gehört das?
Ist das ein bekanntes Problem?
Komplexität? (Ich vermute NP-vollst.)
Falls NP-vollst.: Gibt es Näherungsalg.?

15.11.2022, 10:32

Elvis

Auf diesen Beitrag antworten »

Egal welche Menge von Funktionen erweitert wird, die Menge der ausgezeichneten Elemente wird nicht kleiner. Vermutlich habe ich dein Problem noch nicht verstanden.

15.11.2022, 10:52

GMath

Auf diesen Beitrag antworten »

Pardon, der Fehler liegt bei mir!

Der 3.Abschnitt muss richtig heißen ("allen" statt: "mindestens einer").
Also:

Jede Untermenge der t Funktionen legt eine Menge von Elementen aus G fest
(diejenigen, den von allen Funktionen auf 1 abgebildet werden).

(Beitrag konnte nicht mehr editiert werden).

15.11.2022, 11:08

HAL 9000

Auf diesen Beitrag antworten »

Ok, MIT dieser wichtigen Änderung wären wir bei

Zitat:

Original von GMath (angepasst)
Jede Untermenge der t Funktionen legt eine Menge von Elementen aus G fest
(diejenigen, den von allen Funktionen auf 1 abgebildet werden).

[...]

Letztlich interessieren mich nur diejenigen Untermengen,
die die größten Anzahlen von "ausgezeichneten" Elemente erzeugen.

Das ist ja dann ganz klar diejenige Einermenge, die schlicht aus der Funktion mit den meisten ausgezeichneten Elementen besteht.

Selbstredend kann es auch mehrere solche Funktionen und damit jeweils zugeordnete Einermengen mit der gleichen maximalen Anzahl an ausgezeichneten Elementen geben.

Wo ist denn hier das algorithmische Problem? Oder forderst du zusätzlich, dass die Untermengen eine gewisse Mindestmächtigkeit haben? Bisher lese ich nichts dergleichen. verwirrt

verwirrt

15.11.2022, 11:09

Elvis

Auf diesen Beitrag antworten »

Auch dieses Problem ist trivial. Jede Menge von Funktionen verringert durch Erweiterung um die Nullfunktion die Menge der ausgezeichneten Elemente zur leeren Menge.

15.11.2022, 11:18

HAL 9000

Auf diesen Beitrag antworten »

@Elvis

Den Teil hab ich ganz überlesen...

@GMath

Vielleicht versuchst du, das ganze mal in Symbolsprache zu überführen, da passieren womöglich weniger Unfälle:

Es geht um Indikatorfunktionen $\begin{eqnarray*} f:~G\to \{0,1\} \end{eqnarray*}$ , und du betrachtest eine Teilmenge $\begin{eqnarray*} T\subseteq \{0,1\}^G \end{eqnarray*}$ dieser Indikatorfunktionen, wir wissen nur $\begin{eqnarray*} |T|=t \end{eqnarray*}$ .

Für $\begin{eqnarray*} U\subseteq T \end{eqnarray*}$ ist nun $\begin{eqnarray*} \bigcap_{f\in U} f^{-1}\left(\{1\}\right) \end{eqnarray*}$ die Menge der durch $\begin{eqnarray*} U \end{eqnarray*}$ ausgezeichneten Elemente von $\begin{eqnarray*} G \end{eqnarray*}$ .

Das mal als ein möglicher Anfang.

Anzeige

15.11.2022, 11:37

Elvis

Auf diesen Beitrag antworten »

Gute Idee, das Problem lässt sich anscheinend in der Sprache der Mengenlehre formulieren und dann vielleicht auch dort lösen.

15.11.2022, 12:56

GMath

Auf diesen Beitrag antworten »

Oh-je... da hab' ich ja wohl ziemlich gepatzt.
Tut mir leid - ich bin nicht so der Formalisierungsbär. Augenzwinkern

Augenzwinkern

@HAL 9000:
Danke für den Rahmen.

Vorgegeben ist eine Teilmenge T der Indikatorfunktionen.
Ich suche diejenigen Untermengen dieser Teilmenge,
die nicht um irgendeine weitere Indikatorfunktion der Teilmenge
erweitert werden können, so dass die Anzahl der mit der Untermenge
ausgezeichneten Elemente aus G verringert wird.
(Die Hinzunahme einer Indikatorfunktion zu einer Untermenge
bedeutet ja eine zusätzliche Bedingung, die potentiell
die Anzahl der ausgezeichneten Elemente von G verringert).

Ich brauche ja wohl kaum zu erwähnen,
dass meine Frage aus der Praxis kommt? Augenzwinkern

Augenzwinkern

Und da ist es eigentlich ganz simpel:
Die Indikatorfunktionen sind Eigenschaften,
Elemente aus G können diese Eigenschaften erfüllen oder auch nicht.
Ich will nun wissen, welche Untermengen meiner
vorgegebenen Menge von Eigenschaften T
nicht mehr um weitere "Bedingungen" erweitert werden können,
so dass die Anzahl der bisher ausgezeichneten Elemente aus G
verringert wird.

Im weiteren suche ich unter all diesen speziellen Untermengen diejenigen,
die die größten Mengen ausgezeichneter Elemente beschreiben.
Diese wären dann für mich Kandidaten,
um neue Indikatorfunktionen zu ersinnen,
die die großen Mengen ausgezeichneter Elemente gut partitionieren
(optimalerweise halbieren).
So ähnlich wie Aufbau eines Suchbaum...
EDIT:
Oder Cliquen-Problem fällt mir auch noch ein. Passt aber nicht...

15.11.2022, 13:31

HAL 9000

Auf diesen Beitrag antworten »

Ok, langsam beginne ich zu begreifen:

Man kann zunächst mal mit $\begin{eqnarray*} A:=\bigcap_{f\in T} f^{-1}\left(\{1\}\right) \end{eqnarray*}$ die Menge aller ausgezeichneten Elemente bestimmen, wenn man als Untermenge die Gesamtmenge $\begin{eqnarray*} T \end{eqnarray*}$ nimmt.

Nun kann es aber sein, dass es bereits echte Teilmengen $\begin{eqnarray*} U \end{eqnarray*}$ von $\begin{eqnarray*} T \end{eqnarray*}$ gibt mit ebenfalls $\begin{eqnarray*} \bigcap_{f\in U} f^{-1}\left(\{1\}\right) = A \end{eqnarray*}$ , und genau die suchst du!

Es können nämlich nicht Teilmengen $\begin{eqnarray*} U \end{eqnarray*}$ sein, wo $\begin{eqnarray*} \bigcap_{f\in U} f^{-1}\left(\{1\}\right) = B \end{eqnarray*}$ mit einer echten Obermenge $\begin{eqnarray*} B\supsetneqq A \end{eqnarray*}$ ist:

Denn dann gibt es ein $\begin{eqnarray*} x\in B\setminus A \end{eqnarray*}$ sowie ein $\begin{eqnarray*} \tilde{f}\in T \end{eqnarray*}$ mit $\begin{eqnarray*} f(x)=0 \end{eqnarray*}$ , und $\begin{eqnarray*} U \end{eqnarray*}$ ergänzt um $\begin{eqnarray*} \tilde{f} \end{eqnarray*}$ hat weniger ausgezeichnete Elemente als $\begin{eqnarray*} U \end{eqnarray*}$ , was gemäß deiner Vorgaben ja nicht sein darf.

Einfaches Beispiel: Es ist $\begin{eqnarray*} G=\{1,2,3,4,5,6,7\} \end{eqnarray*}$ und wir betrachten

$\begin{eqnarray*} T = \{ (1111000), (0111100), (0011110), (0001111) \} \end{eqnarray*}$

(die Funktionen mal kurz durch solche Binärfolgen charakterisiert). Dann besteht die Menge der ausgezeichneten Elemente von $\begin{eqnarray*} T \end{eqnarray*}$ lediglich aus $\begin{eqnarray*} \{4\} \end{eqnarray*}$ , und das ist bereits erreichbar durch $\begin{eqnarray*} U^* = \{ (1111000), (0001111) \} \end{eqnarray*}$ sowie jedes andere $\begin{eqnarray*} U \end{eqnarray*}$ mit $\begin{eqnarray*} U^*\subseteq U\subseteq T \end{eqnarray*}$ .

15.11.2022, 14:08

GMath

Auf diesen Beitrag antworten »

Nein, es trifft es nicht ganz.

Es geht mir nicht nur um die (s.o.) "minimal A-erzeugenden" Untermengen von T.
Sondern:
Ich suche alle Untermengen von T, die nicht erweitert werden können,
sodaß die bereits mit dieser Untermenge ausgezeichneten weniger werden.
Bsp.
Man gehe von irgendeiner Untermenge von T aus.
Sie zeichnet eine bestimmte Menge aus G aus.
Wie lange kann man diese Untermenge um Indikatorfunktionen aus T erweitern,
sodaß jeweils weniger Elemente ausgezeichnet werden?
Wenn nichts mehr geht... das ist eine der Untermengen, die ich suche.

Und später:
Von all' den gefundenen Untermengen diejenigen, die jeweils am meisten auszeichnen.
Um für diese Untermengen dann (aus der Anwendung) jeweils eine neue Indikatorfunktion
zu ersinnen, die die ausgezeichneten möglichst gut separiert.

15.11.2022, 14:18

HAL 9000

Auf diesen Beitrag antworten »

Du sagst sehr schnell "Nein", und das finde ich enttäuschend, weil es mir sagt, dass du nicht gründlich gelesen hast, was ich geschrieben habe. Es geht mir nirgendwo nur um minimale A-erzeugende Untermengen. unglücklich

unglücklich

Ich verabschiede mich vorerst in der leisen Hoffnung, dass du deine Schachtelsätze in greifbareres verwandelst. Denn im Kontrast zu

Zitat:

Original von GMath
Tut mir leid - ich bin nicht so der Formalisierungsbär. Augenzwinkern

Augenzwinkern

bin ich keine Labertasche.

15.11.2022, 14:19

GMath

Auf diesen Beitrag antworten »

Ich habe es so gründlich gelesen wie ich es vermag.
Aber vielleicht habe ich Dich trotzdem nicht richtig verstanden?

Nochmal zu der von Dir beschriebenen Untermenge,
die A auszeichnet.
Sie wäre nur dann eine der von mir gesuchten Untermengen,
wenn man aus ihr kein Element entfernen kann,
ohne dass A anwächst.

"Labertasche" empfinde ich als Beleidigung.
Ich versuche, es so gut wie möglich darzustellen.
Und verbal, weil die Formalisierung bei mir evtl.
neue Fehler/ Unsauberkeiten hereinbringt.

Tut mir leid, dass ich kein Mathematiker bin.

15.11.2022, 14:29

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von GMath
Sie wäre nur dann eine der von mir gesuchten Untermengen,
wenn man aus ihr kein Element entfernen kann,
ohne dass A anwächst.

Wieso das denn jetzt??? Oben hieß es noch, es darf kein Element von T geben, das hinzugefügt (!) zur Funktionenmenge eine kleinere Anzahl ausgezeichneter Elemente ergibt - das ist eine komplett ANDERE Forderung! unglücklich

unglücklich

Wenn du ständig die Rahmenbedingungen änderst, dann ist das nervtötend.

Zitat:

Original von GMath
"Labertasche" empfinde ich als Beleidigung.

Tatsächlich? Und ich den "Formalisierungsbär", wenn du mir auf die Tour kommen willst.

15.11.2022, 14:45

GMath

Auf diesen Beitrag antworten »

Ich habe die Rahmenbedingungen nicht "ständig geändert".
Sondern Du hast da etwas verwechselt.
Zu U hinzufügen - # der ausgezeichneten Elemente kleiner
Aus U entfernen - # der ausgezeichneten Elemente größer.

"Labertasche" ist eine unangebrachte Herabsetzung.
Ich habe es zusätzlich verbalisiert, weil mir mit meinen
begrenzten Fähigkeiten beim Formalisieren zusätzlich
Fehler/ Ungenauigkeiten hereinkommen.

15.11.2022, 15:02

HAL 9000

Auf diesen Beitrag antworten »

Ich hab gar nix verwechselt, sondern mich an deinen Text gehalten. Aber rede nur weiter - ich hab sowieso fertig, wenn du jetzt auch noch den Rechthaber spielst.

Zitat:

Original von GMath
Gesucht
Alle Untermengen von Funktionen mit der Eigenschaft,
dass keine Erweiterung von ihr
die Anzahl der auf 1 gesetzten ("ausgezeichneten") Elemente verringert

15.11.2022, 17:39

mYthos

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
....
....

Zitat:

Original von GMath
"Labertasche" empfinde ich als Beleidigung.

Tatsächlich? Und ich den "Formalisierungsbär", wenn du mir auf die Tour kommen willst.

Bitte an beide: Einen netteren Umgangston bewahren!

mY+

15.11.2022, 18:15

Elvis

Auf diesen Beitrag antworten »

@GMath
Könnten wir noch mal von vorne anfangen ? Bei dem ganzen Hin und Her habe ich den Faden verloren. Möchtest du die neueste Version deines Problems so gut und vollständig formulieren , wie du kannst ? Dann schaue ich mir das gerne noch einmal an - und die lieben Kollegen mögen bitte geduldig schweigen.

15.11.2022, 18:16

GMath

Auf diesen Beitrag antworten »

@mYthos:
Dürfte ich bitte erfahren, wo ich einen "nicht netten" Umgangston bewahrt hätte?

Ich habe gesagt, ich sei nicht so der "Formalisierungsbär",
im Sinne von:
Ich bin nicht so geübt im Formalisieren; das wird dann leicht fehlerhaft.
Und deshalb meine verbalen Beschreibungen.
Das habe ich mehrfach betont.

Anderseits wurde ich als "Labertasche" tituliert.

Wer beleidigt hier wen bitteschön?

15.11.2022, 18:48

mYthos

Auf diesen Beitrag antworten »

Tatsächlich, mit "Formalisierungsbär" hast du dich selbst gemeint und nicht HAL.
Tut mir Leid, das habe ich jetzt im Trubel verwechselt.
Die Kennzeichnung "Umgangston" des Threads werde ich daher wieder entfernen ...

Ich schlage dennoch vor, du nimmst das Angebot zur Hilfe an und formulierst dein Problem so gut und vollständig wie möglich.

mY+

15.11.2022, 18:50

GMath

Auf diesen Beitrag antworten »

@Elvis:

Puhhh...Danke!

OK, ich versuche es nochmal.

Diesmal gehe ich von meiner praktischen Aufgabestellung direkt aus.

Ich habe n Elemente aus einer Grundmenge G (n ca. 1e6).
Außerdem sind t Eigenschaften definiert (t ca. 1e3),
die die Elemente aus G haben können (oder eben nicht).
(Diese Eigenschaften sind dann wohl die "Indikatorfunktionen".)
Nun betrachte ich eine beliebige Teilmenge meiner Eigenschaften,
und dafür diejenigen Elemente aus G, die alle diese Eigenschaften erfüllen.

Wenn ich diese Teilmenge nun um eine weitere Eigenschaft erweitere,
so wird die Anzahl der "Erfüllenden" aus G ja i.d.R. kleiner werden
(weil es eben eine zusätzliche Bedingung gibt).

Mich interessieren nun ALLE diejenigen Teilmengen meiner Eigenschaften,
die um keine Eigenschaft erweitert werden können, sodaß die
"Erfüllenden" weniger werden.
(NB: Ich vermute, dass diese Teilmengen auch gerade diejenigen sind,
die - eben andersrum - um keine Eigenschaft verringert werden können,
ohne dass die "Erfüllenden" mehr werden. Aber da bin ich nicht sicher)
...
OK, wenn ich alle gesuchten Teilmengen meiner Eigenschaften habe,
die obige Bedingung erfüllen, so interessiere ich mich (in der Praxis)
gerade für diejenigen, die die meisten Elemente aus n erfüllen.
Weil die für mich die Kandidaten sind, die es erforderlich machen,
für sie eine neue Eigenschaft zu finden, sodaß die "Erfüllenden"
möglichst von der neuen Eigenschaft halbiert wird.

(Wenn ICH das jetzt in Formeln bringen soll, habt Ihr Spaß! Augenzwinkern

Augenzwinkern

Augenzwinkern

Wie schon gesagt, vermute ich dass es irgendwie mit optimalen Suchbäumen
oder auch mit den div. Cliquen-Problemen zu tun hat.
Aber ich komm' nicht drauf.

Ich frage deshalb, weil es mir früher häufig passiert ist,
dass ich ewig an einem Problem rumgebastelt habe,
bis mir jemand gesteckt hat, dass es eine Instanz von diesem
oder jenem (unter Mathematikern allseits bekannten) Problem ist.
Besonders "witzig", wenn es NP-vollständig o.ä. ist.

So, was hab' ich jetzt wieder verkehrt gemacht? Augenzwinkern

Augenzwinkern

Augenzwinkern

15.11.2022, 20:04

Elvis

Auf diesen Beitrag antworten »

Ich verstehe das Problem noch nicht so recht. Ist es möglich, über das praktische Problem etwas zu sagen ? Oft hilft es, mit Anwendern nicht über ihre Interpretation eines Problems sondern über das Problem selbst zu reden. Wenn es dir nichts ausmacht, lass mich an deiner Realität teilhaben, das darf auch gerne ausführlicher sein ...

15.11.2022, 20:44

GMath

Auf diesen Beitrag antworten »

Danke, gerne smile

smile

Das Witzige ist...
die Herkunft aus der Praxis liegt schon fast komplett da!

Die Grundmenge G sind alle möglichen "Dokumente" (bspw. Dateien etc.).
Die Eigenschaften sind... nun... eben Eigenschaften.
Eigenschaften, die für das jeweilige Problem sinnvoll für die
Objekte definiert werden können.
So eine Art "Label", die an den einzelnen Objekten bappen oder eben nicht.

Will man nun alle Objekte, die irgendeine beliebige Auswahl an Eigenschaften hat.
Also die Schnittmenge.
Nun stelle man sich vor, die jeweilige Schnittmenge ist sehr groß.
Und es gibt keine weitere Eigenschaft (Bedingung), die man hinzunehmen kann,
die Menge zu verkleinern (also eine nähere Spezifizierung).
Weil alle Elemente aus der Resultatschnittmenge jeder der restlichen Bedingungen
entweder alle erfüllen, oder alle nicht erfüllen...
Dann... ist das sehr unschön, weil man eben eine große Anzahl manuell
durchschauen muss, um das zu finden, was man am ehesten sucht.
Es wäre sehr wünschenswert, für diese Auswahl an Eigenschaften
eine weitere Eigenschaft zu finden, die die erfüllende Schnittmenge
möglichst gleichmäßig teilt (was die semantische Interpretation erfordert,
d.h. nicht algorithmisch erfolgen kann).
Hätte man das, so wäre die zu betrachtende Schnittmenge eben nur noch
ungefähr halb so groß.

Das Problem an all' dem nur:
Wie findet man diejenigen Auswahlen an Eigenschaften
(= Untermengen der vorgegebenen Eigenschaften),
die obige Bedingung erfüllen?
Ständig passiert es, dass man/ ich eben ZUFÄLLIG so eine Auswahl trifft,
die eben riesige Mengen an "Erfüllenden" erzeugt.
Es wäre also sehr wünschenswert, wenn man einen Algorithmus hätte,
der einem sagt, welche Auswahlen eine weitere Spezifikation bedürften.

Ein ganz konkretes Beispiel haben wir direkt vor der Nase.
Dieses Forum ist in Sub-Foren unterteilt.
Thematisch ( das wären die "Eigenschafen").
(In diesem Fall baumartig/ hierarchisch,
was bei mir nicht der Fall ist).
Es gibt also für die jeweiligen Untergebiete eigene Äste.
Und ein Ast "Sonstiges".
Sagen wir, der Bereich "Topologie" wäre "vergessen" worden
und würde daher in "Sonstiges" behandelt,
und dort einen erheblichen Anteil ausmachen.

Ich weiß nicht... bin ich jetzt verständlicher?

15.11.2022, 22:55

Elvis

Auf diesen Beitrag antworten »

Mir scheint das Problem deshalb kompliziert zu sein, weil eine Menge von 1000 Eigenschaften $\begin{eqnarray*} 2 ^{1000} \end{eqnarray*}$ Teilmengen hat... Morgen ist auch noch ein Tag...

16.11.2022, 05:09

Elvis

Auf diesen Beitrag antworten »

Wir suchen einen Algorithmus, der eine gute Lösung für ein Problem finden kann. Vielleicht können wir auch einen Algorithmus finden, der eine optimale Lösung für ein Problem finden kann. Das klingt nach Integer Programming. Wir müssen nur noch das Problem in einer dazu passenden Sprache formulieren, d.h. wir müssen ein "lineares" Modell mit Integer-Variablen und einer Zielfunktion modellieren und einen geeigneten Solver benutzen. Unterhalte dich mal mit einem IP- oder MILP-Experten (ich kannte früher mal ein paar Firmen, die sowas gemacht haben, aber ich bin nicht mehr im Geschäft und weiß nicht, ob die Ex-Kollegen noch leben). IP-Probleme und speziell binäre IP-Probleme waren schon vor 20 Jahren gut lösbar, mit einem naiven Modell war Sudoku ein schwieriges Problem, mit geschickter Modellierung in einer Millisekunde gelöst. Falls ich dein Problem verstehen werde und modellieren kann melde ich mich wieder - bitte sage bescheid wenn du auf anderem Wege eine Lösung findest.

16.11.2022, 11:03

Elvis

Auf diesen Beitrag antworten »

Als Unternehmensberater würde ich mich nicht mit deiner abstrakten Beschreibung zufrieden geben. Typische Fragen wären : Wer bist du bzw. welche Rolle spielst du ? Was machst du? Warum machst du das? Wie machst du das? Warum machst du das so? Wozu machst du das? Wer hat etwas von deiner Tätigkeit? Ist dein Arbeitgeber / Auftraggeber / Kunde mit deiner Arbeit / deinem Produkt zufrieden? Wie misst du deinen Erfolg? Kann man das, was du machst einfacher / effizienter / effektiver / erfolgreicher / billiger / ertragreicher machen?

Für das abstrakte Problem habe ich eine simple Lösung. Wenn du zu viel Arbeit hast, arbeite weniger. Verteile die Arbeit auf mehrere Menschen oder Maschinen oder Standorte. Teile die Teilmenge der zu bearbeitenden Objekte zufällig in n gleiche Teile auf und bearbeite nur einen dieser Teile. Die zusätzlich eingeführte Eigenschaft nennen wir "Interesse", und die nicht bearbeiteten Objekte heißen "uninteressant".

16.11.2022, 11:40

GMath

Auf diesen Beitrag antworten »

Danke, aber das ist jetzt schon ziemlich off-topic, oder? Augenzwinkern

Augenzwinkern

Ich "habe das Gefühl", als wenn die von mir gesuchten Untermengen
(der vorgegebenen Indikatorfunktionen) eine Art "Standarduntermengen" sein könnten.
So etwas ähnliches wie ein "Abschluss" bei Relationen, nur eben für "Belegungen".
Was für jemanden, der in dem Gebiet drin ist, auf den ersten Blick klar ist...

In dem Fall müsste ich "nur" diese speziellen Untermengen bestimmen
- mit einem "Standard-Alg." oder eben einer passenden Heuristic.
In der Hoffnung, dass die Anzahl dieser Untermengen qualitativ unter $\begin{eqnarray*} 2^{t} \end{eqnarray*}$ liegt.

Übrigens ist die Formalisierung, die HAL 9000 dankenswerterweise vorgelegt hat,
schon passend (wenn es auch am hinteren Teil von meinem Problem abweicht).
Um die "Abschluss-" Eigenschaft zu fassen bräuchte es dann noch ein paar Quantoren
schätze ich.
Und die Bestimmung der größten Werte für die Mengen der "Ausgezeichneten"
ist dann ja trivial.

16.11.2022, 13:00

Elvis

Auf diesen Beitrag antworten »

Das ist nicht off-topic sondern ganz normale angewandte Mathematik. Bevor ich ein praktisches Problem lösen kann muss ich es verstehen, umformulieren und daraus ein mathematisches Problem machen. Das ist keineswegs die Aufgabe der Anwender, die im allgemeinen nicht genug von Mathematik verstehen, so dass sie keine mathematischen Modelle erstellen können. Wenn du es könntest, wäre sogar HAL 9000 mit dir zufrieden, das ist er aber nicht, also redest du bitte mit mir, oder ich gebe auf. Die Methode "Du als Mathematiker löst bitte meine Probleme, aber ich sage dir nicht, welche ich habe." funktioniert nicht.

16.11.2022, 13:57

GMath

Auf diesen Beitrag antworten »

Ist ja schon gut smile

smile

Du hast ja recht.
Ich stimme doch voll und ganz mit Dir überein. smile

smile

Tatsächlich habe ich ja genau dieselben Erfahrungen
diesbzgl. gemacht wie Du.
Wichtig ist es auch, wirklich passende Ausdrücke zu finden
(also durchaus richtige nicht-mathematische).
Das schlimmste was passieren kann, ist an fehlleitenden
Ausdrücken festzuhalten.

Aber...
Du siehst ja, was passiert ist:
Das hier ist ein MATHEMATIK-Forum, und dann noch das
Subforum Hochschulmathematik.
Da kann man vielleicht zurecht erwarten, dass die
User in der Lage sind und sich die Mühe zu machen
die Formalisierung des Problems selbst zu erledigen.
In dem Sinne kann ich HAL 9000 (nomen est omen)
schon verstehen.

Nur: Wenn ich mir VIEL Mühe gebe, kann ich eine
komplizierte mathematische Formulierung schon verstehen.
Aber sie aufstellen?
Das wird bei mir fehlerhaft ohne Ende.

Und um das jeweilige Problem zu durchdringen,
brauche ich es dann doch, es zu interpretieren.

Allerdings seit Gödel, oder spätestens den 20ern
sind wir ja zu Formeln gekommen, die nicht mehr
interpretierbar/ vorstellbar sind.

Also... ich gebe mir schon Mühe...
aber eben nur im Rahmen meiner Möglichkeiten Augenzwinkern

Augenzwinkern

16.11.2022, 18:18

Elvis

Auf diesen Beitrag antworten »

Das Problem formal beschreiben kann ich versuchen, lösen kann ich es ohne Zusatzinformationen nicht.

Gegeben sei eine Menge $\begin{eqnarray*} X=\{x_1,...,x_n\} \end{eqnarray*}$ von "Objekten" und eine Menge $\begin{eqnarray*} E=\{e_1,...,e_m\} \end{eqnarray*}$ von "Eigenschaften" mit $\begin{eqnarray*} e_i:X\to \{0,1\},x_k\to e_i(x_k) \forall i=(1,...,m) \end{eqnarray*}$ .
Für $\begin{eqnarray*} F\subseteq E, G\subseteq E\backslash F \end{eqnarray*}$ sei $\begin{eqnarray*} V_G:=\{x_k\in X|e_i(x_k)=1(\forall e_i\in F\cup G)\} \end{eqnarray*}$ .
Gesucht sind alle $\begin{eqnarray*} G\subseteq E\backslash F \end{eqnarray*}$ mit $\begin{eqnarray*} \alpha\cdot |V_{\emptyset}|\le |V_G|\le \beta\cdot |V_{\emptyset}| \end{eqnarray*}$ , wobei $\begin{eqnarray*} \alpha<0,5<\beta \end{eqnarray*}$ fest vorgegeben sind.

(Das Problem ist komplex, weil $\begin{eqnarray*} 2^{|E\backslash F|} \end{eqnarray*}$ Teilmengen zu betrachten sind.)
(Habe ich nun wenigstens das Problem verstanden ?)

16.11.2022, 18:47

GMath

Auf diesen Beitrag antworten »

Danke für Deine Mühe!

Was meinst Du mit "Zusatzinformationen"?
Ist das Problem denn nicht vollständig beschrieben?

Zur Formalisierung:
F und G: Meinst Du $\begin{eqnarray*} \forall F, G \end{eqnarray*}$ ?
Was ist V_Durchschnitt? (Habe ich nicht eingegeben bekommen)

16.11.2022, 19:08

GMath

Auf diesen Beitrag antworten »

Moment mal!

Durch Deinen Hinweis auf "fehlende Zusatzinformationen"
schwant mir etwas:
Kann es sein, dass ich hier im Mathe-Forum ganz verkehrt bin?
Mir geht es ja um einen Algorithmus.
Nach Identifikation des Problems.
Und nicht um eine mathematische Lösung (im Sinne einer Formel).

Mit Zusatzinformationen meinst Du wahrscheinlich die e_i?
Aber bspw. die sind ja freie Parameter bei meinem Problem!

Vielleicht sollte ich eher in einem... hmm... Datenbank-
-Forum schauen?
(Da werden sie mich vermutlich auf ein Matheforum verweisen Augenzwinkern

Augenzwinkern

)

16.11.2022, 20:01

Elvis

Auf diesen Beitrag antworten »

Jetzt sind wir glaube ich auf demselben Wissensstand angekommen. Meine sämtlichen Fragen gingen in diese Richtung, und ich bin mit meinem Latein am Ende. So geht es jedem Mathematiker und Informatiker, der sich auf Anwendungen einlässt. Immer wieder spannend, weil Theorie und Praxis nur im Zusammenspiel zum Ziel führen können. Weiterhin viel Erfolg - und lass von dir hören, wenn du einer Lösung näher kommst. Wink

Wink

17.11.2022, 10:02

Elvis

Auf diesen Beitrag antworten »

Anscheinend läuft es auf ein Rucksackproblem hinaus, bei dem die Entscheidungsvariablen die (ca. 1000) Eigenschaften sind, die nicht in F liegen. Als Zielfunktion kann man versuchen, meine letzte Ungleichung zu verwenden, indem man sie geeignet formuliert. Entscheidungsprobleme, die als Optimierprobleme modelliert werden können, sind oft lösbar. Die Größenordnung sollte heutzutage kein Problem sein, die Gestaltung der Zielfunktion hängt natürlich von der jeweiligen Software ab. Ich hatte ja schon vorgeschlagen, einen IP-Experten zu fragen.

Nachtrag als Antwort auf deine Frage.
$\begin{eqnarray*} \emptyset \end{eqnarray*}$ ist die leere Menge, $\begin{eqnarray*} V_{\emptyset} \end{eqnarray*}$ ist die Menge der Objekte, die durch Hinzunahme weiterer Eigenschaften zu F ungefähr halbiert werden soll.

Nachtrag. Wenn du wirklich alle G haben willst, die zu spezifizierende Nebenbedingungen erfüllen, und nicht nur ein "optimales" G, dann hast du ein groesseres Problem. Wer das loesen kann, weiß ich nicht.

17.11.2022, 14:35

GMath

Auf diesen Beitrag antworten »

Recht herzlichen Dank nochmal für Deine Unterstützung!

Mein Unterbewußtsein war fleissig, und ist auf eine einfache Beschreibung für die von mir gesuchten Untermengen gekommen:

Gesucht sind diejenigen Untermengen,
die um keine "Eigenschaft"
- ergänzt werden können, sodaß die Anzahl der "Ausgezeichneten" sich verringert
- verringert werden können, ohne dass die Anzahl der "Ausgezeichneten" sich vergrößert.

D.h. einer dieser Untermengen wäre diejenige, die alle Eigenschaften beinhaltet
abzgl. derjenigen Eigenschaften, die weggenommen werden können, ohne die Anzahl der "Ausgezeichneten" zu vergrößern.

Dass ich von diesen Untermengen dann noch "Extreme" suche, ist dann ja erst der nächste Schritt.

Ich glaube, damit habe ich das Problem jetzt zumindest sauber beschrieben.

(Hoffentlich kommt jetzt (nicht)... "Ach-so! Das ist doch GANZ einfach: ..."

17.11.2022, 15:09

GMath

Auf diesen Beitrag antworten »

Dass die oben beschriebene Untermenge i.allg. nicht die Einzige ist,
sieht man, wenn man
- von der leeren Untermenge ausgeht,
- irgendeine Eigenschaft hinzunimmt, die die "Ausgezeichneten" verringert
und damit solange weitermacht, bis es keine Eigenschaft mehr gibt,
die man hinzunehmen kann, sodaß die "Ausgezeichneten" verringert wird.

Diese Untermenge wird dann i.allg. eine andere sein als die im obigen Post
beschriebene.

Meine Hoffnung ist, dass diese ... "Sackgassen"-Menge der Eigenschaften
irgendwie schon graphentheoretisch o.ä. beschrieben ist,
und kleiner als exponentiell ist.
Falls doch exponenentiell: dass es vielleicht eine Heuristik gibt, besonders
große "Ausgezeichnete" Mengen zu identifizieren.

17.11.2022, 18:28

Elvis

Auf diesen Beitrag antworten »

Ich bin nicht sicher ob ich dich verstehe, aber ich bin sicher, dass du mich nicht verstehst. Mein Vorschlag, ein Optimiersystem zu benutzen und einen geeigneten Experten zu konsultieren bedeutet nicht, dass ein "minimales" oder "maximales" (du sagst "extremes") Ergebnis gesucht wird. Optimiersysteme optimieren nicht die Lösung oder eine Lösung, sondern sie finden ungeheuer schnell eine Lösung, falls es eine gibt (wenn nicht, erkennt das Optimiersystem, dass keine Lösung existiert), und diese gefundene Lösung hat die für die Lösung völlig uninteressante Eigenschaft, dass gleichzeitig eine sogenannte Zielfunktion optimiert (minimiert oder maximiert) wird. Die Optimierung der Zielfunktion ist lediglich eine ganz schlaue Technik, um eine Lösung eines Problems zu finden, das auf andere Art nur sehr schwer zu lösen ist.

Ganz so schnell kann ich dein Problem nicht in meine Sprache umformulieren, aber ich bin fast sicher, dass mein Vorschlag, ein lösbares IP-Problem daraus zu machen, weiterhin bestand hat. Meine Zuversicht beruht darauf, dass die notwendigen Mengenberechnungen auf ein Reihenfolgenproblem, also auf eine gewaltige Baumstruktur führen wird. Das ist typisch für das klassische Rucksackproblem, das heute mit Optimiersystemen gelöst wird. Andere Lösungsalgorithmen sind mir dafür nicht bekannt.

17.11.2022, 19:07

GMath

Auf diesen Beitrag antworten »

Entschuldigung, ich hatte es (vorläufig) zurückgestellt,
rückzumelden, dass ich schon verstanden habe,
was Du in Deinen letzten Posts geschrieben hast:

Ich bin hier im Matheforum offenbar verkehrt,
weil es mir letztlich um einen Algorithmus geht
und nicht um die Lösung einer Gleichung o.ä.

Allerdings stimmt das ja nicht so ganz,
weil ein Algorithmus ist ja nicht "im luftleeren Raum",
sondern ergibt sich aus der vorliegenden Struktur.
Und die möchte ICH erst mal erfassen
(bzw. vermute, dass sie schon irgendwo reinpasst).

Ja, Rucksackproblem... könnte sein.
Das ist auch so ein Stichwort.

Mir war es wichtig, diese letzte saubere Formulierung
meiner vorigen zwei Posts zu präsentieren,
weil es damit verbal richtig beschrieben ist ... (glaube ich).

Ich werde mal schauen, ob ich ein geeignetes Forum finde.

Bei Datenbanken könnte ich tatsächlich richtig sein,
aber da kann ich dann kaum strukturelle Einsichten erwarten.
Und im stackoverflow-Forum wird ein Thread erfahrungsgemäß
sofort geschlossen, wenn man nicht nach einer konkreten
Lösung fragt, sondern etwas erst mal verstehen will.
(Also genau das Gegenteil, was doch sinnvoll wäre...)

17.11.2022, 19:53

Elvis

Auf diesen Beitrag antworten »

Datenbanken halte ich für das falsche Stichwort. Was du m.E. brauchst ist Linear Programming (LP), Nonlinear Programming (NLP), Mixed Integer Programming (MIP), Mixed Integer Nonlinear Programming (MINLP), Integer Programming (IP) oder als Oberbegriffe Optimierung und Operations Research.

27.11.2022, 17:39

GMath

Auf diesen Beitrag antworten »

Ich habe das Problem inzwischen lösen können!

Nach erfolglosen Versuchen in einem Datenbank- und einem amerikanischen
Matheforum (s.u.) habe ich ein bisschen prototypisch mit brute-force,
Stichproben und Monte-Carlo rumprobiert.

Was da dann codiert vor mir lag, eröffnete mir die Sicht auf das Problem.
Wie "befürchtet"... Augenzwinkern

Augenzwinkern

... ziemlich simpel:
https://math.stackexchange.com/questions...weak-partitions

Herzlichen Dank für die Unterstützung, die mich bei der Stange gehalten hat!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »