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

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

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

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

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

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

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

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

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

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

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

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

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

קישורים חיצוניים

הערות שוליים

בעיות NP-שלמות