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

בעיית כיסוי קבוצות (באנגלית: 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}}$).

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

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

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

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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