בעיות בתכנות דינמי

פיבונאצי

השתמשנו בטכניקת memorisation זה נקרא גם top-down . שיטה זו מאפשרת לנו לבצע caching לערכים וככה למנוע חישובים מיותרים .

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

למשל בפיבונאצי, בישביל $f_i$ צריך רק את $f_{i-1},f_{i-2}$ ואין באמת צורך בכולם.

למשל הנ״ל יעבוד באופן הבא.

שימוש ב bottom-up חוסך זכרון רב. עם כי לעומת memorized הביצועים לא יהיו גבוהים בהרבה מmemo.

Planting flowers in a flowerbox

בהינתן מערך $A$ בגודל $n$ . כל איבר במערך , מייצג ערך ״תזונתי״ לצמח. נרצה לשתול צמחים ככה שנקסמם את הערך התזונתי שכל הצמחים מקבלים ביחד. הבעיה היא שלא ניתן לשתול אותם אחד ליד השני.

אם נבנה dependency graph לפונקצייה, היא אמורה להראות בסגנון הזה

כי התשובה האם ניתן לשתול או לא תלוייה בהאם שתלנו או לא שתלנו באיבר ליד.

התלות הריקורסיבית תהיה בצורה הבאה

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

נרצה לחשב להשתמש ב bottom-up לפי התלות באיברים שבנינו:

change making problem

הרעיון של הבחירה הוא באופן הבא:

כלומר הפונקצייה הריקורסיבית תיראה באופן הבא

כאשר $t$ מייצג את הסכום הדרוש ו $d$ את אוסף סוגי המטבעות הדרושים.

התשובה תהיה עבור ערך $t_0$ נוכל להפעל את הפונקצייה כך $f(n,d,t_0)$ .

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

במצב כזה, שבו קשה לנו לחזות מה תהיה תוצאת החישוב הבאה וכי אנחנו לא מכסים את כל השיטות חישוב האפשרויות מומלץ להשתמש בשיטת top down ולא bottom up.

content aware image resizing

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

1 . נוכל להגדיר יחס בין פיקסלים באופן הבא

נקרא לזה energy of a pixel

באופן מתמטי , נגדיר את האנרגייה $e$ של פיקסל , ביחס לארבעת הפיקסלים מסביבו באופן הבא

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

נאיבי $O(2^n)$ על כל ערך נרוץ על כל הסכומים האפשריים שלו עם $n-1$ הערכים האפשרים רצים על קבוצה החזקה של $[n]$ ובודקים את כל הצירופים האפשריים.

ריקורסיבי
נגדיר את הפונקצייה הבאה

הסבר, קלט : המערך כ$A$ גודלו כ $n$ והמספר שמחפשים כ $k$ . אם המשקל שווה ל0 אין מה לחפש כי המספרים טבעיים אז הכל תקין וכנ״ל אם המערך ריק. אחרת לוקחים את האיבר האחרון , אם אין מה לבדוק אותו, כלומר משקלו גבוה יותר מהסכום, נבדוק בלעדיו, אחרת נפעיל את האופרטור הבינארי $or$ על הפונקצייה כאשר מחשיבים את האיבר בסכום ואת הפונקצייה כאשר האיבר לא בסכום.

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

דינאמי נשתמש בטכניקה של memorization כלומר מלמעלה למטה, נחזיק מערך דו מימדי המכיל את כל הזוגות הסדורים האפשריים של אינדקס והסכום שאפשר לקבל כלומר מטריצה בגודל $n\times k$ . המערך יהיה מאותחל כולו מ $-1$ המערך יכיל את הערכים true או false בעת ההשמה (כלומר 0 או 1).
וכעת כל מה שנשאר לעשות הוא לפני הקריאות הריקורסיביות לבדוק האם יש איבר במקום ה $n,k$ של המטריצה שלנו.
אם יש נחזיר אותו , אחרת נבדוק בידיוק את אותם התנאים רק נעשה השמה באופן הבא:

סיבוכיות זמן+מקום $O(n\cdot k)$

	static int subsetSum(int a[], int n, int sum)
	{
		// Storing the value -1 to the matrix
		int tab[][] = new int[n + 1][sum + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= sum; j++) {
				tab[i][j] = -1;
			}
		}
		if (sum == 0)
			return 1;

		if (n <= 0)
			return 0;

		if (tab[n - 1][sum] != -1)
			return tab[n - 1][sum];

		if (a[n - 1] > sum)
			return tab[n - 1][sum]
				= subsetSum(a, n - 1, sum);
		else {
			if (subsetSum(a, n - 1, sum) != 0
				|| subsetSum(a, n - 1, sum - a[n - 1])
					!= 0) {
				return tab[n - 1][sum] = 1;
			}
			else
				return tab[n - 1][sum] = 0;
		}
	}

