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 w 1 w 2 w n 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 x 1 x n 0 1 displaystyle x 1 dotsc x n in 0 1 nbsp die j 1 n w j x j displaystyle sum j 1 n w j x j nbsp maximieren unter der Nebenbedingung j 1 n w j x j 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 C 1 C 2 C m displaystyle C 1 wedge C 2 wedge ldots C m nbsp mit den Variablen x 1 x n displaystyle x 1 ldots x n nbsp werden die Dezimalzahlen w 1 w 2 n 2 m 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 x i displaystyle x i nbsp und x i 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 x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 3 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 x 1 displaystyle x 1 nbsp x 2 displaystyle x 2 nbsp x 3 displaystyle x 3 nbsp C 1 displaystyle C 1 nbsp C 2 displaystyle C 2 nbsp C 3 displaystyle C 3 nbsp w 1 displaystyle w 1 nbsp 1 0 0 1 1 0w 2 displaystyle w 2 nbsp 1 0 0 0 0 1w 3 displaystyle w 3 nbsp 0 1 0 0 1 0w 4 displaystyle w 4 nbsp 0 1 0 1 0 1w 5 displaystyle w 5 nbsp 0 0 1 1 1 0w 6 2 n displaystyle w 6 2n nbsp 0 0 1 0 0 1w 7 displaystyle w 7 nbsp 0 0 0 1 0 0w 8 displaystyle w 8 nbsp 0 0 0 2 0 0w 9 displaystyle w 9 nbsp 0 0 0 0 1 0w 10 displaystyle w 10 nbsp 0 0 0 0 2 0w 11 displaystyle w 11 nbsp 0 0 0 0 0 1w 12 2 n 2 m 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 w 1 100110 displaystyle w 1 100110 nbsp besagt dass x 1 displaystyle x 1 nbsp in den Klauseln C 1 displaystyle C 1 nbsp und C 2 displaystyle C 2 nbsp aber nicht C 3 displaystyle C 3 nbsp vorkommt w 2 displaystyle w 2 nbsp setzt das fur x 1 displaystyle overline x 1 nbsp um w 3 displaystyle w 3 nbsp fur x 2 displaystyle x 2 nbsp w 4 displaystyle w 4 nbsp fur x 2 displaystyle overline x 2 nbsp etc Die Zeilen w 2 n 1 displaystyle w 2n 1 nbsp bis w 2 n 2 m 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 w 1 displaystyle w 1 nbsp oder w 2 displaystyle w 2 nbsp w 3 displaystyle w 3 nbsp oder w 4 displaystyle w 4 nbsp etc ausgewahlt werden kann wodurch in der Formel x i 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 x i displaystyle x i nbsp true die Zahl w 2 i 1 displaystyle w 2i 1 nbsp auf falls x i displaystyle x i nbsp false die Zahl w 2 i 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 w i displaystyle w i nbsp zunachst jeweils genau ein w 1 displaystyle w 1 nbsp oder w 2 displaystyle w 2 nbsp w 3 displaystyle w 3 nbsp oder w 4 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