Home | english  | Impressum | Datenschutz | Sitemap | KIT

Software Entwicklung: Automatische Generierung und Auswertung vieler Beispiele für ein ungelöstes Informatik-Problem

Software Entwicklung: Automatische Generierung und Auswertung vieler Beispiele für ein ungelöstes Informatik-Problem
Typ: Praktikum
Dozent:

Prof. Böhm

Es gibt eine faszinierende Liste offener Mathematik- und Informatik-Probleme, s. b.

https://de.wikipedia.org/wiki/Ungel%C3%B6ste_Probleme_der_Mathematik  oder
https://de.wikipedia.org/wiki/Liste_ungel%C3%B6ster_Probleme_der_Informatik .

Um Einsichten zu bekommen, die zur Lösung eines solchen Problems beitragen könnten, ist es möglicherweise hilfreich, sehr viele Beispiele zu haben, die man dann automatisch auswertet. Ihre Aufgabe besteht darin, ein Werkzeug zu bauen, die diese Sicht auf die Dinge für ein konkretes Problem umsetzt, wie folgt:

Ausgangspunkt für diese Aufgabenstellung sind die Total Coloring Conjecture und die Erdős–Faber–Lovász Conjecture. S. b. https://en.wikipedia.org/wiki/Total_coloring und https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Faber%E2%80%93Lov%C3%A1sz_conjecture (dort insbesondere die dritte äquivalente Formulierung der Vermutung "any simple hypergraph with n vertices has chromatic index (edge coloring number) at most n"). -- Bevor Sie weiterlesen, sollten Sie diese Vermutungen verstanden haben.

Wir beschreiben die Aufgabenstellung zunächst ausschließlich anhand der Total Coloring Conjecture.

Wir haben uns unterschiedliche Heuristiken zum Kolorieren von Graphen überlegt und wollen mit Hilfe dieses Praktikums herausfinden, wie gut sie funktionieren, auf welchen Graphen sie wie gut funktionieren, und ob es gar eine Heuristik gibt, für die wir keinen Graph finden können, auf dem sie nicht funktioniert. Dazu sollen Sie eine Software schreiben, die im Wesentlichen Folgendes tut:

  1. Sie generiert viele unterschiedliche Graphen.
  2. Sie wendet unterschiedliche Heuristiken darauf an.
  3. Sie gibt die interessanten/auffälligen Graphen in geeigneter Weise aus.
     

Wir beschreiben das im Folgenden ausführlicher. Zunächst ein paar Definitionen: Die Objekte eines Graphen sind seine Knoten und seine Kanten. D. h. wenn wir im Folgenden sagen, dass wir dem Objekt o eine Farbe zuweisen, kann es sich bei o entweder um einen Knoten oder um eine Kante handeln. "Farbe zuweisen" und "kolorieren" sind für uns Synonyme.

m sei der maximale Grad eines Knotens im Graph. Wir haben also m+2 Farben, im Folgenden repräsentiert als Zahlen, d. h. die Farben sind F = {1, 2, ..., m+2}. Die Heuristiken, die wir uns überlegt haben, haben i. d. R. die Eigenschaft, dass sie ein Objekt nach dem anderen kolorieren. Zu Beginn sind also alle Objekte unkoloriert, während der Ausführung der Heuristik gibt es kolorierte und unkolorierte Objekte, und am Ende -- sollte die Heuristik stets funktionieren -- gibt es nur noch kolorierte Objekte.

Als freie Farben eines Knotens n bezeichnen wir F abzüglich der Farbe von n und der Farben aller zu n adjazenten und bereits kolorierten Kanten. (D. h. diese Definition ist nur für bereits kolorierte Knoten.) Die Menge der möglichen Farben einer (noch nicht kolorierten) Kante e ist der Schnitt der freien Farben der zu e adjazenten Knoten. Die Menge der möglichen Farben einer Menge von Kanten ist die Vereinigung der Mengen der möglichen Farben der Kanten. Sei schließlich K eine Menge von Kanten, die zu einem Knoten adjazent sind. Wir definieren die sogenannte Flexibilität von K wie folgt: flex(K) := Anzahl möglicher Farben von K - |K|.

