בעיית תרמיל הגב

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

בעיית תרמיל הגבאנגלית: Knapsack problem) היא בעיית מיטוב קומבינטורית הנחקרת בתחום מדעי המחשב. בבעיה זו נתונה קבוצת עצמים שלכל אחד מהם משקל ומחיר, ובנוסף נתון חסם על המשקל. המטרה היא למצוא אוסף של העצמים הנתונים שסכום משקליהם אינו עולה על החסם הנתון, ומחירו מרבי.

הבעיה נחשבת לבעיה חשובה במדעי המחשב בגלל הערך התאורטי שלה (הבעיה היא NP-שלמה[1]), ובגלל השימושים שלה בתחומים כמו הקצאת משאבים וקריפטוגרפיה[2].

הגדרת הבעיה[עריכת קוד מקור | עריכה]

נתונים n עצמים ולכל עצם i נתונים מחירו p_i ומשקלו w_i. לכל עצם i נסמן ב-x_i את מספר העצמים מחפץ שנכניס לתרמיל. המטרה היא למקסם את הביטוי \sum_{i=1}^n p_ix_i (המחיר הכולל של העצמים בתרמיל) בכפוף לאילוץ \sum_{i=1}^n w_ix_i \leq W (משקלם הכולל של החפצים אינו עולה על החסם).

הגרסה הנפוצה והפשוטה ביותר היא בעיית תרמיל הגב הבינארי: בבעיה זו לכל חפץ יש עותק אחד בלבד ולכן x_i \in \{0,1\} (או שהאיבר נכנס לתרמיל או שאינו נכנס לתרמיל).

בבעיית תרמיל הגב החסומה, לכל עצם i יש כמות c_i ומותר להכניס לתרמיל מספר עותקים של העצם: x_i \in \{0,1,...,c_i\}.

בבעיית תרמיל הגב הלא חסומה, מותר לקחת מספר עותקים בלתי מוגבל מכל עצם: x_i \geq 0.

NP-שלמות[עריכת קוד מקור | עריכה]

גרסת ההכרעה של בעיית תרמיל הגב היא: בהינתן n עצמים עם מחירים p_i ומשקלים w_i, ובהינתן מחיר כולל P יש להכריע האם קיימת בחירה של העצמים כך ש- \sum_{i=1}^n p_ix_i \geq P תחת האילוץ \sum_{i=1}^n w_ix_i \leq W. בעיה זו היא NP-שלמה:

  • הוכחה שהבעיה ב-NP מתבצעת על ידי ההבחנה שבהינתן פתרון x ניתן לוודא בזמן פולינומי האם מתקיימים התנאים \sum_{i=1}^n p_ix_i \geq P ו-\sum_{i=1}^n w_ix_i \leq W.
  • הוכחה שהבעיה היא NP-קשה מתבצעת על ידי רדוקציה מבעיית החלוקה[3][4]: בהינתן מופע של בעיית החלוקה a_1,a_2,...,a_n נוכל להגדיר מופע של בעיית תרמיל הגב שבו לכל i מתקיים w_i=p_i=a_i וכמו כן מתקיים W=P=\frac{\sum_{i=1}^n a_i}{2}. קיים תרמיל חוקי‏[5] עבור מופע הבעיה אם ורק אם קיימת חלוקה של העצמים A = {a_1,a_2,...,a_n} לשתי קבוצות בעלות סכום זהה: בהינתן חלוקה A = X \cup Y התרמיל החוקי יהיה פשוט X (נשים לב שמשקל התרמיל ומחירו הם בדיוק מחצית מסכום איברי A), ובהינתן תרמיל X החלוקה של A תהיה לקבוצות X, A/X (שוב, מטעמי חוקיות הפתרון, סכום כל קבוצה הוא מחצית סכום איברי A).

גישות לפתרון[עריכת קוד מקור | עריכה]

תכנון דינאמי[עריכת קוד מקור | עריכה]

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

האלגוריתם הבא פותר את בעיית תרמיל הגב הבינארית בסיבוכיות זמן O(nW).

בהינתן מופע של הבעיה כמתואר בחלק "הגדרת הבעיה", נגדיר m[i,w] להיות מחיר הפתרון המיטבי שניתן להשיג באמצעות עצמים שמספר הסידורי שלהם אינו עולה על i ושסכום משקלם אינו עולה על w. הגדרה זו מאפשרת פיתוח נוסחת נסיגה ל-m[i,w]:

  • אם w_i > w\,\! אז מתקיים m[i,\,w]=m[i-1,\,w] (לא ניתן להשתמש בעצם שמספרו i).
  • אם w_i \leq w אז מתקיים m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_i]+w_i) (ניתן להשתמש בעצם שמספרו i והמחיר המיטבי הוא המחיר המרבי מבין המקרה בו הערך נבחר והמקרה בו הוא לא נבחר).
  • תנאי הבסיס ייקבע להיות m[0,w]=0 לכל w (ללא עצמים המחיר הכולל הוא תמיד 0).

כעת ניתן, באמצעות חישוב ערכי הטבלה m, לחשב ברקורסיה את m[n,W], הלוא הוא המחיר המיטבי לבעיה.

הקוד הבא בשפת Python מממש את האלגוריתם המתואר‏[6]:

def knapsack01_dp(items, limit):
    table = [[0 for w in range(limit + 1)] for j in xrange(len(items) + 1)]
 
    for j in xrange(1, len(items) + 1):
        item, wt, val = items[j-1]
        for w in xrange(1, limit + 1):
            if wt > w:
                table[j][w] = table[j-1][w]
            else:
                table[j][w] = max(table[j-1][w],
                                  table[j-1][w-wt] + val)
 
    result = []
    w = limit
    for j in range(len(items), 0, -1):
        was_added = table[j][w] != table[j-1][w]
 
        if was_added:
            item, wt, val = items[j-1]
            result.append(items[j-1])
            w -= wt
 
    return result

אלגוריתמי קירוב[עריכת קוד מקור | עריכה]

גישה אחרת לפתרון הבעיה היא שימוש באלגוריתמי קירוב. לבעיה זו קיימים מספר אלגוריתמי קירוב כולל סכמת קירוב פולינומית מלאה‏[7].

אלגוריתם הקירוב החמדן הבא מוצא תרמיל שמחירו עבור קטן פי לכל היותר 2 מהפתרון המיטבי‏[8]: מיין את העצמים לפי יחס המחיר-משקל שלהם p_j/w_j והוסף לתרמיל, כל עוד זה אפשרי, את העצם בעל היחס הגדול ביותר שניתן להכניס.

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Vazirani, Algorithms, 2006
  2. ^ David Pisinger, Algorithms for Knapsack Problems ,1995
  3. ^ בעיית החלוקה היא בעיית ההכרעה המוגדרת באופן הבא: בהינתן רב-קבוצה של מספרים שלמים, האם ניתן לחלק אותה לשתי רב-קבוצות כך שסכום כל אחת מתתי הרב-קבוצות שווה
  4. ^ Anupam Gupta, 15-854: Approximations Algorithms - Dynamic Programming, 2005
  5. ^ פתרון חוקי לבעיה הוא פתרון המקיים את כל האילוצים של הבעיה
  6. ^ מקור לקוד התוכנית: http://rosettacode.org/wiki/Knapsack_problem/0-1
  7. ^ Chandra Chekuri, CS 598CSC: Approximation Algorithms, 2009
  8. ^ Alexander Souza, Combinatorial Algorithms - Lecture Notes , Winter Term 10/11, 2011