בעיית הסכומים החלקיים

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

במדעי המחשב, בעיית הסכום החלקי (Subset Sum Problem) היא בעיה חשובה בתורת הסיבוכיות ובקריפטוגרפיה. הבעיה היא כזו: בהינתן קבוצה של מספרים שלמים, האם קיימת תת-קבוצה לא ריקה שלה שסכום איבריה הוא אפס? לדוגמה, בהינתן הקבוצה {7-,3-,2-,8,5} כקלט לבעיה, התשובה תהיה חיובית, והקבוצה שסכומה אפס תהיה {2-,3-,5}. בעיה זו היא NP-שלמה.

בעיה שקולה לבעיה זו היא כדלקמן: בהינתן קבוצת מספרים שלמים I, ומספר נוסף s, האם קיימת תת-קבוצה לא ריקה של I שסכום איבריה הוא s?

ניתן גם לחשוב על בעיית הסכום החלקי כעל מקרה מיוחד של בעיית תרמיל הגב.[1] מקרה מיוחד של בעיה זו היא בעיית החלוקה(אנ'), בה נשאלת השאלה האם קיימת תת-קבוצה שסכום איבריה שווה לסכום כל האיברים שאינם בתת-קבוצה זו.

אלגוריתמים לפתרון הבעיה

בעיה זו היא NP-שלמה, לכן עדיין לא נמצא אלגוריתם הפותר אותה בזמן יעיל. לעומת זאת, ניתן לפתור את הבעיה באמצעות אלגוריתם פסאודו פולינומי, ובאמצעות אלגוריתם פולינומי מקרב.

אלגוריתם לפתרון בזמן אקספוננציאלי

יש מספר דרכים לפתור את בעיית הסכום החלקי בזמן אקספוננציאלי בגודל הקבוצה. האלגוריתם הנאיבי ביותר יבדוק את כל תתי הקבוצות האפשריות, ויבדוק האם סכומן מתאים להגדרת הבעיה. זמן הריצה של אלגוריתם כזה יהיה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(2^{n}n)} , שכן ישנן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^{n}} תתי קבוצות שהאלגוריתם יבדוק, ובכל קבוצה כזו יש לכל היותר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} איברים שהאלגוריתם יסכום.

קיים גם אלגוריתם טוב יותר שרץ בזמן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(2^{\frac{n}{2}})} שהוצג לראשונה על ידי הורוביץ וסהני(אנ') בשנת 1972. האלגוריתם פועל באופן הבא:

  1. נחלק את הקלט לקבוצות T ו-U בגודל כל אחת.
  2. נחשב את הקבוצות A ו-B כאשר A היא קבוצת כל הזוגות הסדורים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a_i,p_i)} כך ש-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p_i} הוא קידוד של בחירת איברים ב-T שסכומם הוא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_i} ובאותו אופן B היא קבוצת הזוגות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (b_i,q_i)} עבור U.
  3. נמיין את A ו-B בסדר עולה.
  4. נחפש זוג הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a_i,p_i)} ו-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (b_j,q_j)} כך שמתקיים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_i + b_j = s} .

אלגוריתם זה דורש מקום מאחר ש-A ו-B הן בגודל כזה כל אחת (הן מייצגות את קבוצות החזקה של קבוצות בגודל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{n}{2}} ). כדי להראות את הטענה לגבי זמן הריצה, צריך להראות שניתן לבנות את הקבוצות באופן ממוין בזמן ולחפש זוג מתאים בזמן דומה. הזמן של המיון נובע מהדרך בה בונים את A ו-B. את החיפוש ניתן לבצע בזמן הדרוש באופן הבא:

  1. נסמן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i = 1, j = |B|}
  2. אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_i + b_j > s} , נסמן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle j = j-1}
  3. אחרת, אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_i + b_j < s} , נסמן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i = i+1}
  4. אחרת, נחזיר את איחוד הקבוצות המקודדות על ידי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p_i} ו-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_j}

אלגוריתם לפתרון בזמן פסאודו פולינומי

פתרון בזמן פסאודו פולינומי אומר שעבור בעיה זהה בה הקלט הוא בבסיס אונרי קיים פתרון הרץ בזמן פולינומי.