Die Heuristiken, die betrachtet werden müssen, sind wie folgt:

(1) Greedy:

  • Zuerst werden die Knoten koloriert; danach erfolgt die Kolorierung der Kanten.
  • Die Kolorierung der Knoten darf zum einen die Vorgaben gemäß Total Coloring Conjecture nicht verletzen, d. h. zwei benachbarte Knoten dürfen nicht die gleiche Farbe haben, und die Farben sollen zum anderen möglichst gleich häufig als Knotenfarben vorkommen. (Das lässt sich einfach lösen; wenn Sie sich damit schwertun sollten, verrate ich Ihnen, wie es geht.)
  • Zum Kolorieren der Kanten werden dann alle Knoten einer nach dem anderen durchgegangen, und alle Kanten adjazent zu diesem Knoten, die noch nicht koloriert sind, werden koloriert, eine Kante nach der anderen.
  • Beim Kolorieren der Kanten ist darauf zu achten, dass alle Farben möglichst gleich häufig vergeben werden. Dabei kann die Vergabe einer Farbe an eine Kante das gleiche Gewicht haben wie die Vergabe einer Farbe an einen Knoten, oder wir können diese Fälle unterschiedlich gewichten. Beispiel: Angenommen, ein Knoten und sieben Kanten haben die Farbe 1. Bei gleicher Gewichtung haben acht Objekte die Farbe 1. Wenn wir Knoten beispielsweise doppelt gewichten, haben Objekte mit Gesamtgewicht 9 die Farbe 1. (Diese Gewichtung soll ein exogener Parameter sein.)

(2) Greedy+One:

Wie (1), sobald eine Kante aber nur noch eine mögliche Farbe hat, wird sie mit dieser Farbe koloriert. (D. h. in jedem Schritt werden zu Beginn alle noch nicht kolorierten Kanten durchlaufen, und es wird geschaut, wieviele mögliche Farben jede dieser Kanten hat. Eventuell muss man nicht in jedem Schritt alle dieser Kanten inspizieren; es ist aber derzeit unklar, wieviel eine entsprechende Optimierung bringt. Möglicherweise ist das ein sinnvolles Kann-Kriterium.)

(3) Greedy+Few:

"Ähnlich" zu (1), wenn eine Kante e1 aber gerade mehr mögliche Farben hat als eine Kante e2, darf im nächsten Schritt nicht e1 koloriert werden. (D. h. Kanten mit vergleichsweise wenigen möglichen Farben sind bevorzugt als nächste zu kolorieren.)

(4) Greedy+Set:

  • Es kann vorkommen, dass einzelne Kanten, für sich betrachtet, noch viele mögliche Farben haben, eine Menge von Kanten aber dennoch nicht mehr kolorierbar ist. Beispiel: Ein Knoten hat vier ausgehende unkolorierte Kanten, jede dieser Kanten hat die möglichen Farben {1, 2, 3}.
  • Heuristik deshalb "ähnlich" zu (3): Wir suchen in jedem Schritt, bevor wir Kanten kolorieren, den Knoten n und eine Teilmenge der Kanten adjazent zu n, K, für die flex(K) über alle Knoten hinweg minimal ist. (D. h. es gibt keine andere Menge von Kanten adjazent zu irgendeinem Knoten mit echt kleinerer Flexibilität.) Diese Kanten kolorieren wir dann als nächstes. Für den Fall, dass es mehrere derartige Mengen von Kanten geben sollte, sind Sie gehalten, sich eine oder mehrere Vorgehensweisen zu überlegen, in welcher Reihenfolge vorgegangen werden sollte.

(5) Greedy+Connected:

Wie (4), nur dass es sich bei K nicht um eine Menge von Kanten handeln muss, die zu einem Knoten adjazent sind, sondern um eine beliebige Menge zusammenhängender Kanten. (Diese Variante wird vermutlich bereits auf Graphen mittlerer Größe einen unerträglichen Rechenaufwand verursachen, das ist aber nicht schlimm. Eventuell können wir den Aufwand zumindest deckeln, indem wir uns auf Teilgraphen der Größe k beschränken, mit k, der Anzahl der Kanten, als exogenem Parameter.)

