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

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

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

מתאימים לזוגות שבמערך A. אם משתמשים ב[[מבני נתונים ואלגוריתמים - מחברת קורס/#|]], קל לראות שהסיבוכיות היא $\displaystyle \Theta (n)$. קל גם למצוא את העומדת בראש החברה. פשוט יש למצוא עבור איזה $\displaystyle s\in \{1,\ldots n\}$,‏ $\displaystyle s$ אינו מופיע כאיבר השני באף אחד מהזוגות בA. גם שלב זה אורך $\displaystyle \Theta (n)$. כעת נתבונן בתת-עץ כלשהו, שראשו בצומת $\displaystyle u$, וילדי $\displaystyle u$ הם $\displaystyle v_{1},\ldots v_{i}$ (שים לב שכל צומת יכול להיות גם הוא ראשו של תת-עץ בעצמו).

.

.

נגדיר כ$\displaystyle m^{+}(u)$ את הפתרון הטוב ביותר לתת-העץ ששורשו $\displaystyle u$ (הסיבה לסימון המוזר תתבהר בהמשך). בעץ זה, או שנבחר להזמין את $\displaystyle u$, או שלא. אם לא נזמין את $\displaystyle u$, קל להווכח שהפתרון הוא, עפ"י ההגדרה, $\displaystyle \sum _{j=1}^{i}m^{+}(v_{j})$. מצד שני, נניח שנבחר להזמין את $\displaystyle u$. האם במקרה זה נוכל בהכרח להזמין $\displaystyle 1+\sum _{j=1}^{i}m^{+}(v_{j})$? לכאורה כן, מפני ש$\displaystyle u$ עצמו תורם 1 אדם למסיבה, ושאר הביטוי מתאר את הפתרונות הטובים ביותר עבור ילדיו. מצד שני, נוסחה זו לוקחת בחשבון גם מצבים אסורים, בהם אנו מזמינים הן את $\displaystyle u$ והן את אחד מילדיו הישירים. ננסה, אם כן, להגדיר דברים בצורה עדינה יותר. לכל צומת $\displaystyle u$, נגדיר כ$\displaystyle m^{+}(u)$ את הפתרון הטוב ביותר לתת-העץ ששורשו $\displaystyle u$ כאשר מותר (אך לא חייבים) לבחור ב$\displaystyle u$. (נשים לב שהגדרת $\displaystyle u$ לא השתנתה.) נגדיר כ$\displaystyle m^{-}(u)$ את הפתרון הטוב ביותר ל תת-העץ ששורשו $\displaystyle u$ כאשר אסור לבחור ב$\displaystyle u$. קל לחשב רקורסיבית שתי פונקציות אלו, ואחת מהן גם פותרת את הבעיה המקורית. המשפט הבא טוען זאת במדוייק.

משפט: לכל צומת $\displaystyle u$: אם $\displaystyle u$ עלה, אז: $\displaystyle m^{+}(u)=1$ $\displaystyle m^{-}(u)=0$

• אם ילדי $\displaystyle u$ הם $\displaystyle v_{1},\ldots v_{i}$:

$\displaystyle m^{+}(u)=\max\{1+\sum _{j=1}^{i}m^{-}(v_{j}),\sum _{j=1}^{i}m^{+}(v_{j})\}$
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikibooks.org/v1/":): {\displaystyle \displaystyle m^{-}(u) = <span xmlns="" class="latex">\sum_{j = 1}^im^{+}(v_j)</span> }
אם $\displaystyle s$ שורש העץ, אז הפתרון לבעייתנו הוא $\displaystyle m^{+}(s)$.

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

1. נניח שילדי $\displaystyle u$ הם $\displaystyle v_{1},\ldots v_{i}$. אם לא מזמינים את

$\displaystyle u$, מותר (אם כי לא חייבים) להזמין כל אחד מילדיו הישירים. הטוב ביותר שנוכל לקבל הוא $\displaystyle \sum _{j=1}^{i}m^{+}(v_{j})$. לכן

 $\displaystyle m^{-}(u)=\sum _{j=1}^{i}m^{+}(v_{j})$

כעת נניח שמותר להזמין את $\displaystyle u$. אז יש שתי אפשרויות: מזמינים אותו, או לא מזמינים אותו. אם לא מזמינים אותו, מקבלים בדיוק את המצב הקודם, דהיינו $\displaystyle \sum _{j=1}^{i}m^{+}(v_{j})$. אם מזמינים את $\displaystyle u$ יש להוסיף 1, אך אסור להזמין אף אחד מילדיו הישירים. הטוב ביותר שנוכל לקבל הוא $\displaystyle 1+\sum _{j=1}^{i}m^{-}(v_{j})$. יש לקחת את הטוב משתי האפשרויות. לכן $\displaystyle m^{+}(u)=\max\{1+\sum _{j=1}^{i}m^{-}(v_{j}),\sum _{j=1}^{i}m^{+}(v_{j})\}$