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

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

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

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

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

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

ניסוח פורמלי

בהינתן קבוצה ${\mathcal {U}}$ וקבוצה ${\mathcal {S}}$ של תתי קבוצות של ${\mathcal {U}}$, כיסוי הוא תת-קבוצה ${\mathcal {C}}\subseteq {\mathcal {S}}$ כך שאיחוד האיברים של ${\mathcal {C}}$ הוא ${\mathcal {U}}$.

הבעיה היא למצוא את הכיסוי המינימלי של ${\mathcal {U}}$ (כלומר הכיסוי שמשתמש בכמה שפחות איברים מ-${\mathcal {C}}$).

בגרסת בעיית ההכרעה של בעיית כיסוי הקבוצות נתון הזוג $({\mathcal {U}},{\mathcal {S}})$ ומספר טבעי $k$, והשאלה היא האם יש תת-קבוצה של ${\mathcal {S}}$ מגודל $k$ לכל היותר שמהווה כיסוי של ${\mathcal {U}}$.

דוגמה

בהנחה ונתונה לנו קבוצה ${\mathcal {U}}=\{1,2,3,4,5\}$ ומשפחה של קבוצות ${\mathcal {S}}=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}$. איחוד של כל הקבוצות ב-${\mathcal {S}}$ מכיל את כל האלמנטים ב-${\mathcal {U}}$. לעומת זאת כיסוי הקבוצות הקטן ביותר עבור מקרה זה יהיה: $SETCOVER=\{\{1,2,3\},\{4,5\}\}$.

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

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

מזער את $\sum _{S\in {\mathcal {S}}}x_{S}$	(מזער את מספר הקבוצות)
כאשר $\sum _{S\colon e\in S}x_{S}\geqslant 1$ לכל $e\in {\mathcal {U}}$	(כל איבר ב-${\mathcal {U}}$ מכוסה על ידי קבוצה אחת לפחות)
$x_{S}\in \{0,1\}$ לכל $S\in {\mathcal {S}}$	($x_{S}=1$ אם $S$ איבר בכיסוי ו-$x_{S}=0$ אם לא)

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

הדרך הפשוטה ביותר לבצע את זה היא על ידי אלגוריתם קירוב חמדני. באלגוריתם זה בונים תת-קבוצה של ${\mathcal {S}}$ כדלקמן: מתחילים מקבוצה ריקה ומצרפים לה מדי צעד איבר מ-${\mathcal {S}}$ (שהוא למעשה תת-קבוצה של ${\mathcal {U}}$) המגדיל ככל האפשר (בשלב הנוכחי) את מספר האיברים באיחוד האיברים שכבר נבחרו (מוסיפים את האיבר שיכסה כמה שיותר איברים מ-${\mathcal {U}}$ שעדיין לא כוסו). האלגוריתם משיג יחס קירוב של $H(n)$ (כלומר הוא מוצא פתרון שקטן מ-$H(n)$ פעמים גודל הכיסוי האופטימלי). כאשר $H(n)=\sum _{k=1}^{n}{\frac {1}{k}}\leq \ln {n}+1$ הוא המספר ההרמוני ה-$n$-י. ו-$n$ הוא גודל הקבוצה שאותה צריך לכסות, כלומר $|{\mathcal {U}}|=n$. למעשה ניתן להוכיח שהאלגוריתם משיג יחס קירוב של $ln(n')-ln(ln(n'))+\Theta (1)$ כאשר $n'$ הוא גודל האיבר הגדול ביותר ב-${\mathcal {S}}$ (כיוון שכל איבר ב-${\mathcal {S}}$ הוא למעשה תת-קבוצה של ${\mathcal {U}}$).

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

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

מדיה וקבצים בנושא בעיית כיסוי קבוצות בוויקישיתוף