(6+) Kolorierung der Kanten nicht mehr strikt nach der Kolorierung der Knoten:

Mit den bisherigen Heuristiken haben wir erst die Knoten koloriert, dann die Kanten. Sie sollen sich Varianten dieser bisherigen Heuristiken überlegen, für die das nicht der Fall ist (d. h. 'enge' Verzahnung der Kolorierung von Knoten und Kanten ist jetzt gewünscht), sie im Spezifikationsdokument sauber beschreiben und umsetzen.

Ein Kann-Kriterium ist schließlich, dass Sie sich weitere Heuristiken ausdenken und implementieren. (Über diese Heuristiken sollten wir aber sprechen, bevor Sie sich an den detaillierten Entwurf und an die Umsetzung machen, und kurz darüber nachdenken, ob sie sich wirklich aus inhaltlicher Sicht lohnen.)

Es folgen jetzt Erläuterungen zu den Schritten (1) und (3) aus der obigen Aufzählung:

  • In Schritt (1) sollen Graphen mit gleicher Knotenanzahl zufällig generiert werden. Es sollen möglichst alle Knoten den gleichen Grad haben. D. h. die Anzahl der Knoten und der Grad der Knoten sind exogene Parameter in diesem ersten Schritt.
  • Es sollen die o. g. Heuristiken auf die in Schritt (1) erzeugten Graphen angewendet werden -- mit unterschiedlichen Varianten der Ausgabe. Z. B.:

                     * "Alle Graphen, die mit Heuristik x kolorierbar sind."
                     * "Alle Graphen, die nicht mit Heuristik x kolorierbar sind."
                     * "Alle Graphen, die mit Heuristik x, nicht aber mit Heuristik y oder z kolorierbar sind."
                     * "Die k Graphen, bei denen Heuristik k 'am frühesten'/'am spätesten' abbricht."
                       (Es obliegt Ihnen, sich Definitionen von 'früh' auszudenken und umzusetzen -- das sollte aber
                       nicht schwierig sein.)

Für die Festlegung, was genau ausgegeben werden soll, sollen Sie eine vernünftige und möglichst einfache Benutzeroberfläche konzipieren und erstellen.

  • Außerdem interessiert uns, inwieweit das Verhalten der Heuristiken von der Reihenfolge abhängt, in der Knoten und Kanten koloriert werden -- bei manchen Heuristiken ist die nicht spezifiziert. (Es obliegt Ihnen, sich unterschiedliche Policies auszudenken, welche Reihenfolge in solchen Fällen gilt, und geeignete Möglichkeiten der Darstellung der Resultate zu entwickeln. Diese sollen Sie im Spezifikationsdokument beschreiben und in den folgenden Projektphasen umsetzen.)
  • Neben der zufälligen Generierung soll es die Möglichkeit geben, Graphen 'von Hand' zu erzeugen, sei es, dass man sie komplett frei eingibt, sei es, dass man Graphen, die gerade ausgegeben wurden, modifizieren will. Auf diese Graphen sollen dann wieder die Heuristiken anwendbar sein.

All das außerdem für Hypergraphen (ohne Kolorierung der Knoten)! D. h. für die zweite Vermutung bitte diese im Prinzip gleiche Lösung.

Wir hatten im vergangenen Wintersemester eine inhaltlich verwandte PSE-Aufgabe gestellt, die in Breite und Tiefe mit dieser hier vergleichbar ist, und die zwei Teams bearbeitet haben. Da die Bearbeitung in beiden Fällen sehr gut geklappt hat und erfolgreich war, halten wir auch diese vorliegende Aufgabenstellung für in Breite und Tiefe angemessen. Für die Bewertung/Benotung Ihrer Leistung ist nicht relevant, ob mit Hilfe Ihres Werkzeugs tatsächlich interessante Einsichten zustande kommen -- es gelten die üblichen PSE-Bewertungskriterien.