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

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

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

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

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

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

== ניסוח פורמלי ==
בהינתן קבוצה <math>\mathcal U</math> וקבוצה <math>\mathcal S</math> של תתי קבוצות של <math>\mathcal U</math>, כיסוי הוא תת-קבוצה <math>\mathcal C \subseteq \mathcal S</math> כך שאיחוד האיברים של <math>\mathcal C</math> הוא <math>\mathcal U</math>.

הבעיה היא למצוא את הכיסוי המינימלי של <math>\mathcal U</math> (כלומר הכיסוי שמשתמש בכמה שפחות איברים מ-<math>\mathcal C</math>).

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

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

== הצגה כבעיית תכנון ליניארי בשלמים ==
ניתן להציג את בעיית כיסוי קבוצות כבעיית תכנון ליניארי בשלמים כך:
{|
|מזער את <math>\sum_{S \in \mathcal S} x_S</math>
|(מזער את מספר הקבוצות)
|-
|כאשר <math>\sum_{S\colon e \in S} x_S \geqslant 1</math> לכל <math>e\in \mathcal U</math>
|(כל איבר ב-<math>\mathcal U</math> מכוסה על ידי קבוצה אחת לפחות)
|-
|<math>x_S \in \{0,1\}</math> לכל <math>S\in \mathcal S</math>
|(<math>x_S=1</math> אם <math>S</math> איבר בכיסוי ו-<math>x_S=0</math> אם לא)
|}

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


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

==הערות שוליים==

קטגוריה:בעיות NP-שלמות