NP-vollständiges Problem < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 14:39 So 11.09.2011 | | Autor: | Harris |
| Aufgabe | Das Multiprozessor-Scheduling-Problem ist wie folgt definiert:
GEGEBEN: Eine Zahl $n$ von Prozessen und deren Laufzeiten [mm] $t_1,...,t_n$; [/mm] eine Zahl $m$ von Prozessoren; eine Deadline $D$.
GESUCHT: Eine Aufteilung der $n$ Prozesse auf die $m$ Prozessoren, so dass die Summe der Laufzeiten der Prozesse, die einem Prozessor zugeordnet sind, jeweils unterhalb von D bleibt.
Die Zahlen [mm] $n,m,t_1,...,t_n,D$ [/mm] sind natürliche Zahlen und in Binärdarstellung gegeben.
Weisen Sie nach, dass das Multiprozessor-Scheduling-Problem NP-vollständig ist, indem Sie ein geeignetes NP-vollständiges Problem auf das Multiprozessor-Scheduling-Problem reduzieren.
Tipp: Es bietet sich folgender Spezialfall einer vereinfachten Variante des Rucksackproblems an. Gegeben: $n$ natürliche Zahlen [mm] $a_1,...,a_n$; [/mm] gesucht: eine Auswahl [mm] $I\subset\{1,...,n\}$ [/mm] so, dass [mm] $\sum_{i\in I} a_i [/mm] = b$ mit [mm] $b=\frac{1}{2}\sum_{i=1}^n a_i$. [/mm] |
Hi!
Ich hätte hier einen Lösungsansatz, weiß aber nicht, ob er richtig ist:
Multiprozessor-Scheduling-Problem (MSP) ist in NP, da eine Lösung gegeben ist, indem man alle Partitionen von [mm] $t_1,...,t_n$ [/mm] betrachtet und auf ihre Gültigkeit (Summe der Laufzeiten einer Partition < $D$) überprüft. Exponentielle Laufzeit [mm] $\Rightarrow [/mm] MSP [mm] \in [/mm] NP$.
NP-härte: (Verwende Spezialfall des Rucksackprolems)
Identifiziere die $n$ Zahlen [mm] $a_1,...,a_n$ [/mm] als $n$ Prozesse. Identifiziere die Anzahl der Prozessoren als $2$. Identifiziere die Deadline $D$ als [mm] $D=\frac{1}{2}\sum_{i=1}^n a_i$.
[/mm]
Durch Lösen des MSP erhält man eine Aufteilung [mm] $I\subset\{1,...,n\}$, [/mm] so dass [mm] $\sum_Ia_i=\frac{1}{2}\sum_{i=1}^na_i=\sum_{\{1...n\}\setminus I}a_i$.
[/mm]
Durch direktes Übertragen (Aufwand [mm] \mathcal{O}(1)) [/mm] der Indexmenge $I$ finden wir nun eine Auswahl der Gegenstände [mm] $a_1,...,a_n$, [/mm] so dass die vereinfachte Variante des Rucksackproblems gelöst ist.
Also gilt $vereinfachtesRucksackProblem [mm] \leq_{p}MSP\Rightarrow$ [/mm] MSP ist NP-vollständig.
Ich hoffe, ich habe das richtig verstanden, dass man bei NP-härte ein bekanntes NP-hartes Problem löst, indem man es auf ein neues Problem (in Poly-Laufzeit) übersetzt, dieses löst und anschließend die Lösung (in Poly-Laufzeit) zurückübersetzt. Stimmt das?
Viele Grüße,
Harris
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Di 13.09.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
