Suchen einer guten linearen Anordnung von Mengen.

03.05.2013, 17:56	Bierdeckel	Auf diesen Beitrag antworten »
Suchen einer guten linearen Anordnung von Mengen. Ich arbeite schon etwas länger an einem Problem bei dem es darum geht eine lineare Anordnung von Mengen zu finden. Mein Ziel ist einen Algorithmus zu entwickeln der das selbstständig macht. Folgende Problemstellung: Wir haben eine (beliebige) Zahl von (beliebigen) Mengen. Sie könnten so aussehen. $\begin{eqnarray} A= \lbrace a,b,c,d,e,f,g \rbrace \end{eqnarray}$ $\begin{eqnarray} B= \lbrace c,e,a,x \rbrace \end{eqnarray}$ $\begin{eqnarray} C= \lbrace a,z,h \rbrace \end{eqnarray}$ $\begin{eqnarray} D= \lbrace a,b \rbrace \end{eqnarray}$ Das Ziel ist jetzt die Elemente dieser Mengen so linear anzuordnen, dass Die Elemente einer Menge nicht getrennt werden. Kein Element doppelt aufgeschrieben werden muss. Leider ist es generell nicht möglich eine solche Anordnung zu finden. Es gibt Konstellationen in denen diese beiden Bedingungen unerfüllbar sind. In diesem Fall ist es ausreichend wenn so wenige Mengen wie möglich getrennt werden. Eine gute Lösung für das obige Problem wäre diese Anordnung: $\begin{eqnarray} (z,h,a,b,d,f,g,c,e,x) \end{eqnarray}$ Dabei wurde zuerst Menge $\begin{eqnarray} C \end{eqnarray}$ gefolgt von $\begin{eqnarray} D \end{eqnarray}$ und $\begin{eqnarray} A \end{eqnarray}$ gereiht. Menge $\begin{eqnarray} B \end{eqnarray}$ wurde aufgespalten (A wurde zu beginn der Sequenz verwendet) Ich denke, dass die Matrix aller Durchschnitte von Mengen hilfreich sein müßte, ich hab aber noch nicht herausgefunden wie eine gute Lösung damit zusammenhängt. $\begin{eqnarray} \begin{pmatrix} a,b,c,d,e,f,g & a,c,e & a & a,b \\ a,c,e & c,e,a,x & a & a \\ a & a & a,z,h & a\\ a,b & a & a & a,b \end{pmatrix} \end{eqnarray}$ Ich poste das hier, weil ich hoffe jemand kann mir einen hilfreichen Mathematischen Satz oder ein Paper nennen, der/das diesem Problem die Zähne zieht, oder zumindest hinweise liefert. Brute Force fällt ja wegen der exponentiellen Problemkomplexität von vornherein flach.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »