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

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

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

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

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

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

ניסוח פורמלי

בהינתן קבוצה $𝒰$ וקבוצה $𝒮$ של תתי קבוצות של $𝒰$, כיסוי הוא תת-קבוצה $𝒞\subseteq 𝒮$ כך שאיחוד האיברים של $𝒞$ הוא $𝒰$.

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

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

דוגמה

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

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

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

מזער את $\sum _{S\in 𝒮}{x}_S$	(מזער את מספר הקבוצות)
כאשר $\sum _{S:e\in S}{x}_S⩾1$ לכל $e\in 𝒰$	(כל איבר ב-$𝒰$ מכוסה על ידי קבוצה אחת לפחות)
$x_S\in \{0,1\}$ לכל $S\in 𝒮$	($x_S=1$ אם $S$ איבר בכיסוי ו-$x_S=0$ אם לא)

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

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

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