מבנה ההוכחה: החמדן אופטימלי (וקטורים בת"ל)

משפט. הפתרון שמחזיר האלגוריתם החמדן הוא פתרון אופטימלי.

יהי אופטימלי. בסדר משקלים יורד: , .

  • שלב 1 — .
    • אם : לפי הלמה אפשר להוסיף מ ל בסתירה לאופטימליות.
    • אם : לפי הלמה אפשר להוסיף מ ל בסתירה לחמדנות.
  • שלב 2 — אם אז קיים עם .
  • שלב 3 — סתירה.

שתיהן בת"ל כי הן תת-קבוצות של ושל . גדול מ . לפי הלמה קיים כך ש- בת"ל, כלומר היה זמין בשלב , והחמדן בחר את :

הערה. ההוכחה השתמשה בלמה שלוש פעמים, ובשום מקום לא השתמשה בכך שמדובר בוקטורים.

אלגוריתמים · פרופ׳ יוחאי בר סיני · האוניברסיטה העברית

בעיית אופטימיזציה גנרית

בעיית אופטימיזציה גנרית

  • קלט:
    • קבוצה סופית ;
    • פונקציית משקל ;
    • אוסף של תת-קבוצות של — מרחב הפתרונות החוקיים.
  • פלט: שעבורו מקסימלי.

וקטורים בת"ל:

התרמיל השלם:

שיבוץ משימות

תכונה משותפת לשלוש הבעיות: תורשתית — אם ו- אז גם (תת-קבוצה של קבוצה חוקית היא חוקית).

אלגוריתמים · פרופ׳ יוחאי בר סיני · האוניברסיטה העברית

האלגוריתם החמדן

אלגוריתם חמדן לקבוצת וקטורים בת"להאלגוריתם החמדן הגנרי
  1. עיבוד מוקדם: ממיינים לפי משקל יורד. מעתה נניח כי .
  2. אתחול: — האינדקסים שעדיין ניתנים לבחירה; — תכיל את הפתרון החמדן.
  3. איטרציה: כל עוד :
    1. הצב ב- את האינדקס המינימלי ב-.
    2. הוסף את ל- והסר אותו מ-.
    3. הסר מ- כל אינדקס שעבורו תלוי לינארית ב- שעבורו .
  4. סיים כל עוד
  5. סיום: מחזירים את .

אבל האלגוריתם החמדן לא עובד בבעיית התרמיל השלם, למרות ש תורשתית. מה עוד חסר?

אלגוריתמים · פרופ׳ יוחאי בר סיני · האוניברסיטה העברית

תורשתיות, תכונת ההחלפה, מטרואיד

הגדרה (מטרואיד). תהי קבוצה סופית ו- אוסף לא ריק של תת-קבוצות של . הזוג נקרא מטרואיד אם מקיימת:

  1. תורשתיות: אם ו- אז ;
  2. תכונת ההחלפה: אם וגם אז קיים כך ש-.

איברי נקראים הקבוצות הבלתי-תלויות של המטרואיד.

משפט: החמדן אופטימלי על מבנה מטרואידי

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

הוכחה: ההוכחה של משפט האופטימליות לוקטורים עוברת מילה במילה.

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

הוכחה: לא נוכיח בכיתה. ההוכחה מופיעה בסיכום שיועלה ל-Moodle; להרחבה — פרק 16 של Cormen.

ביחד:

החמדן הגנרי אופטימלי לכל אם ורק אם מטרואיד.

אלגוריתמים · פרופ׳ יוחאי בר סיני · האוניברסיטה העברית

אותה הוכחה, על וקטורים בת"למטרואיד

משפט. הפתרון שמחזיר האלגוריתם החמדן הוא פתרון אופטימלי.אם מטרואיד, האלגוריתם החמדן הגנרי מחזיר פתרון אופטימלי, לכל .

יהי אופטימלי. בסדר משקלים יורד: , .

  • שלב 1 — .
    • אם : לפי הלמהלפי תכונת ההחלפה אפשר להוסיף מ ל בסתירה לאופטימליות.
    • אם : לפי הלמהלפי תכונת ההחלפה אפשר להוסיף מ ל בסתירה לחמדנות.
  • שלב 2 — אם אז קיים עם .
  • שלב 3 — סתירה.

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

אלגוריתמים · פרופ׳ יוחאי בר סיני · האוניברסיטה העברית

דוגמאות למטרואידים

מטרואיד וקטורי: , = הקבוצות הבלתי תלויות לינארית.

מטרואיד השידוכים: גרף, , = קבוצות קודקודים שקיים שידוך המכסה אותן.

מטרואיד גרפי: גרף, , = קבוצות קשתות חסרות מעגלים (יערות).

abcdef

נראה בתרגול: החמדן הגנרי על המטרואיד הגרפי הוא פשוט קרוסקל.

אלגוריתמים · פרופ׳ יוחאי בר סיני · האוניברסיטה העברית

דוגמא ללא מטרואידים

בעיית התרמיל השלם. נבנה קלט קטן:

1w = 252w = 253w = 50W = 50

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

שיבוץ משימות:

123

, חוקיים, , אבל אי אפשר להוסיף ל- אף משימה מ- בלי להפר חוקיות.

אז למה החמדן עבד על שיבוץ משימות?

אלגוריתמים · פרופ׳ יוחאי בר סיני · האוניברסיטה העברית

Class deck for 03-matroids session 2, text taken from handout-matroids.md. Generated by gen03_slides.py (session scratchpad); the proof-structure slide appears twice, the second time with old/new spans toggled by the #hl / #sw fragments. Build: scripts/build-slides.sh (or Cmd+Shift+B) -> slides-matroids.html