Suche Algorithmus um aus einer Menge von Intervallen die maximale Teilmenge bei der es keine Überschneidungen gibt

Hi

ich habe mehrere Intervalle und möchte jetzt die maximale Teilmege finden bei
der sich aber keine Intervalle überschneiden dürfen. Gibt es einen solchen Algorithmus? Bei meiner Suche bin ich auf das "Subset Sum" Problem gestoßen. Aber das ist nicht was ich meine. Kennt jemand zufällig solch einen Algorithmus?

mfg

Jester

Ich kann Dir zumindest sagen, dass Dein Problem auf den klangvollen Namen "Maximum (Weight) Independent Set in Interval Graphs" hört.

Ich vermute, dass ein relativ einfaches dynamisches Programm funktionieren dürfte. Sortiere die Intervalle nach ihrem rechten Endpunkt und berechne für jeden dieser Endpunkte die beste Lösung bei der nur Intervalle die vollständig links des aktuellen Endpunkts liegen erlaubt sind.

Immer wenn Du den nächsten Endpunkt (sagen wir der heißt r_x) betrachtest gibt es zwei Möglichkeiten, entweder du nimmst das entsprechende Intervall I_x = (l_x,r_x) mit dazu, oder eben nicht. Die jeweils beste Gesamtkombination lässt sich dann aus den vorher berechneten Lösungen zusammenbauen: Wenn das Intervall I_x nicht mit aufgenommen wird, dann ist es einfach die bisherige beste Lösung. Wenn es aufgenommen wird, dann muß es kombiniert werden mit der bisher besten Lösung, die nur Intervalle benutzt, die links von l_x liegen. Den besseren dieser beiden Werte merkst Du Dir als beste Lösung, die Intervalle benutzt, die links von r_x liegen. Im Prinzip füllst Du also nur ein 1-dimensionales Array aus. Das ganze dürfte also in Linearzeit laufen. Außerdem funktioniert es auch dann noch, wenn Du nicht die Anzahl der Intervalle, sondern deren Gesamtlänge maximieren willst.

Danke für die Informationen, das hört sich ja interessant an. Google liefert für "Maximum (Weight) Independent Set in Interval Graphs" nicht soviele Treffer gibt es irgendwo ein Dokument was den Zusammenhang mit den Graphen weiter erläutert ?

Christoph

Fourierpolynom schrieb:

Danke für die Informationen, das hört sich ja interessant an. Google liefert für "Maximum (Weight) Independent Set in Interval Graphs" nicht soviele Treffer gibt es irgendwo ein Dokument was den Zusammenhang mit den Graphen weiter erläutert ?

Der Zusammenhang ist: Jedes Intervall steht für einen Knoten. Zwei Knoten sind durch eine Kante verbunden genau dann, wenn sich die korrespondierenden Intervalle überschneiden. Man bekommt dadurch die sogenannten "Intervallgraphen". Auf denen sind einige Probleme sehr effizient lösbar, die auf allgemeinen Graphen NP-vollständig sind.

Was ein independent set ist, steht auch auf Wikipedia: Das ist eine Knotenmenge, bei der keine zwei Knoten adjazent sind. Im Fall von Intervallgraphen bedeutet "keine zwei Knoten sind adjazent" gerade "keine zwei Intervalle überlappen sich".

Danke fuer die Antwort!