#algorithms #computer_science

greedy algorithms

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

דוגמה חיפוש בינארי :
הקלט הוא מערך ממויין של 𝑛 מספרים ומספר 𝑥 , ורוצים להחליט אם 𝑥 נמצא במערך . האלגוריתם הקלאסי פותר את הבעיה בזמן $O (\log n)$ , האלגוריתם הזה הוא אלגוריתם חמדן : הרקורסיה מתחייבת לחפש רק בחצי אחד , ואז האלגוריתם ממשיך ברקורסיה רק עבור החלק הזה . איך מוכיחים שאלגוריתם חיפש בינארי הוא נכון? כיוון שהוא אלגוריתם רקורסיבי , אז הכיוון הוא הוכחה באינדוקציה , נתבונן בצעד האינדוקציה , אנחנו צריכים להוכיח שהחצי של המערך שלא מסתכלים עליו , לו מונע אותנו מלהגיע לתשובה הנכונה , וכך יכולים להוכיח שהאלגוריתם מחזיר את התשובה הנכונה (בשימוש בהנחת האינדוקציה ).

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

הבחירה החמדנית

נרצה להוכיח את ה greedy choice של האלגוריתם על ידי כך שנראה שההחלטה החמדנית המקומית שהאגוריתם החמדני עושה , לא מונע האלגוריתם מלהגיע לפתרון נכון (או אופטימלי). למשל בחיפוש הבינארי נוכל להגיד שהבחירה החמדנית היא ״אם האוסף שלנו ממויין והאיבר שאנחנו מחפשים גדול מהחציון, אז בוודאות הוא נמצא בתת המופע הימני של האוסף או שהוא לא נמצא בכלל, אחרת, בשמאלי או שהוא לא נמצא בכלל .״

תת- המבנה האופטימלי

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

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

א. Prefix Code - Huffman Code
ב. Minimum Spanning Tree

בעיית בחירת הפעילויות

פוליטקיאי מתמודד בבחירות ורוצה להספיק להגיע להופיע בכמה שיותר אירועים. ישנה חפיפה בין אירועים, והמתמודד לא יכול להגיע לאירוע באופן חלקי, כיוון שבכך הוא יביך את מארחיו ויפסיד מצביעים. מנגד, למתמודד יש כח על של התעתקות ממקום למקום, כך שהמעבר בין מקומות אינו לוקח לו זמן.
באופן פורמלי נגדיר את הבעיה ככה
בהינתן שתי פעילויות שמיוצגות על ידי זמן התחלה וסיום $[s_{i}, f_{i}]$ הפעילות ה $A_{i}$ ו $[s_{j}, f_{j}]$ הפעילות ה $A_{j}$ נאמר שהפעילויות מתיישבות זו עם זו אמ״מ

f_{i} \leq s_{j} \lor s_{i} \geq f_{j}

זה מתאר מצב של חוסר חפיפה דוגמה לכך על ציר הזמן תיראה ככה
Pasted image 20221127184816.png|300

קלט: מערך של פעילויות $S - {A_{1}, A_{2}, A_{3}, \dots, A_{n}}$ כך שלכל פעילות $A_{i}$ יש זמן התחלה וסיום כמתואר למעלה.
פלט:תת הקבוצה גדולה ביותר $A \subseteq S$ של כל הפעילויות שמתיישבות זו עם זו.

פתרון
נרצה לבנות אלגוריתם חמדני - ישנה איזושהי פעילות $A_{i}$ שזאת הפעילות הראשונה אליה הפוליטיקאי ילך בפתרון אופטימלי.
נשים לב שבהינתן שניקח $A_{i}$ כזאת לא ייתכן שנמצא פעילות $A_{j}$ שמסתיימת לפני תחילת הפעילות $A_{i}$ אחרת היינו יכולים להוסיף גם את $A_{j}$ לקבוצת הפעילויות ואז $A_{i}$ אינה הפעילות הראשונה בפתרון האופטימלי.
מההבחנה הזו, נשים לב לכך שבבואנו לבחור את הפעילות הראשונה, הפרמטר שהכי מעניין אותנו אינו מתי הפעילות מתחילה אלא דווקא מתי היא מסתיימת.
נרצה את הפעילות שמסתיימת מוקדם ביותר, כי זאת תשאיר לנו כמה שיותר אפשרויות לבניית הקבוצה הכי גדולה. לכן הבחירה החמדנית שלנו תהיה שקיים פתרון אופטימלי לבעיית בחירת הפעילויות בו בוחרים פעילות שמסתיימת מוקדם ביותר.
בכל שלב ניקח את הפעילות שמסתיימת מוקדם ככל הניתן מבין הפעילויות שעוד אפשר לקחת, ונמחק מרשימת האפשרויות את כל אלה שחופפות לה.

