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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

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

הבעיה היא: נתונה קבוצה סופית הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S} של קבוצות סופיות, שאיחודן הוא הקבוצה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle U} . יש למצוא תת-קבוצה של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S} בגודל מינימלי, שאיחוד הקבוצות בה הוא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle U} . כלומר יש למצוא את הכיסוי הקטן ביותר לקבוצה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle U} שהוא תת-כיסוי של .

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

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

ניסוח פורמלי

בהינתן קבוצה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal U} וקבוצה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal S} של תתי קבוצות של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal U} , כיסוי הוא תת-קבוצה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal C \subseteq \mathcal S} כך שאיחוד האיברים של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal C} הוא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal U} .

הבעיה היא למצוא את הכיסוי המינימלי של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal U} (כלומר הכיסוי שמשתמש בכמה שפחות איברים מ-).

בגרסת בעיית ההכרעה של בעיית כיסוי הקבוצות נתון הזוג ומספר טבעי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} , והשאלה היא האם יש תת-קבוצה של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal S} מגודל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} לכל היותר שמהווה כיסוי של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal U} .

דוגמה

בהנחה ונתונה לנו קבוצה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal U= \{1,2,3,4,5\}} ומשפחה של קבוצות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal S= \{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}} . איחוד של כל הקבוצות ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal S} מכיל את כל האלמנטים ב-. לעומת זאת כיסוי הקבוצות הקטן ביותר עבור מקרה זה יהיה: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle SETCOVER = \{\{1,2,3\},\{4,5\}\}} .

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

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

מזער את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{S \in \mathcal S} x_S} (מזער את מספר הקבוצות)
כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{S\colon e \in S} x_S \geqslant 1} לכל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e\in \mathcal U} (כל איבר ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal U} מכוסה על ידי קבוצה אחת לפחות)
הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_S \in \{0,1\}} לכל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S\in \mathcal S} (הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_S=1} אם איבר בכיסוי ו-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_S=0} אם לא)

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

הדרך הפשוטה ביותר לבצע את זה היא על ידי אלגוריתם קירוב חמדני. באלגוריתם זה בונים תת-קבוצה של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal S} כדלקמן: מתחילים מקבוצה ריקה ומצרפים לה מדי צעד איבר מ-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal S} (שהוא למעשה תת-קבוצה של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal U} ) המגדיל ככל האפשר (בשלב הנוכחי) את מספר האיברים באיחוד האיברים שכבר נבחרו (מוסיפים את האיבר שיכסה כמה שיותר איברים מ-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal U} שעדיין לא כוסו). האלגוריתם משיג יחס קירוב של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle H(n)} (כלומר הוא מוצא פתרון שקטן מ-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle H(n)} פעמים גודל הכיסוי האופטימלי).[3] כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle H(n) = \sum_{k=1}^{n} \frac{1}{k} \le \ln{n} +1} הוא המספר ההרמוני ה-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} -י. ו-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} הוא גודל הקבוצה שאותה צריך לכסות, כלומר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |\mathcal U|=n} . למעשה ניתן להוכיח שהאלגוריתם משיג יחס קירוב של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle ln(n')-ln(ln(n'))+\Theta(1)} כאשר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n'} הוא גודל האיבר הגדול ביותר ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal S} (כיוון שכל איבר ב- הוא למעשה תת-קבוצה של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal U} ).[4] [5]

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

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

ויקישיתוף ראו מדיה וקבצים בנושא זה בוויקישיתוף.

הערות שוליים

  1. ^ Vijay V. Vazirani, Approximation Algorithms, 2001 doi: 10.1007/978-3-662-04565-7
  2. ^ Korte & Vygen 2012, p. 414.
  3. ^ אלגוריתמים, 2013, עמ' 21-22
  4. ^ Chvatal V., A Greedy Heuristic for the Set-Covering Problem, Mathematics of Operations Research, Vol. 4 No. 3, 1979, עמ' 233-235
  5. ^
    שגיאות פרמטריות בתבנית:צ-מאמר

    פרמטרי חובה [ מחבר ] חסרים
    , A tight analysis of the greedy algorithm for set cover, STOC '96, 1996, עמ' 435–441 doi: 237814.237991
סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0