הפתרון לבעיה הזו משתמש בתכנון דינמי. נניח שהקלט הוא מהצורה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_1 , ... , X_n} , ועלינו לבדוק האם קיימת תת-קבוצה שסכום איבריה הוא אפס. יהא A הסכום של כל האיברים השליליים בקבוצה, ויהא B הסכום של כל האיברים החיוביים בה.

נגדיר את הפעולה הבוליאנית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q(i,s)} להיות התשובה לשאלה: "האם קיימת תת-קבוצה של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_1 , ... , X_i} שסכום איבריה הוא s". ברור כעת כי פתרון הבעיה הוא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q(n,0)} .

נבחין כי עבור הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A>s,s>B} מתקיים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \forall i: Q(i,s)=false} . כעת, ניצור טבלה בגודל , כאשר הערך בנקודה (i,j) יהיה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q(i,A+j)} , ונמלא את הטבלה מלמטה למעלה ומשמאל לימין באמצעות הרקורסיה הבאה:

  • מקרה הבסיס: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q(1,s) := (x_{1}==s)}
  • עבור הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i=2,...,n} : הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q(i,s) := Q(i-1,s) or (x_{i} == s) or Q(i-1,s-x_{i})}

מילוי כל תא לוקח זמן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(1)} כי ערכי הטבלה שהוא משתמש בהן בפסוק הלוגי ידועים כבר מחישובים קודמים, ולכן זמן מילוי הטבלה יהיה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(n*(B-A))} .

הפתרון לא נחשב פולינומי בתורת הסיבוכיות כיוון שהערך הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B-A} אינו פולינומי בגודל הבעיה, שהוא מספר הביטים שדרוש כדי לייצג אותם. האלגוריתם הוא פולינומי בערכים של ושל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B} , שהם אקספוננציאלים במספר הביטים שלהם.

אלגוריתם קירוב בזמן פולינומי

אלגוריתם קירוב לבעיית הסכום החלקי הוא כדלהלן: בהינתן קבוצת מספרים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_1 , ... , X_n} , מספר s, ומספר c>0 כלשהו, נרצה שהפלט יהיה:

  • "לא", אם לא קיימת תת-קבוצה שמסתכמת למספר בין הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (1-c)s} להפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s} .
  • "כן", אחרת.

אם כל המספרים הם לא שליליים, ניתן לפתור זאת בזמן פולינומי ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} וב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{1}{c}} .

נשים לב שבבעיה המקורית, אם כל סכום אפשרי של מספרים יכול להיכתב באמצעות P ביטים, אם נפתור את הבעיה המקורית באלגוריתם הקירוב עם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c=2^{-P}} , נפתור את הבעיה בדיוק. לכן אלגוריתם זה הוא פתרון מדויק של הבעיה כשהוא רץ בזמן פולינומי ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} וב- (כלומר, אקספוננציאלי ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} ).

האלגוריתם המקורב לבעיה הוא:

initialize a list S to contain one element 0.
 for each i from 1 to n do
   let T be a list consisting of xi + y, for all y in S
   let U be the union of T and S
   sort U
   make S empty 
   let y be the smallest element of U 
   add y to S 
   for each element z of U in increasing order do
      //trim the list by eliminating numbers close to one another
      //and throw out elements greater than s
     if y + cs/n < z ≤ s, set y = z and add z to S 
 if S contains a number between (1 − c)s and s, output yes, otherwise no

האלגוריתם רץ בזמן פולינומי כיוון שהרשימות S,T,U תמיד בגודל פולינומי ב-n וב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{1}{c}} , ולכן גם כל הפעולות שנעשות עליהן מתבצעות בזמן פולינומי. גודל הרשימות אכן נשאר פולינומי היות שאנו מוסיפים עצמים ל-S אם הם גדולים מהעצם הקודם ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{cs}{n}} וקטנים מ-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S} . הצעד שמוודא שההפרש בין כל שני עצמים שמתווספים הוא לפחות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{cs}{n}} מוודא שברשימה יש לכל היותר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{n}{c}} עצמים.

האלגוריתם נכון כיוון שבכל צעד מתווספת שגיאה של לכל היותר , ובמהלך הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} שלבים מתווספת שגיאה של לכל היותר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle cs} .

ראו גם

לקריאה נוספת

הערות שוליים

  1. ^ Martello, Silvano; Toth, Paolo (1990). "4 Subset-sum problem". Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. עמ' 105–136. ISBN 0-471-92420-2. MR 1086874.