IS
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Independent Set
Hallo,
im Vorlesungsskript tauchen ja folgende NP-schweren-Probleme nicht auf:
- Independent Set
- Rucksack
- Bin Packing.
In einen der alt Klausuren war aber nach IS gefragt.
Hat jemand eine Definition der obigen Probleme im Wanka-Stil (das ist: <> + Mengen “|” Zermelo Fränkel Schreibweise )
Siehe Übungsblatt 6:
Das Independent Set Problem ist die Sprache
IS = {<G,k> | G ist ein ungerichteter Graph, k ∈ IN, G hat eine unabhängige Menge U mit |U| = k}.
Eine Teilmenge U ⊆ V der Knotenmenge heißt unabhängige Menge (engl.: independent set), wenn es in der Kantenmenge E keine Kanten zwischen Knoten aus U gibt.
IS = {<G,k>|G ist ungerichteter Graph, k ∊ N, G hat eine unabh. Menge U mit |U|=k}
Bin Packing und Rucksackproblem hatten wir soweit ich weiß weder in der Vorlesung noch in den Übungen definiert(?).
Oder meinst du mit Bin Packing das binary programming?
Rucksack (packen) = Bin Packing? Edit: Rucksack ist wohl gleich Knapsack, da gibt’s noch verschiedene Wertigkeiten - was wir wohl nicht brauchen dürften.
Folgendes steht dazu in meiner Mitschrift:
Die a_i sind wohl die Gewichte. Ich frag mich nur, ob man das normalerweise nicht noch maximieren will…
Edit2: Der Lösungsvektor wird durch die \alpha_i hinter dem Existenzquantor beschrieben, nicht die a_i, denn das sind ja die (bekannten) Gewichte.
Der Teil mit a_1, …, a_n sollten alphas sein, oder? Ansonsten, wo kommen die her?
Die as sagen, ob das i-te (i = 1…n) Element in deinem Rucksack ist, daher multiplizierst du die entsprechenden Gewichte in der Summe mit 0 oder 1.
Und woher kommen dann die alphas? Die müssen doch irgendwie auch mit ein Wort der Sprache …
In meiner Mitschrift steht folgendes:
Als Erklaerung vll noch: die Formel mit den alpha’s sind die Bedingung, die erfuellbar sein muss, wie zB bei SAT der Teil mit „Phi ist erfuellbare KNF“.
Ich hab gerade festgestellt, dass die a_i bei mir sowohl die gegebenen Gewichte, als auch die gesuchten 0,1er waren - und nun korrigiert: Gesucht sind die alphas, und nur die sind aus {0,1}. Trotzdem fehlt mir da irgendwas, denn momentan ist das Problem immer mit \vec \alpha = \vec 0 (also dem Nullvektor) erfüllbar…
In den Vorlesungsmitschriften der alten Semester (BFS.pdf, BFS_VL_Master.pdf) steht die Formel in einer kleinen Abaenderung:
Das wuerde das Problem mit dem Nullvektor loesen.
-chris
Das kommt dem Sinn des Rucksackproblems auch irgendwie näher…
Nur bedingt.
Beim Rucksackproblem willst du ja den Inhalt des Rucksacks maximieren, der Inhalt muss allerdings nicht gleich der maximalen Kapazitaet des Rucksacks sein (weil das Aufgrund von Verschnitt uU gar nicht moeglich ist).
Deswegen wird hier wahrscheinlich auch <= gewaehlt.
Dein Ziel beim Rucksackproblem ist ja normalerweise, dass du den Wert des Inhalts maximieren willst () unter der Bedingung
-chris