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