מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/הזמנות למסיבה/תשובה

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה אל: ניווט, חיפוש

התשובה מתחלקת לשלושה חלקים:

  1. הפיכת המערך A לעץ.
  2. מציאת העומדת בראש החבר.
  3. פתרון הבעיה על העץ.ראשית נבנה את העץ המתאר את החברה. קל לעשות זאת. צמתי העץ הם פשוט , וקשתותיו

מתאימים לזוגות שבמערך A. אם משתמשים ב[[מבני נתונים ואלגוריתמים - מחברת קורס/#|]], קל לראות שהסיבוכיות היא . קל גם למצוא את העומדת בראש החברה. פשוט יש למצוא עבור איזה ,‏ אינו מופיע כאיבר השני באף אחד מהזוגות בA. גם שלב זה אורך . כעת נתבונן בתת-עץ כלשהו, שראשו בצומת , וילדי הם (שים לב שכל צומת יכול להיות גם הוא ראשו של תת-עץ בעצמו).

נגדיר כ את הפתרון הטוב ביותר לתת-העץ ששורשו (הסיבה לסימון המוזר תתבהר בהמשך). בעץ זה, או שנבחר להזמין את , או שלא. אם לא נזמין את , קל להווכח שהפתרון הוא, עפ"י ההגדרה, . מצד שני, נניח שנבחר להזמין את . האם במקרה זה נוכל בהכרח להזמין ? לכאורה כן, מפני ש עצמו תורם 1 אדם למסיבה, ושאר הביטוי מתאר את הפתרונות הטובים ביותר עבור ילדיו. מצד שני, נוסחה זו לוקחת בחשבון גם מצבים אסורים, בהם אנו מזמינים הן את והן את אחד מילדיו הישירים. ננסה, אם כן, להגדיר דברים בצורה עדינה יותר. לכל צומת , נגדיר כ את הפתרון הטוב ביותר לתת-העץ ששורשו כאשר מותר (אך לא חייבים) לבחור ב. (נשים לב שהגדרת לא השתנתה.) נגדיר כ את הפתרון הטוב ביותר ל תת-העץ ששורשו כאשר אסור לבחור ב. קל לחשב רקורסיבית שתי פונקציות אלו, ואחת מהן גם פותרת את הבעיה המקורית. המשפט הבא טוען זאת במדוייק.



משפט:

לכל צומת :

  1. אם עלה, אז:
 



  • אם ילדי הם :


עיבוד הנוסחה נכשל (שגיאת תחביר): {\displaystyle \displaystyle m^{-}(u) = <span xmlns="" class="latex">\sum_{j = 1}^im^{+}(v_j)</span> }
אם שורש העץ, אז הפתרון לבעייתנו הוא .


הוכחה: #אם עלה, אז הוא בעצם כל תת-העץ שבראשו הוא עומד. אם מזמינים אותו, הוספנו עובד 1, ואם לא הזמנו אותו, הוספנו 0 עובדים.

  1. נניח שילדי הם . אם לא מזמינים את

, מותר (אם כי לא חייבים) להזמין כל אחד מילדיו הישירים. הטוב ביותר שנוכל לקבל הוא . לכן

 


מש"ל.PNG

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