מעבר מרקורסיה לאיטרציה

[tseliot]

מעבר מרקורסיה לאיטרציה

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

int getValue() { for each move { if (move is possible) { board.push(move); int moveValue=getValue(); board.pop(); if(black) { if(moveValue>best Value) { store current move as best move; } } else// white { if(moveValue<best Value) { store current move as best move; } } } else { continue; } } if(no moves were possible) { caculate score; return score; } else { return best move's value; } }​

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

 

[vinney]

זה שזה אפשרי זה לא אומר שזה

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

 

[tseliot]

מהו עומק רקורסיה מוגבל וסביר?

ברור לי שזה תלותי בהרבה פרמטרים, אבל נגיד על PC ממוצע, מה הגבול שאחריו לא היית משמתמש ברקורסיה?

 

[vinney]

החישוב יחסית פשוט

יש לך מחסנית של 32K, כל קריאה לפונקציה זה 8 בתים של כתובת החזרה + פרמטרים. נגיד שבממוצע אתה מנצל 2K מהמחסנית, חשב כמה קריאות (+משתנים מקומיים, אם יש לך, לכל קריאה) יכנסו לך ב30K הנותרים. אם אתה מממש מחסנית משלך, הקוד שלך הופך מסורבל טיפה (לא בהרבה), אבל מצד שני אתה לא תצטרך לשמור כתובת החזרה (כבר חסכת מקום), וגם ההגבלה של 32K (שזה אגב אפשר לשנות בקומפילציה לערכים שונים) לא תחול עלייך.

 

[ron369]

למה המחסנית היא של 32K?

וגם, רגע. משתנים בתוך פונקציות לא נשמרים במחסנית? (לא statics) (אוף, אני עוד בראש של חישוביות. למי יש כוח למבחן ב-C

)

 

[vinney]

לשם דוגמא

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

 

[ron369]

הממ

דווקא נראה שכתובות החזרה שלי יותר גדולות: (אני קורא לזה "התכוננות למבחן"

) #include<stdio.h> void f(long int x){ printf("%d \n",x); f(x+1); } void main(){ f(0); } result = 11755 #include<stdio.h> int num=0; void f(void){ printf("%d \n",num); num+=1; f(); } void main(){ f(); } result= 12314

 

[ron369]

תודה בכל מקרה, ותיקון

(חשבתי שהוא יישר את הכל לשמאל. אבל לא...)

#include<stdio.h> void f(long int x){ printf("%d \n",x); f(x+1); } void main(){ f(0); } result = 11755 #include<stdio.h> int num=0; void f(void){ printf("%d \n",num); num+=1; f(); } void main(){ f(); } result= 12314​

 

[vinney]

הא?

 

[ron369]

בדקתי מתי המחסנית תתמלא,

כך שהתכנית תתקע

 

[double X]

האלגוריתם שלך

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