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

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

בעיית כיסוי קבוצותאנגלית: 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
Logo hamichlol.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0