בעיית כיסוי קבוצות

בעיה קלאסית בקומבינטוריקה, מדעי המחשב, אופטימיזציה וסיבוכיות הבעיה נכללת ברשימת 21 הבעיות ה-NP-שלמות של קארפ

בעיית כיסוי קבוצותאנגלית: Set Cover Problem) היא בעיה קלאסית בקומבינטוריקה, מדעי המחשב, אופטימיזציה וסיבוכיות הבעיה נכללת ברשימת 21 הבעיות ה-NP-שלמות של קארפ.

בעיית כיסוי הקבוצות היא בעיה חשובה בתחום אלגוריתמי קירוב. היא בעיה ש"לימודה הוביל לפיתוח טכניקות יסודיות לתחום הכולל" של אלגוריתמים מקורבים.[1]

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

שאלה זו היא NP-קשה; וגרסת בעיית ההכרעה שלה היא NP-שלמה.[2]

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

ניסוח פורמליעריכה

בהינתן קבוצה   וקבוצה   של תתי קבוצות של  , כיסוי הוא תת-קבוצה   כך שאיחוד האיברים של   הוא  .

הבעיה היא למצוא את הכיסוי המינימלי של   (כלומר הכיסוי שמשתמש בכמה שפחות איברים מ- ).

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

דוגמהעריכה

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

הצגה כבעיית תכנון ליניארי בשלמיםעריכה

ניתן להציג את בעיית כיסוי קבוצות כבעיית תכנון ליניארי בשלמים כך:

מזער את   (מזער את מספר הקבוצות)
כאשר   לכל   (כל איבר ב-  מכוסה על ידי קבוצה אחת לפחות)
  לכל   (  אם   איבר בכיסוי ו-  אם לא)

אלגוריתם חמדניעריכה

הדרך הפשוטה ביותר לבצע את זה היא על ידי אלגוריתם קירוב חמדני. באלגוריתם זה בונים תת-קבוצה של   כדלקמן: מתחילים מקבוצה ריקה ומצרפים לה מדי צעד איבר מ-  (שהוא למעשה תת-קבוצה של  ) המגדיל ככל האפשר (בשלב הנוכחי) את מספר האיברים באיחוד האיברים שכבר נבחרו (מוסיפים את האיבר שיכסה כמה שיותר איברים מ-  שעדיין לא כוסו). האלגוריתם משיג יחס קירוב של   (כלומר הוא מוצא פתרון שקטן מ-  פעמים גודל הכיסוי האופטימלי).[3] כאשר   הוא המספר ההרמוני ה- -י. ו-  הוא גודל הקבוצה שאותה צריך לכסות, כלומר  . למעשה ניתן להוכיח שהאלגוריתם משיג יחס קירוב של   כאשר   הוא גודל האיבר הגדול ביותר ב-  (כיוון שכל איבר ב-  הוא למעשה תת-קבוצה של  ).[4][5]

לחלופין, ניתן למצוא קירוב טוב לפתרון בהסתמך על תכנון ליניארי בשילוב עם תהליך של עיגול מקרי.

קישורים חיצונייםעריכה

הערות שולייםעריכה

  1. ^ Vijay V. Vazirani, Approximation Algorithms, 2001 doi: 10.1007/978-3-662-04565-7
  2. ^ Korte & Vygen 2012, p. 414.
  3. ^ אלגוריתמים, 2013, עמ' 21-22
  4. ^ Chvatal V., A Greedy Heuristic for the Set-Covering Problem, Mathematics of Operations Research, Vol. 4 No. 3, 1979, עמ' 233-235
  5. ^
    שגיאות פרמטריות בתבנית:צ-מאמר

    פרמטרי חובה [ מחבר ] חסרים
    , A tight analysis of the greedy algorithm for set cover, STOC '96, 1996, עמ' 435–441 doi: 237814.237991