Skip to content. | Skip to navigation

Personal tools

Sections
You are here: Home / Publikationen / Informatik / Theorie und Praxis der automatischen Stundenplanerstellung / Diplomarbeit / html / Die Komplexität von Teilproblemen

Die Komplexität von Teilproblemen

next up previous contents
Next: Der Normalfall Up: Komplexität des Problems Previous: Randomisierte Algorithmen/Heuristiken

Die Komplexität von Teilproblemen

  Insbesondere im Rahmen eines interaktiven Systems ist die Komplexität von Teilproblemen interessant, da seitens des Benutzers häufig verlangt wird, lokale Widersprüche aufzuheben. Im folgenden wird daher immer ein Teil des Problems bzw. ein bestimmter Parameter als konstant angenommen.

Festhalten des Zeitpunkts

  Geht es lediglich darum, die zu einem bestimmten Zeitpunkt angeforderten Ressourcen zu verteilen, so kann dies durch einfaches Matching geschehen: Siehe Abschnitt 8.4.3.
Abhängigkeiten zwischen flexiblen Ressourcen - wie z.B. Bevorzugung von benachbarten Klassenräumen - können aber bereits nicht mehr in polynomieller Zeit aufgelöst werden. Es gibt auch keinen approximativen Algorithmus, da dieses Problem durch Komplementbildung in das der maximalen unabhängigen Teilmenge überführt werden kann. Sei ein Graph gegeben, in dem eine Clique gegebener Größe u zu finden ist: Assoziiert man jeden Knoten mit einer flexiblen Ressource und legt die Vorlieben so fest, daß zwei Ressourcen einander bevorzugen wenn die entsprechenden Kanten verbunden sind, so korrespondiert offenbar eine entsprechende Clique im Graphen zu einer optimalen Ressourcenzuteilung von u Objekten.
Kann man die Objekte aber nach Wichtigkeit der Wünsche so aufteilen, daß die jeweiligen Gruppen innerhalb keine Abhängigkeiten aufweisen, so besteht auf jeder Ebene nur das Problem, die u bevorzugtesten Elemente auszuwählen (a). Sind diese zusätzlich nur von einigen Elementen der höheren Ebene abhängig, läßt sich das Ganze durch Netzwerkflüsse behandeln (b)gif. Das oben angesprochene Matching wird dann ein Spezialfall dieses Verfahrens mit zwei Ebenen:

  tex2html_wrap5536

Allerdings zeigt dieses Teilproblem ein Verhalten, das dem von 2SAT bzw. von Max2SAT ähnelt: Ist eine Menge von Stunden gegeben, der Ressourcen zugeteilt werden sollen, bei der aber nicht gesichert ist, daß wirklich jede Stunde mit Räumen o.ä. versorgt werden kann, so ist das Problem, eine optimale Lösung zu finden, tex2html_wrap_inline5146 - hart und nicht konstant approximierbar. Denn: Gegeben ein Graph, in dem eine maximale unabhängige Menge gefunden werden soll, assoziiere jeden Knoten mit einer Stunde, füge für jede Kante einen gesonderten Raum hinzu, und stelle die Anforderung, daß die beiden inzidenten Stunden genau diesen Raum brauchen. Offenbar korrespondiert dann eine maximale Zahl verteilter Stunden zu einer maximalen unabhängigen Knotenmenge.
Während das Entscheidungsproblem also in tex2html_wrap_inline5238 liegt, ist das Optimierungsproblem sehr schwer.gif

Eine ebenfalls tex2html_wrap_inline5146 -harte Variante ergibt sich, wenn man verlangt, daß zu allen Zeiten die gleichen Ressourcen, z.B. Räume, verwandt werden sollen. Hier erhält man wieder ein allgemeines Graphenfärbungsproblem, indem man die Räume als Farben und die Veranstaltungen als Knoten interpretiert, die genau dann verbunden sind, wenn sich diese zu irgendeinem Zeitpunkt überschneiden.

Festhalten eines Objekts

Wie [dW85] zeigt, kann auch unter der Annahme von Abwesenheitszeiten der Plan für eine einzelne Klasse optimal durch Netzwerkflüsse gelöst werden.

tex2html_wrap5538

Das gleiche kann natürlich auch für Lehrer, Räume etc. durchgeführt werden.

Festhalten der Blockungen

  Hat man die Schulstunden den Zeitstunden zugeordnet, so läßt das Permutieren der Zeitstunden die Gültigkeit der harten Nebenbedingungen unberührt. Betrachtet man hier zunächst nur die indirekten Nebenbedingungen, so erhält man in der einfachsten Form - nur Relationen zwischen aufeinanderfolgenden Stunden - eine Variante des Problems des Handlungsreisenden. Will man z.B. den Wochenplan einer Klasse unter dem Aspekt modifizieren, daß die zurückzulegende Wegstrecke minimiert wird, so erhält man eventuell noch eine euklidische Metrik, so daß Approximationsalgorithmen wie der von ARORA [Vyg] anwendbar bleiben. Kommen dazu noch Regelungen wie die, daß auf eine Schwimmstunde z.B. nicht Mathematik folgen sollte, so müssen die Entfernungen in diesem Problem noch nicht einmal mehr der Dreiecksungleichung genügen, was dazu führt, daß noch nicht einmal eine Approximation bis auf einen konstanten Faktor möglich ist [Jun90]. Es können zudem natürlich auch mehrere Stunden übergreifende Relationen auftreten.


next up previous contents
Next: Der Normalfall Up: Komplexität des Problems Previous: Randomisierte Algorithmen/Heuristiken

(c) Martin Loehnertz 1999