Activity-Selector(S)
	sort(S, by: f_i)
	A = {A_1}
	j=1
	for i=2 to n
	if s_i >= f_j
		A = A union {A_i}
		j = i
	return A

נוכל לתאר אותו גם בצורה ריקורסיבית

בחר את הפעילות שמסיימת מוקדם ביותר
מחק את הפעילויות שלא מתיישבות איתה (אלו שמתחילות לפני סיומה)
הוסף באופן ריקורסיבי בחירה גדולה ביותר של פעילויות מהפעילויות הנותרות.

הוכחת נכונות

תכונת הבחירה החמדנית
קיים פתרון אופטימלי לבעיית בחירת הפעילויות בו בוחרים את הפעילות שמסתיימת מוקדם ביותר
ניקח פתרון אופטימלי כלשהו נסמנו OPT
אם הפעילות שמסתיימת מוקדם נמצאת שם סיימנו.
אחרת נסתכל על הפעילות שמסתיימת ראשונה נסמן אותה כ $j = m i n O P T$ כמו כן נגדיר את $1$ להיות הפעילות שמסתיימת ראשונה באופן כללי (בגלל שגם ככה מסתכלים על הפעילויות ממוינות לפי זמני סיום).
אנחנו יודעים שהפעילות $j$ מסתיימת בוודאות אחרי $1$ ולכן נבנה את $O P T^{'}$ בצורה הבאה

O P T^{'} = O P T / {j} \cup {1}

נוכיח כי הוא פתרון חוקי :
עבור שתי פעילויות $x, y \in O P T^{'}$ אם הן היו גם ב $O P T$ אז סיימנו. אם אחת מהן היא $1$ (בלי הגבלת הכלליות נניח כי $x = 1$ ) אזי מחוקי אי שיוויון יתקיים

f_{1} \leq f_{j} \leq s_{y}

כי $j, y$ פעילויות שמתיישבות זו עם זו בפתרון אופטימלי OPT ו $1$ בוודאות מסתיימת לפניה אז גם אם $1, j$ לא מתיישבות , בוודאות מתקיים ש $1, y$ כן מתיישבות.

נוכיח כי הוא פתרון אופטימלי:

| O P T^{'} | = | O P T | + 1 - 1 = | O P T |

ו OPT הוא פתרון אופטימלי.

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

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

יהי פתרון $A$ כפי במוצג בהגדרת הפתרון למעלה ונב״שׁ שאינו אופטימלי ופתרון $B$ אופטימלי שמכיל בתוכו את $1$ לפי למת הבחירה החמדנית.
מהנתון מתקיים

| B | > | A |

אנחנו יודעים שמתקיים מאיך ש $A$ בנוי ש $1 \in A$ כי זאת הפעילות שמסתיימת מוקדם ביותר. כמו כן אנחנו יודעים ש $A / {1}$ הוא פתרון אופטימלי לבעיה כיוון ש $A$ בנוייה מתת פתרון אופטימלי איחוד עם $ֿ {1}$ .
כלומר נקבל שגם $A / {1}$ וגם $B / {1}$ הם פתרונות אופטימלים עם הפעילויות ${i \in S | s_{i} \geq f_{1}}$ . כלומר יתקיים

| B / {1} | \leq | A / {1} | \to | B | - 1 \leq | A | - 1 \to | A | \geq | B |

בסתירה לכך ש $A$ לא אופטימלית.

בעיית תרמיל הגב בשברים

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

קלט: מערך של מחירים $V = (v_{1}, v_{2}, \dots, v_{n})$ ומערך של משקלים $W = (w_{1}, w_{2}, \dots, w_{n})$ ומספר $B$ .
פלט: החפצים או החלק שאנחנו לוקחים מכל חפץ (1- לקחת את כל החפץ , 0- לא לקחת בכלל , כל מספר בין לבין- לקחת את החלק היחסי). הפלט ייראה כך $X = (x_{1}, x_{2}, x_{3}, \dots, x_{n})$ כך ש $x_{i} \in [0, 1]$ ומתקיים

\forall_{1 \leq i \leq n} : \sum_{i = 1}^{n} x_{i} w_{i} \leq B \land \sum_{i = 1}^{n} x_{i} v_{i} is the maximum possible sum

נציע אלגוריתם חמדני הפותר את הבעיה הזו.
בעוד שבבעיית תרמיל הגב הרגילה לעבוד עם יחס עלות ליחידת משקל מסויימת לא היה עובד, כאן אכן נוכל לעבוד איתו.
נסמן $a_{i} = \frac{v_{i}}{w_{i}}$ ונמיין את החפצים לפי יחס הסדר מהגדול להקטן על $a_{i}$ . כלומר במקום ה1 יהיה את היחס עלות למשקל הכי גבוה.
כעת נבחר באופן חמדני את הערכים שם היחס הגדול ביותר כל עוד יש מקום, עד לזה שערכו הקטן ביותר.

Knapsack(V,W,B)
	define A[n]
	for i=1 to n
		A[i] = a_i = v_i / w_i
	sort V and W from biggest to smallest using A
	define X[n]
	for i=1 to n
		x[i] = min(B,w_i)/w_i
		B = B - x_i * w_i
	return X

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

ניקח את המקסימום האפשרי מהחפץ עם היחס עלות-משקל הגבוהה ביותר.
משמיטים את כמה שלקחנו מהמשקל
מפעילים את הריקורסיה עם משקל מופחת ובלי האיבר שהוספנו

הוכחת נכונות

תכונת הבחירה החמדנית
קיים פתרון אופטימלי לבעיית תרמיל הגב בשברים בו לוקחים את החלק הגדול ביותר שניתן מהחפץ שמתאים ל־a1) החפץ עם השווי הגדול ביותר ליחידת משקל).
יהי פתרון אופטימלי כלשהו $(x_{1}, x_{2}, \dots, x_{n})$
אם קיים $x_{i}$ כך שהוא מכיל בתוכו את החפץ הגבוה ביותר ליחידת משקל סיימנו.
אחרת ישנו בלי הגבלת הכלליות נניח $x_{1}$ הוא מתאר את הכמות שלקחנו בפתרון האופטימלי הזה עם היחס הטוב ביותר מבין כל האחרים שלקחנו. נחלק למקרים :

לא לקחנו בכלל מ $v$ שהוא מתאר את הכמות שלקחנו מהחפץ עם $a$ המשתלם ביותר מבין כל החפצים כלומר $x = 0$ - נכניס את $x$ לאחר שחישבנו אותו מחדש עבור $B$ המקורי (נזכיר $x = m i n (B, w) / w$ ) לאוסף ונבדוק האם אין חריגה במשקל, אם אין אז סיימנו כי הוספנו עוד ערך בלי לחרוג. אם יש חריגה נתחיל להשמיט כמה משקל שאנחנו יכולים מהסוף להתחלה , כלומר מ $x_{n}$ עד ל $x_{1}$ ההשמטה תהיה ביחס לחריגה מהמשקל. החריגה תבוא לידי ביטוי בצורה מספר שלילי כלומר $B = W < 0$ וכעת מה שאפשר לעשות זה

Balance(B)
	assert B < 0
	
	for i=n to 1
		B =  B + x_i * w_i
		if B < 0
			continue
		if B = 0
			return 
		x_i = min(B, w_i)/w_i		
		return

אם לקחנו מ $v$ אבל לא בכמות המקסימלית, נעשה בידיוק אותו דבר, נעשה חישוב מחדש ל $x$ נכניס אותו לוקטור ונריץ את אותו אלגוריתם.

נשים לב שברור שהסכום החדש יניב יותר כסף , קל להוכיח את זה באופן הבא, נפרק את המשקל שלקחנו מ $x$ , נסמנו $w$ כסכום של כל המשקלים שהשלמנו
$w = w_{n} + w_{n - 1} + \dots + w_{1}$
אם לא לקחנו מ $w_{i}$ אז ערכו $0$ . כעת יתקיים

\forall_{i \in [1, n]} : \frac{v}{w_{i}} > \frac{v_{i}}{w_{i}} \to \sum_{i = 1}^{n} \frac{v}{w_{i}} > \sum_{i = 1}^{n} \frac{v_{i}}{w_{i}}

נשים לב שבוודאות ניתן יהיה לאזן על ידי הורדת משקלים בלי שנגיד למצב ש״אין מספיק להוריד״ כי בסוף בוודאות סכום כל מי שאינו $x$ היה $B$ כלומר יש לנו עד $B$ להוריד מהמשקל.

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

נב״ש שהפתרון המתואר בלמה $(x_{1}, x_{2}, \dots, x_{n})$ אינו אופטימלי ונניח ש $(y_{1}, \dots, y_{2})$ פתרון אופטימלי. מהנחת הבחירה החמדנית נקבל ש

y_{1} = x_{1} \land \sum_{i = 1}^{n} x_{i} < \sum_{i = 1}^{n} y_{i}

אם נוריד את $x_{1}, y_{1}$ נקבל שתי פתרונות אופטימליים לבעיה תרמיל הגב בשברים עבור תרמיל במשקל $B - x_{1} w_{1}$ . אבל מכאן יתקיים בגלל שכעת אנחנו עובדים עם תת פתרון אופטימלי $x_{2}, \dots, x_{n}$

\sum_{i = 2}^{n} y_{i} \leq \sum_{i = 2}^{n} x_{i}

ומכאן

\sum_{i = 2}^{n} y_{i} + x_{1} \leq \sum_{i = 2}^{n} x_{i} + x_{1}

שזה בסתירה לאי שיוויון הראשון.