עזרה בכתיבת אלגוריתם\פתרון בעיה עם ניחוח תכנותי, קצת מסובך

[שוקו]

שלום, הבעיה שלי היא כזאת:

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

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

קובי נמצא בנקודה רחוקה יותר (נגיד 0,10), ונע ב1 מטר לשניה בכיוון מסויים- נקבע את זה בזווית 0-360. בנוסף, תוך כדי תנועתו (נניח שיוסי נע בצעדים בדידים של קוביה אחת במערכת הצירים שלנו\בצעדים של מטר) הוא יכול להחליט לשנות את הכיוון שלו בהסתברות מסויימת (אותה נפלג אחר כך בצורה בדידה כלשהי)

דוגמא: קובי נמצא בנקודה (0,7) ונע בכיוון 180* (ז"א היישר ליוסי בראשית). ולכן סיכוי הפגיעה הם 100%.

אבל, בהסתברות של 25% שהוא יפנה שמאלה\ימינה, ואכן באחד התרחישים ואחרי צעד קדימה ל (0,6) הגורל רצה והוא פונה שמאלה ומגיע ל(1,6) וכו' ואז סיכוי הפגיעה הוא 0% כי הוא רחוק מידי.

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

מדובר במשהו רקורסיבי, אבל איני מתכנת ולא יודע איך לאכול את זה.

תודה

[שניצל]

הפתרון הוא תכנון דינמי.

אתה רוצה הרי לדעת מה ההסתברות לפגיעה כשקובי נמצא במיקום x,y בזמן t. אז תגדיר פונקציה כזו (P(x,y,t. הפונקציה הזו מקיימת תנאי רקורסיבי כלשהו - לדוגמה, אם הסיכוי של קובי ללכת לכל כיוון הוא בדיוק 1/4, אז הנוסחה היא משהו כזה:

P(x,y,t) = 1/4 P(x-1,y,t+1) + 1/4 P(x+1,y,t+1) + 1/4 P(x,y-1,t+1) + 1/4 P(x,y+1,t+1)

וכמובן יש מקרי קצה מסויימים (לדוגמה אם t>5 אתה יודע ש-P(x,y,t)=0 בכל מקרה).

אז מה שאתה עושה הוא לחשב ברקורסיה, אבל לעשות "caching" לפתרונות שחישבת עד כה - אתה יוצר מערך תלת מימדי (או אפילו HashMap/Dictionary) שיכיל את ערכי P שחושבו עד כה. בפונקציה שמחשבת את (P(x,y,t, אתה קודם כל בודק: אם המערך מכיל כבר ערך עבור x,y,t הנתונים, אתה פשוט מחזיר אותו. אחרת אתה מבצע את החישוב, ולפני שאתה מחזיר את התוצאה אתה שומר אותה במקום המתאים במערך.

זמן הריצה של האלגוריתם הזה הוא כמספר הערכים השונים של P שצריך לחשב, שזה כנראה (max(y)*max(x)*max(t.

יש מבין?

[שוקו]

יש מבין?

תודה, כן הבנתי את הכיוון. אתקדם עם הנושא הזה בהזדמנות