www.wikidata.de-de.nina.az

Teilsummenproblem Das auch Untermengensummenproblem engl subset sum problem ist ein berühmtes Problem der Informatik und

Teilsummenproblem

Das Teilsummenproblem (auch Untermengensummenproblem, engl. subset sum problem) ist ein berühmtes Problem der Informatik und des Operations Research. Es ist ein spezielles Rucksackproblem.

Problembeschreibung Bearbeiten

Gegeben sei eine Menge von ganzen Zahlen . Gesucht ist eine Untermenge, deren Elementsumme maximal, aber nicht größer als eine gegebene obere Schranke ist (oft ist auch gefragt, die Schranke exakt zu erreichen).

Formal: Gesucht sind , die maximieren unter der Nebenbedingung .

NP-Vollständigkeit Bearbeiten

Das Problem ist NP-vollständig und somit vermutlich nicht effizient lösbar. Es kann mit der Branch-and-Bound-Methode gelöst werden.

Der Beweis der NP-Schwere erfolgt durch eine Reduktion von 3-SAT. Für eine gegebene Klauselmenge mit den Variablen werden die Dezimalzahlen sowie die Schranke anhand einer Tabelle konstruiert. Es wird vorausgesetzt, dass keine Klauseln vorhanden sind, die und gleichzeitig enthalten; dies ist keine Einschränkung, da eine solche Klausel immer erfüllt wäre und somit weggelassen werden kann, ohne den Sinn zu verändern.

Beispielsweise wird die Formel wie folgt verarbeitet (eine Erklärung folgt nach der Tabelle).

1 0 0 1 1 0
1 0 0 0 0 1
0 1 0 0 1 0
0 1 0 1 0 1
0 0 1 1 1 0
0 0 1 0 0 1
0 0 0 1 0 0
0 0 0 2 0 0
0 0 0 0 1 0
0 0 0 0 2 0
0 0 0 0 0 1
0 0 0 0 0 2
1 1 1 4 4 4
  • Die Ziffern einer Zeile werden als Stellen einer Dezimalzahl aufgefasst.
  • Die ersten 2n Zeilen sind lediglich eine Codierung der Formel selbst: besagt, dass in den Klauseln und , aber nicht vorkommt. setzt das für um, für , für etc.
  • Die Zeilen bis sind "Korrekturzeilen", die nur auf der Diagonalen jeweils abwechselnd den Wert 1 oder 2 haben.
  • Die Zahl besteht nur aus n Einsen und m Vieren. Dies bewirkt, dass bei Addition der Spaltenwerte, an den ersten n Stellen nur entweder oder ; oder etc. ausgewählt werden kann, wodurch in der Formel auf true oder false gesetzt wird. Die Vieren sind so gewählt, dass zusätzlich zu den beiden Korrekturwerten, die zusammen nur 1+2=3 ergeben, noch mindestens eine der Variablen in den Klauseln vorhanden sein muss, um auf 4 zu kommen. Sind mehr Variablen verfügbar, können entsprechend Korrekturzeilen weggelassen werden.

Besitzt nun die boolesche Formel eine erfüllende Belegung, so nehmen wir falls =true die Zahl auf; falls =false die Zahl . Damit sind schon die Einsen in korrekt. Da alle Klauseln erfüllt sind, ist in den gerade hinzugefügten Zahlen in jeder Klausel mindestens eine erfüllte Variable vorhanden, somit sind die Spaltensummen im rechten Teil schon mindestens 1 und höchstens 3. Nun muss man nur noch die Korrekturvariablen geeignet wählen, um auf 4 zu kommen. Mit der konstruierten Menge ist es so möglich, genau zu erreichen, wenn die Formel erfüllbar ist.

