.. (לתיקייה המכילה) | ||
האם d יכול להיות שלילי? | |
לא, d הוא מספר אי שלילי |
מודפסים לי מסלולים ריקים | |
יש להשתמש באחת מהגרסאות 3.6.6 או 3.6.7 של פייתון ולא אחרת. הוראות התקנה מופיעות במחברת מהתרגול הראשון. בכל מקרה, יש לוודא שהמסלולים אכן מודפסים כהלכה. |
חלק ז׳ - בחישוב יצא שמחלקים באפס | |
תחשבו מה קורה שאחד הערכים בוקטור x מתקרב מאוד לאפס. מה זה אומר על הערך הזה? מה זה אומר על ההגרלה? האם יש בכלל צורך להגריל במקרה כזה? |
סעיף 24 - איפה נמצא אלגוריתם ה- anytime? | |
בסעיף 24 אתם לא נדרשים לממש מחלקה / פונק׳ ייעודים עבור אלגוריתם anytime. אתם צריכים להריץ האלג׳ הגרידי-סטוכסטי (שמימשתם בסעיף 23) 100 פעם בלולאה, לשמור את התוצאות של ריצות אלו ברשימה, ולאחר מכן (או במהלך אותה לולאה), בהתבסס על תוצאות הריצות הללו, לחשב את תוצאות אלג׳ anytime לכל איטרציה. אותן התוצאות של 100 הריצות של הגרידי-סטוכסטי משמשות אתכם גם כדי לחשב את תוצאות האלג׳ anytime (כלומר אין צורך לבצע 100 הרצות נוספות עבור הגרידי-סטוכסטי). אופן החישוב מפורט בהערות שבתוך האזור הרלוונטי בקוד בקובץ main.py. |
סעיף 24 - מתי משתנה ה- T ב- 100 ההרצות של הגרידי-סטוכסטי | |
בסעיף 24 כל אחת מ- 100 ההרצות של האלג׳ הגרידי-סטוכסטי היא הרצה מלאה של אלג׳ זה שמומש בסעיף 23. כלומר כבר מימשתם את החלק שמטפל בערך T בסעיף 23. בפרט, כל הרצה כזו מתחילה בערך T התחלתי 1.0 ובמהלכה הערך T קטן פי 0.95 בכל בחירת צומת לפיתוח (כלומר תצטרכו ליצור אובייקט solver חדש לטובת כל ריצה). |
סעיף 12 - תיקון טעות בהערות בקוד בקובץ main.py | |
בהערות לעיתים מוזכר שם הפונק׳ plot_distance_and_expanded_by_weight_figure בעוד שהכוונה היא לפונק׳ plot_distance_and_expanded_wrt_weight_figure. |
סעיף 26 - תיקון טעות בהערות בקוד בקובץ main.py | |
בהערות בקוד עבור סעיף זה כתוב להשתמש ב- big_deliveries_prob בעוד הכוונה היא ל- small_deliveries_strict_problem. |
סעיף 27 - תיקון טעות | |
במסמך ההוראות התבקשתם להסביר מדוע היוריסטיקה זו מיודעת. זוהי טעות בשאלה. כמובן שהמונח ״מיועדת״ הינו יחסי להיוריסטיקה אחרת ואין לו משמעות אבסולוטית. הכוונה היא: רשמו בדו״ח מדוע היוריסטיקה זו *קבילה*. |
סעיף 27 - איך יוצרים קלט עבור בעיה RelaxedDeliveriesProblem חדשה? | |
צרו אובייקט חדש מסוג DeliveriesProblemInput עם הקלט לבעיה. ה c'tor של המחלקה DeliveriesProblemInput מקבל כפרמטרים את השדות של מחלקה זו לפי סדר הופעתם בחלק העליון של הגדרת המחלקה DeliveriesProblemInput המוגדרת בקובץ deliveries/deliveries_problem_input.py. את אובייקט הקלט שיצרתם אתם שולחים כפרמטר לבנאי המחלקה של הבעיה. |
חלק תיאורתי סעיף ב׳ - האם העץ יכול להיות אינסופי? | |
כן. |
סעיף 12 - יש לי גבעה בגרף. האם זה בסדר? | |
באופן כללי, אנחנו מצפים שככל ש- w גדול יותר, אנחנו נותנים יותר משקל להיוריסטיקה ולכן הפתרון פחות ״טוב״ (כלומר רחוק יותר מהפתרון האופטימלי - יקר יותר). הגרף שלכם אמור להראות מגמה כללית מתאימה. שימו לב שבסעיף זה אנחנו למעשה בוחנים 20 אלגוריתמים שונים על אותו קלט שרירותי קבוע ובעזרת היוריסטיקה (שאינה מושלמת) שנקבעה מראש. לכל זוג אלגוריתמי w-A* (שמתאימים לזוג ערכי wi<wj) אנחנו מצפים שעבור הרבה קלטים שונים האלג׳ המתאים ל- wi יניב פתרון זול יותר מאשר הפתרון שמניב האלג׳ המתאים ל- wj. אבל- האם מובטח שטענה זו תתקיים לכל קלט? האם לא ניתן לתכנן קלט כזה שעבורו wj יניב פתרון זול יותר? (זכרו שההיוריסטיקה אינה מושלמת). |
סעיף 28 - תיקון טעות | |
התבקשתם להשוות את מספר המצבים שפותחו לעומת הריצה בסעיף הקודם. הכוונה היא להשוות את מספר המצבים שפותחו לעומת הריצות בסעיף 26 עם המשקלים השונים. בפרט, לתוצאה מסעיף 26 עם משקל 0.5 ובנוסף לאיזה משקל בסעיף 26 מספר הפיתוחים היו לראשונה נמוכים יותר מאשר מספר הפתוחים בפתרון מסעיף 28 אם בכלל? בכמה הפתרון עם משקל זה (מסעיף 26) פגע באיכות הפתרון? |
איך אפשר לייצג בפייתון את הערך אינסוף? | |
אפשר להשתמש בערך np.inf כדי לייצג את הערך אינסוף. |
סעיף 23 - איך לממש את המתודה open_successor_node באלג׳ הגרידי-סטוכסטי? | |
ראשית, גם באלג׳ הזה אנחנו מתחזקים close. שימו לב לפרמטר use_close=True שמקבל ה- c’tor של BestFirstSearch ממנו יורש GreedyStochastic. באלג׳ UC, כאשר סוגרים צומת, לא ייתכן שיימצא מסלול טוב יותר לצומת הזה (מוסבר באחת מהשקופיות במצגת של תרגול 3 בגרסה של אלעד). לעומת זאת, באלג׳ A* למשל מצב שכזה ייתכן (גם מופיע בשקופיות). זה השפיע על אופן המימוש שלנו למתודה זו באלג׳ A*. האם מצב שכזה ייתכן גם עבור אלג׳ ה- GreedyStochastic? כדי לענות על שאלה זו, הזכרו מהי פונק׳ ה- f-score של אלג׳ ה- GreedyStochastic? |
חלק תיאורתי - האם דלתא הוא חסם תחתון או עליון? | |
דלתא חסם תחתון על מחיר הקשתות. |
חלק תיאוריתי - האם ניתן להשתמש בערך של דלתא לצורך הגדרת היוריסטיקה? | |
הערך של דלתא אינו ידוע ולא ניתן להשתמש בו כדי להגדיר היוריסטיקה חדשה בשאלה זו. |
חלק תיאורתי - עודכן | |
שימו לב: המסמך עודכן והוספו הבהרות בחלק התיאורתי. |
האם צריך לשנות משהו בקובץ best_first_search.py? | |
לא. אפשר להתעלם מההערה TODO שם. |
חלק תיאורתי - מה ההבדל בין מצב לבין צומת בעץ החיפוש? למה זה עוזר לי שיש לי את הצומת? | |
מתוך פניות חוזרות שמנו לב שרבים מכם עדיין לא מבדילים בין מצב במרחב המצבים לבין צומת בעץ החיפוש שנוצר במהלך ריצת אלג׳ החיפוש. בכדי לוודא שאתם בקיאים לחלוטין בהבדלים, מומלץ להביט בשקפים 7+13 של תרגול 3 בגרסה Tut3-elad.pptx (המצגת עודכנה לאחרונה בכדי להבהיר את הנקודה). |
סעיף 27 - באיזו היוריסטיקה עלינו להשתמש עבור ה solver של בעיית ה- relaxed הפנימית המוגדרת בתוך מתודת ה- estimate של ההיוריסטיקה החדשה? | |
לצורך פתרון בעיה פנימית זו השתמשו בהיוריסטיקה MSTAirDistHeuristic. אגב, שימו לב: בהקשר של סעיף זה מופיע *פעמיים* המושג ״בעייה פנימית״. יש את בעיית ה- relaxed הפנימית שפותרים ב- RelaxedDeliveriesHeuristic.estimate ויש את בעיית ה- map הפנימית שפותרים בתוך פונק׳ העוקב של הבעיה StrictDeliveriesProblem. |
סעיף 24 - מה בדיוק אמור להיות בגרף? | |
הגרף צריך להכיל 4 עקומות: (1) עבור 100 תוצאות הרצת הגרידי-סטוכסטי; (2) עבור תוצאת ה- anytime (שגם היא משתנה בין האיטרציות); (3) תוצאת הרצת ה- A* שהיא קו אופקי שלא תלוי באיטרציה; (4) תוצאת הרצת הגרידי (שאינו סטוכסטי) וגם הוא קו אופקי שלא תלוי באיטרציה. בנוסף, יש להוסיף לגרף (באמצעות matplotlib) אינדקס שמתאר לכל אחת מארבעת העקומות (לפי צבע) לאיזה אלג׳ היא מתאימה. צריך גם להוסיף כיתוב לצירים. וכמו בכל גרף, להוסיף לו כותרת מתאימה. |
סעיף 24 - על איזה בעיה להריץ? | |
big_deliveries_prob |
זוגות אחרים מקבלים תוצאות ריצה שונות. ממה זה יכול לנבוע? | |
בשלד הקוד שסיפקנו לכם יש אי-דטרמיניסטיות בבחירת הצומת הבא מ- open כאשר יש מספר צמתים עם אותו ערך f score מינימלי. זה יכול לגרום להבדלים בין תוצאות הריצה במימושים שונים. ייתכנו 2 מימושים שלמים נכונים ותקינים שיניבו תוצאות שונות. זה בסדר ואתם לא צריכים להיות מוטרדים מכך. לצורך הרצת בדיקות הוגנות, פתרנו אצלינו את הבעיה ע״י הכנסת שינויים נקודתיים בקבצי קוד שאתם לא אמורים לערוך. אם אתם מעוניין להשוות את תוצאות הריצה מול מימושים של זוגות אחרים, אתם יכולים לשנות בקובץ best_first_search במימוש המחלקה SearchNodesPriorityQueue במתודה push_node את השורה השנייה בשורה הבאה self._nodes_queue[node] = (node.expanding_priority, hash(node.state)). לצורך ההשוואה, וודאו שמימשתם בצורה זהה לחלוטין את מתודת hash במחלקת המצב. הפתרון שלנו לבעיה הזו הוא טיפה יותר מורכב כדי לאפשר שכל זוג יגדיר לו hash כרצונו. |
חלק תיאורתי - סעיף ד׳ - הוספת הנחה | |
ניתן להשתמש בהנחה הבאה: אם A* הכניס לתור open צמתים שונים בעלי אותו ערך f-score, הם ישלפו מהתור open לפי סדר ההכנסה. |
חלק תיאורתי - סעיפים ב׳ + ג׳ - האם זה בסדר להריץ אלג׳ חיפוש כדי לחשב את הערך ההיוריסטי? | |
ראשית, שימו לב לדרישות הסיבוכיות מהאלג׳ ההיוריסטי שאתם נדרשים לכתוב (מופיע באחת ההבהרות לסעיף ב׳ בהוראות העבודה. תקף גם לסעיף ג׳ כמובן). אתם נדרשים לכתוב פונק׳ estimate היוריסטית ולא אלג׳ חיפוש. ברקע רץ אלג׳ חיפוש מיודע (שלא אתם כותבים). כל פעם שאלג׳ החיפוש הזה נתקל במצב s (שהגיע למשל מהפעלה של succ על מצב אחר), הוא כרגיל עוטף אותו בצומת חדש v בעץ החיפוש (מתקיים v.state = s) ומבצע קריאה לאלג׳ ההיוריסטי (זה שאתם מנסחים) עם הצומת v. כמובן שבמהלך החיפוש ייתכנו הרבה קריאות לאלג׳ שלכם (קריאה לכל צומת שנוצר בעץ החיפוש). שימו לב שאם האלג׳ ההיוריסטי היה יכול לבצע סיור מלא בעץ היינו יכולים לחשב כך בדיוק את ההיוריסטיקה המושלמת h*. זו לא הכוונה בסעיף זה. אתם לא נדרשים לחשב היוריסטיקה מושלמת, אלא לכתוב אלג׳ שבמקרים מסויימים ינצל (בצורה חכמה) מצבים עליהם h מוגדרת לטובת מצבים עבורם h לא מוגדרת, וזאת מבלי לחרוג מדרישות הסיבוכיות. |
חלק תיאורתי - סעיפים ב׳ + ג׳ - תיקון טעות בהבהרות | |
בהבהרה השלישית בסעיף ב׳ יש טעות. החלפנו בין S לבין S'. הכוונה היא לנצל את הערך של h על מצבים שבהם היא מוגדרת לטובת חישוב הערך עבור מצבים שבהם היא אינה מוגדרת. כמובן שלא ניתן לנצל את הגדרת h על מצבים עליהם היא לא מוגדרת. |
חלק תיאורתי - סעיפים ב׳ + ג׳ - האם ניתן להשתמש במחיר האופרטור בין אב למצב עוקב? | |
תניחו שמחיר האופרטור בין מצב למצב העוקב שמור כשדה בצומת המייצג את המצב העוקב. |
סעיפים 26 + 28 - עם איזה משקלים להריץ? מול איזה משקלים להשוות? | |
1. את סעיף 26 אתם מריצים עם 20 משקלים שונים כפי שרשום בהוראות עבור סעיף זה. 2. את סעיף 28 אתם מריצים רק על משקל w=0.5. 3. לאחר מכן, בהשוואה בסעיף 28 אתם משווים את ההרצה של סעיף 28 (עם w=0.5 כאמור) מול 2 הרצות שונות (שני ערכי w שונים) מסעיף 26: (1) ההרצה של 26 עם משקל w=0.5, ו- (2) ההרצה של סעיף 26 עבור ה- w מינימלי (שאותו אתם אמורים למצוא, מבין ה- 20 שנבדקו שם) שעבורו מס׳ הפיתוחים (של סעיף 26) נמוך יותר מאשר מספר הפיתוחים של ההרצה (היחידה) של סעיף 28. |
הוראות הגשת מטלה רטובה - באיזה תיקייה לשים את קבצי הקוד? | |
בקובץ ה- zip שאתם מגישים, אמור להופיע קובץ pdf של הדו״ח ותיקייה בשם AI1 כפי שרשום בהוראות ההגשה. בתוך התיקייה AI1 צריכים להופיע הקבצים והתיקיות שהיו בתיקייה hw1 שחילצתם מה- zip המקורי שאנחנו סיפקנו לכם (כלומר הקובץ main.py והתיקיות deliveries, experiments, framework). אנא מחקו את התיקייה db שנמצאת בתיקייה framework. אנא מחקו גם תיקיות __pycache__ שנוצרו בתוך התיקיות השונות במהלך העבודה (בקובץ zip המקורי שסיפקנו לכם לא היו כאלו כלל), ותיקיות .idea של PyCharm. פרט לקובץ ה- pdf של הדו״ח, ההגשה לא אמורה להכיל קבצים שלא היו ב- zip המקורי שאנחנו סיפקנו לכם. |