נאיבי
אנחנו נרצה את תת הקבוצה הקטנה ביותר שתקיים שסכום הערכים שלה יוצא בידיוק הסכום המבוקש. הפתרון הנאיבי יהיה לרוץ על קבוצת החזקה של סוגי המטבעות כלומר $2^k$ ולחשב את כל האפשרויות השונות.

ריקורסיה
נגדיר את הפונקצייה הבאה

הסבר :

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

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

דינאמי
את הבעיה הזאת נפתור בשיטת top down גם כן, נגדיר מערך דו מימדי בגודל $k\times n$ בדומה לתרגיל הקודם לפני הקריאות הריקורסיביות נבדוק האם קיים ערך במקום עליו אנחנו עומדים, אם כן נחזיר אותו בזמן קבוע אחרת נפעיל את הקריאות הריקורסיביות תוך כדי השמה.

סיבוכיות $O(n\cdot k)$

f(V,k,n):
 if k  0 or n  o : return 0
 if k==1 : return n
 if R[k-1,n] != 0 : return R[k-1,n]
 if V[k]>n : return f(V,k-1,n)
 return min(f(V,k,n-V[k])+1 , f(V,k-1,n))

נאיבי נחשב את כל הקריאות האפשריות , על קבוצת החזקה של הקלט $S$ כלומר כל תתי המחרוזות האפשריות סך הכל $O(2^n)$ .

ריקורסיבי
נגיד את הפונקצייה הבאה

f(S,n,i):
  if i>=n
    return true
  for(j=i ; j<=n l j++) :
    return T(S,i,j) and f(S,i,j+1)

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

דינאמי
נשים לב שהפעם אנחנו עובדים עם אינדקס אחד נוכל לשמור את המידע $f(i)$ במערך חד מימדי $A[n]$ כך שבאיבר האחרון נשמור $true$ ובכל ערך $i$ אחר נשמור האם קיימת חלוקה ל $f(i)$ כלומר לתת הסטרינג $S[i...n]$ . האלגוריתם יהיה top down כיוון שאנחנו בונים את הסטרינג שלנו מתוך הבנה שהגעה לסוף משמעותה שהגענו ל$true$

for i=n to 1 {
  boolean temp = false
 for j=n to i {
   if j >= n:
   temp = T(S, i, j) and A[j+1]
    if j==n:
     temp = T(S, i, j)
     if temp == true:
     A[i] <- true
     break
     if temp == false:
   A[i] <- false
  }
 }
return A[1];

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

זמן הריצה יהיה $O(n^2)$ כי בעצם מבצעים בנייה של איברים המערך באופן התלוי בכל מי שהיה לפניו.
סיבוכיות המקום היא $O(n)$ .

לכל משבצת שבה הארנב נמצא יש 3 אפשרויות תזוזה, ולכל תזוזה כזו יש מחיר, כמו כן ייתכן שהמסלול שהארנב יבצע יוביל אותו למצב לא תקין שממנו לא ניתן להגיע כלל ליעד. לכן נגדיר את הפונקצייה הבעיה $f:(s_1,s_2)\times (i,j)\to Integer$ פונקצייה המקבלת את הממטריצה וערכי כל משבצת, נקודה התחלה ונקודה יעד ותחשב את הערך המינימלי עבור כל המסלולים האפשריים. באופן ריקורסיבי זה ייראה כך

זמן הריצה הירקורסיבי יהיה כל תתי הקבוצות שמייצגות מסלול כלומר $O(2^n)$ .
נרצה לייעל את מספר המסלולים שעוברים באותם הנקודות על ידי שמירה של הערכים במטריצה שכל איבר בה מייצג את $C(i,j)$ . כמו כן , נרצה להשתמש בשיטת bottom up לאלגוריתם הדינמי שלנו, כיוון שאנחנו יודעים שכל איבר במסלול בנוי מהערכים המינימלים במשבצות שבאו לפניו ולכן נגדיר את הקוד הבא

int f((s1,s2),(i,j)) {

  for i in [n] : 
    for j in [n] :

	min [C(i-1,j)+P2(i-1,j) ,
	 C(i,i-1)+ P1(i,j-1) , 
	 C(i-1,j-1) + P3(i-1 , j-1)]
  return C[n,n]
}