בעיית כיסוי קבוצות
בעיית כיסוי קבוצות (באנגלית: Set Cover Problem) היא בעיה קלאסית בקומבינטוריקה, מדעי המחשב, אופטימיזציה וסיבוכיות. הבעיה נכללת ברשימת 21 הבעיות ה-NP שלמות של קארפ.
בעיית כיסוי הקבוצות היא בעיה חשובה בתחום אלגוריתמי קירוב. היא בעיה ש"לימודה הוביל לפיתוח טכניקות יסודיות לתחום הכולל" של אלגוריתמים מקורבים.[1]
הבעיה היא: נתונה קבוצה סופית של קבוצות סופיות, שאיחודן הוא הקבוצה . יש למצוא תת-קבוצה של בגודל מינימלי, שאיחוד הקבוצות בה הוא . כלומר יש למצוא את הכיסוי הקטן ביותר לקבוצה שהוא תת-כיסוי של .
שאלה זו היא NP-קשה; וגרסת בעיית ההכרעה שלה היא NP-שלמה.
הבעיה הזו היא דוגמה אופיינית וחשובה של בעיית אופטימיזציה בדידה. תכונה חשובה של בעיה בסיסית זו היא שניתן למצוא באופן יעיל קירוב סביר לאופטימום שלה - ניתן למצוא באופן יעיל פתרון לבעיה הקרוב לפתרון האופטימלי, בסיבוכיות שתהיה בסדר גודל של הלוגריתם של גודל הקבוצה שאותה יש לכסות.
ניסוח פורמלי
עריכהבהינתן קבוצה וקבוצה של תתי קבוצות של , כיסוי הוא תת-קבוצה כך שאיחוד האיברים של הוא .
הבעיה היא למצוא את הכיסוי המינימלי של (כלומר הכיסוי שמשתמש בכמה שפחות איברים מ- ).
בגרסת בעיית ההכרעה של בעיית כיסוי הקבוצות נתון הזוג ומספר טבעי , והשאלה היא האם יש תת-קבוצה של מגודל לכל היותר שמהווה כיסוי של .
דוגמה
עריכהבהנחה ונתונה לנו קבוצה ומשפחה של קבוצות . איחוד של כל הקבוצות ב- מכיל את כל האלמנטים ב- . לעומת זאת כיסוי הקבוצות הקטן ביותר עבור מקרה זה יהיה: .
הצגה כבעיית תכנון ליניארי בשלמים
עריכהניתן להציג את בעיית כיסוי קבוצות כבעיית תכנון ליניארי בשלמים כך:
מזער את | (מזער את מספר הקבוצות) |
כאשר לכל | (כל איבר ב- מכוסה על ידי קבוצה אחת לפחות) |
לכל | ( אם איבר בכיסוי ו- אם לא) |
אלגוריתם חמדני
עריכההדרך הפשוטה ביותר לבצע את זה היא על ידי אלגוריתם קירוב חמדני. באלגוריתם זה בונים תת-קבוצה של כדלקמן: מתחילים מקבוצה ריקה ומצרפים לה מדי צעד איבר מ- (שהוא למעשה תת-קבוצה של ) המגדיל ככל האפשר (בשלב הנוכחי) את מספר האיברים באיחוד האיברים שכבר נבחרו (מוסיפים את האיבר שיכסה כמה שיותר איברים מ- שעדיין לא כוסו). האלגוריתם משיג יחס קירוב של (כלומר הוא מוצא פתרון שקטן מ- פעמים גודל הכיסוי האופטימלי).[2] כאשר הוא המספר ההרמוני ה- -י. ו- הוא גודל הקבוצה שאותה צריך לכסות, כלומר . למעשה ניתן להוכיח שהאלגוריתם משיג יחס קירוב של כאשר הוא גודל האיבר הגדול ביותר ב- (כיוון שכל איבר ב- הוא למעשה תת-קבוצה של ).[3] [4]
לחלופין, ניתן למצוא קירוב טוב לפתרון בהסתמך על תכנון ליניארי בשילוב עם תהליך של עיגול מקרי.
קישורים חיצוניים
עריכההערות שוליים
עריכה- ^ Vijay V. Vazirani, Approximation Algorithms, 2001 doi: 10.1007/978-3-662-04565-7
- ^ אלגוריתמים, 2013, עמ' 21-22
- ^ Chvatal V., A Greedy Heuristic for the Set-Covering Problem, Mathematics of Operations Research, Vol. 4 No. 3, 1979, עמ' 233-235
- ^ Petr Slavík, A tight analysis of the greedy algorithm for set cover, STOC '96, 1996, עמ' 435–441 doi: 237814.237991