Benutzer:Robintibor/Informatik/Kombinatorische Optimierung/Mengenüberdeckungsproblem

Das Mengenüberdeckungs-Optimierungsproblem ist ein Problem, an dem man gut verschiedene Ansätze zur Lösung von Optimierungsproblemen zeigen kann.

Beispiel

Stell dir vor, du gehst ins Restaurant und weißt genau, was für Zutaten du heute essen willst - sagen wir Tomaten, Champignons, Ananas und Rucola. Das Restaurant hat verschiedene Gerichte zur Auswahl:

Gericht	Zutaten	Preis
Salat 1	Tomaten, Rucola	2,50
Salat 2	Rucola, Champignons	2,00
Pizza 1	Tomaten, Champignons, Rucola	4,50
Pizza 2	Tomaten, Ananas	3,50
Dessert 1	Ananas	1,50

Du willst nun möglichst wenig Geld ausgeben und dabei alle dir im Kopf vorschwebenden Zutaten gegessen haben. Das ist ein Mengenüberdeckungsoptimierungsproblem.

Definition

Allgemein können wir ein Mengenüberdeckungs-Problem so formulieren:

Gegeben:

• Eine Universalmenge U die abgedeckt werden muss (unsere im Kopf schwebenden Zutaten)
• Teilmengen von U: $S_{1},S_{2},...,S_{n}$ (die Gerichte des Restaurants)
• Kosten der Teilmengen von U (die Preise der Gerichte)

Gesucht:

• Eine Menge von Teilmengen, so dass alle Elemente von U enthalten sind, die möglichst wenig kostet (eine Menge von Gerichten, in der alle von uns gewünschten Zutaten vorkommen und die insgesamt möglichst wenig kostet)

Greedy Algorithmus

Wie könnten wir dieses Problem nun lösen? Eine Möglichkeit für unser Problem ist die folgende: Wir wählen nach und nach immer das Gericht, das pro neuer Zutat am wenigsten kostet. Als erstes wählen wir Salat 2, denn er ist pro neuer Zutat am billigsten: Er enthält 2 neue Zutaten, Rucola und Champignons und kostet 2€, also pro neuer Zutat 1€. Als zweites wählen wir dann Dessert 1, das kostet 1,50€ und hat 1 neue Zutat, die Ananas, kostet also pro neuer Zutat 1,50 €. Als drittes und letztes wählen wir dann:

Test

	Salat 1
	Pizza 1
	Pizza 2

Optimal ist die Lösung allerdings nicht, ....TODO :) TODO auch Greedy Driekter Beweis

Dual Fitting Analysis

Wandeln wir unser Essensproblem leciht ab und erlauben wir es, dass wir Gerichte auch nur teilweise kaufen können, also ein Drittel Pizza, Sieben Neuntel Salat, usw.

Ignorieren, adnere Ideen

Stell dir eine Schule vor, die jedem Schüler etwas mitteilen will, z.B. Aufklärung über einen neuen Aufenthalts- und Spielraum. In der Schule haben sich die Schüler Kurse ausgewählt wie Mathematik, Kunst, Sport oder Geschichte. Um nun jeden Schüler zu erreichen, will die Schule in so vielen Kursen den neuen Aufenthaltsraum vorstellen, bis jeder Schüler etwas über ihn gehört hat. Dabei will sie möglichst wenig Unterricht behindern, und bewertet den Unterricht dabei danach, wie viel die Schüler in ihm lernen, so hält sie es vielleicht für weniger schlimm einen Kurs am Nachmittag zu stören als einen Kurs am Vormittag. Die Aufgabe ist es nun also, die Kurse, in der die Aufklärung stattfindet, so auszuwählen, dass jeder Schüler erreicht wird und dabei möglichst wenig effektive Lernzeit weggenommen wird.