Wenn nun genau erreicht werden kann, so muss die Teilmenge der zunächst jeweils genau ein oder ; oder etc. enthalten, weil sonst die Einsen in nicht erfüllt wären. Somit ist gewährleistet, dass eine Variable tatsächlich true oder false (und nicht keins oder beides) ist. Durch diese Auswahl der Teilmenge muss dann auch jede Klausel erfüllt sein, denn wenn in einer Klausel keine Variable durch die Belegung erfüllt wäre, so würde die Addition nicht die notwendige Vier in ergeben. Daher ist die boolesche Formel insgesamt erfüllbar.

Literatur Bearbeiten

  • Soma, Nei Y. Toth, Paolo: An exact algorithm for the subset sum problem. European Journal of Operational Research 136 S. 57–66
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, und Clifford Stein. Algorithmen – Eine Einführung. Oldenbourg-Verlag, 2004. ISBN 3-486-27515-1. Seiten 1017ff.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das Teilsummenproblem auch Untermengensummenproblem engl subset sum problem ist ein beruhmtes Problem der Informatik und des Operations Research Es ist ein spezielles Rucksackproblem Problembeschreibung BearbeitenGegeben sei eine Menge von ganzen Zahlen I w1 w2 wn displaystyle I w 1 w 2 dotsc w n nbsp Gesucht ist eine Untermenge deren Elementsumme maximal aber nicht grosser als eine gegebene obere Schranke c displaystyle c nbsp ist oft ist auch gefragt die Schranke c displaystyle c nbsp exakt zu erreichen Formal Gesucht sind x1 xn 0 1 displaystyle x 1 dotsc x n in 0 1 nbsp die j 1nwjxj displaystyle sum j 1 n w j x j nbsp maximieren unter der Nebenbedingung j 1nwjxj c displaystyle sum j 1 n w j x j leq c nbsp NP Vollstandigkeit BearbeitenDas Problem ist NP vollstandig und somit vermutlich nicht effizient losbar Es kann mit der Branch and Bound Methode gelost werden Der Beweis der NP Schwere erfolgt durch eine Reduktion von 3 SAT Fur eine gegebene Klauselmenge C1 C2 Cm displaystyle C 1 wedge C 2 wedge ldots C m nbsp mit den Variablen x1 xn displaystyle x 1 ldots x n nbsp werden die Dezimalzahlen w1 w2n 2m displaystyle w 1 ldots w 2n 2m nbsp sowie die Schranke c displaystyle c nbsp anhand einer Tabelle konstruiert Es wird vorausgesetzt dass keine Klauseln vorhanden sind die xi displaystyle x i nbsp und xi displaystyle overline x i nbsp gleichzeitig enthalten dies ist keine Einschrankung da eine solche Klausel immer erfullt ware und somit weggelassen werden kann ohne den Sinn zu verandern Beispielsweise wird die Formel x1 x2 x3 x1 x2 x3 x1 x2 x3 displaystyle x 1 vee overline x 2 vee x 3 wedge x 1 vee x 2 vee x 3 wedge overline x 1 vee overline x 2 vee overline x 3 nbsp wie folgt verarbeitet eine Erklarung folgt nach der Tabelle x1 displaystyle x 1 nbsp x2 displaystyle x 2 nbsp x3 displaystyle x 3 nbsp C1 displaystyle C 1 nbsp C2 displaystyle C 2 nbsp C3 displaystyle C 3 nbsp w1 displaystyle w 1 nbsp 1 0 0 1 1 0w2 displaystyle w 2 nbsp 1 0 0 0 0 1w3 displaystyle w 3 nbsp 0 1 0 0 1 0w4 displaystyle w 4 nbsp 0 1 0 1 0 1w5 displaystyle w 5 nbsp 0 0 1 1 1 0w6 2n displaystyle w 6 2n nbsp 0 0 1 0 0 1w7 displaystyle w 7 nbsp 0 0 0 1 0 0w8 displaystyle w 8 nbsp 0 0 0 2 0 0w9 displaystyle w 9 nbsp 0 0 0 0 1 0w10 displaystyle w 10 nbsp 0 0 0 0 2 0w11 displaystyle w 11 nbsp 0 0 0 0 0 1w12 2n 2m displaystyle w 12 2n 2m nbsp 0 0 0 0 0 2c displaystyle c nbsp 1 1 1 4 4 4Die Ziffern einer Zeile werden als Stellen einer Dezimalzahl aufgefasst Die ersten 2n Zeilen sind lediglich eine Codierung der Formel selbst w1 100110 displaystyle w 1 100110 nbsp besagt dass x1 displaystyle x 1 nbsp in den Klauseln C1 displaystyle C 1 nbsp und C2 displaystyle C 2 nbsp aber nicht C3 displaystyle C 3 nbsp vorkommt w2 displaystyle w 2 nbsp setzt das fur x1 displaystyle overline x 1 nbsp um w3 displaystyle w 3 nbsp fur x2 displaystyle x 2 nbsp w4 displaystyle w 4 nbsp fur x2 displaystyle overline x 2 nbsp etc Die Zeilen w2n 1 displaystyle w 2n 1 nbsp bis w2n 2m displaystyle w 2n 2m nbsp sind Korrekturzeilen die nur auf der Diagonalen jeweils abwechselnd den Wert 1 oder 2 haben Die Zahl c displaystyle c nbsp besteht nur aus n Einsen und m Vieren Dies bewirkt dass bei Addition der Spaltenwerte an den ersten n Stellen nur entweder w1 displaystyle w 1 nbsp oder w2 displaystyle w 2 nbsp w3 displaystyle w 3 nbsp oder w4 displaystyle w 4 nbsp etc ausgewahlt werden kann wodurch in der Formel xi displaystyle x i nbsp auf true oder false gesetzt wird Die Vieren sind so gewahlt dass zusatzlich zu den beiden Korrekturwerten die zusammen nur 1 2 3 ergeben noch mindestens eine der Variablen in den Klauseln vorhanden sein muss um auf 4 zu kommen Sind mehr Variablen verfugbar konnen entsprechend Korrekturzeilen weggelassen werden Besitzt nun die boolesche Formel eine erfullende Belegung so nehmen wir falls xi displaystyle x i nbsp true die Zahl w2i 1 displaystyle w 2i 1 nbsp auf falls xi displaystyle x i nbsp false die Zahl w2i displaystyle w 2i nbsp Damit sind schon die Einsen in c displaystyle c nbsp korrekt Da alle Klauseln erfullt sind ist in den gerade hinzugefugten Zahlen in jeder Klausel mindestens eine erfullte Variable vorhanden somit sind die Spaltensummen im rechten Teil schon mindestens 1 und hochstens 3 Nun muss man nur noch die Korrekturvariablen geeignet wahlen um auf 4 zu kommen Mit der konstruierten Menge ist es so moglich genau c displaystyle c nbsp zu erreichen wenn die Formel erfullbar ist Wenn nun c displaystyle c nbsp genau erreicht werden kann so muss die Teilmenge der wi displaystyle w i nbsp zunachst jeweils genau ein w1 displaystyle w 1 nbsp oder w2 displaystyle w 2 nbsp w3 displaystyle w 3 nbsp oder w4 displaystyle w 4 nbsp etc enthalten weil sonst die Einsen in c displaystyle c nbsp nicht erfullt waren Somit ist gewahrleistet dass eine Variable tatsachlich true oder false und nicht keins oder beides ist Durch diese Auswahl der Teilmenge muss dann auch jede Klausel erfullt sein denn wenn in einer Klausel keine Variable durch die Belegung erfullt ware so wurde die Addition nicht die notwendige Vier in c displaystyle c nbsp ergeben Daher ist die boolesche Formel insgesamt erfullbar Literatur BearbeitenSoma Nei Y Toth Paolo An exact algorithm for the subset sum problem European Journal of Operational Research 136 S 57 66 Thomas H Cormen Charles E Leiserson Ronald L Rivest und Clifford Stein Algorithmen Eine Einfuhrung Oldenbourg Verlag 2004 ISBN 3 486 27515 1 Seiten 1017ff Abgerufen von https de wikipedia org w index php title Teilsummenproblem amp oldid 238848923