בתשובות שפורסמו בכלל אין התייחסות למשקל 3 או 2 ולא ברור איך לפתור את זה? זה נראה כאילו נרשם פיתרון כללי או פיתרון שלא קשור לסעיף ד'
אם אפשר הסבר יותר מובן לפיתרון הבעיה אני אשמח תודה
שאלה לגבי עבודה 6
מנהל: TA_Isana
שאלה לגבי עבודה 6
שאלה לגבי עבודה 6 תרגיל 3 סעיף ד': כול המשקולות הם 2 או 3
בתשובות שפורסמו בכלל אין התייחסות למשקל 3 או 2 ולא ברור איך לפתור את זה? זה נראה כאילו נרשם פיתרון כללי או פיתרון שלא קשור לסעיף ד'
אם אפשר הסבר יותר מובן לפיתרון הבעיה אני אשמח תודה
בתשובות שפורסמו בכלל אין התייחסות למשקל 3 או 2 ולא ברור איך לפתור את זה? זה נראה כאילו נרשם פיתרון כללי או פיתרון שלא קשור לסעיף ד'
אם אפשר הסבר יותר מובן לפיתרון הבעיה אני אשמח תודה
Re: שאלה לגבי עבודה 6
קצת קשה להסביר רקורסיות אבל אני אנסה..
תנסה להסתבכל על השאלה כעל מעגלים כאשר קודקוד S נמצא באמצע
אחריו יש עוד מעגל בו נמצאים כל הקודקודים במרחק 1 ברור למעשה כי כל שכן ישיר נמצא במרחק הכי קצר לS ולא משנה מה המרחק שלו..
שאתה מגיע לשורה שנייה התמונה משתנה. נסתכל נגיד על קודקוד V איך תדע מה המסלול הכי קצר ל S אתה פשוט תראה מבין השכנים שלו שנמצאים במעגל הראשון מי במרחק הכי קצר.. אני אנסה לרשום את זה למרות שזה קצת קשה
S
וברמה הראשונה נמצאים הקודקודים עם המשקלים הבאים:
3 2 3 3 3
ולצורך העניין V מקושר לכולם.. ברור כי עדיף לנו לעבור דרך הקודקוד באורך 2
ככה למעשה אנחנו מכסים עוד מעגל ועוד מעגל
ככה שבמעגל ה K כולם מעודכנים..
ואז שיש לך קודקוד במרחק K+1 אתה הולך באותה דרך.. בודק מבין השכנים שלו ברמה K מי הכי קצר... זה מה שאני הבנתי אז קח את זה בעירבון מוגבל..
אני מאמין שהבנתי נכון אבל אני אשמח אם יתקנו אותי.. את הניתוח רשמו שם ואני מאמין שאם תבין את מה שאמרתי יהיה לך קל להבין את הניתוח זמן ריצה..
שיהיה לך המון בהצלחה במועד ב!
תנסה להסתבכל על השאלה כעל מעגלים כאשר קודקוד S נמצא באמצע
אחריו יש עוד מעגל בו נמצאים כל הקודקודים במרחק 1 ברור למעשה כי כל שכן ישיר נמצא במרחק הכי קצר לS ולא משנה מה המרחק שלו..
שאתה מגיע לשורה שנייה התמונה משתנה. נסתכל נגיד על קודקוד V איך תדע מה המסלול הכי קצר ל S אתה פשוט תראה מבין השכנים שלו שנמצאים במעגל הראשון מי במרחק הכי קצר.. אני אנסה לרשום את זה למרות שזה קצת קשה
S
וברמה הראשונה נמצאים הקודקודים עם המשקלים הבאים:
3 2 3 3 3
ולצורך העניין V מקושר לכולם.. ברור כי עדיף לנו לעבור דרך הקודקוד באורך 2
ככה למעשה אנחנו מכסים עוד מעגל ועוד מעגל
ככה שבמעגל ה K כולם מעודכנים..
ואז שיש לך קודקוד במרחק K+1 אתה הולך באותה דרך.. בודק מבין השכנים שלו ברמה K מי הכי קצר... זה מה שאני הבנתי אז קח את זה בעירבון מוגבל..
אני מאמין שהבנתי נכון אבל אני אשמח אם יתקנו אותי.. את הניתוח רשמו שם ואני מאמין שאם תבין את מה שאמרתי יהיה לך קל להבין את הניתוח זמן ריצה..
שיהיה לך המון בהצלחה במועד ב!
Re: שאלה לגבי עבודה 6
שאלה נוספת לגבי שאלה 5 סעיף א':תארו אלגוריתם המוצא האם יש מסלול מs לt באורך אי זוגי?
לא כול כך מובן הפיתרון ומדוע צריך להסתבך כול כך עם בניית גרף חדש. לא עדיף לשנות את הBFS במקצת כשייתן עדיפות למסלולים אי זוגיים מינימלים מאשר מסלולים זוגיים מינימלים.
כלומר אם נתחיל סריקת BFS מקודקוד s ונגיע לקודקוד t כשהוא אפור ונבדוק שהמרחק שנבחר עבורו (d(t,הוא זוגי אז נבדוק אם הקודקוד שאנחנו עומדים עליו V המרחק שלו מ-s
פלוס אחד יתן לנו מרחק אי זוגי של t לs.
בכול אופן לא הבנתי את הפיתרון הרשום,אם מישהוא יוכל להסביר לי ,אני אשמח
.
תודה לבחור שענה לי למעלה
לא כול כך מובן הפיתרון ומדוע צריך להסתבך כול כך עם בניית גרף חדש. לא עדיף לשנות את הBFS במקצת כשייתן עדיפות למסלולים אי זוגיים מינימלים מאשר מסלולים זוגיים מינימלים.
כלומר אם נתחיל סריקת BFS מקודקוד s ונגיע לקודקוד t כשהוא אפור ונבדוק שהמרחק שנבחר עבורו (d(t,הוא זוגי אז נבדוק אם הקודקוד שאנחנו עומדים עליו V המרחק שלו מ-s
פלוס אחד יתן לנו מרחק אי זוגי של t לs.
בכול אופן לא הבנתי את הפיתרון הרשום,אם מישהוא יוכל להסביר לי ,אני אשמח
.תודה לבחור שענה לי למעלה
Re: שאלה לגבי עבודה 6
אני אנסה להסביר גם את השאלה הזאת יש לך גרף חדש ובכל קודקוד יש לך שני כניסות
כניסה זוגית וכניסה איזוגית.. כמו שהיו לך 3 צבעים מקודם יהיה לך גם עכשיו 3 צבעים אבל לכל כניסה..
ככה שאם יש לך כניסה זוגית אז אשרייך כנל לגבי כניסה אי זוגית..
ככה אתה ממלא את כל הכניסות האפשריות.. גם זוגיות וגם אי זוגיות..
זה כל הקטע פה.. הבעיה במה שאמרת זה שאם אתה נותן עדיפות רק לזוגיים אז אחד לפני הזוגי יהיה גם זוגי... ואז הוא לא יספר.. ואז לא תגיע למה שאתה צריך..
יש לך כפילות במספר הקודקודים.. אבל זה בסדר מבחינת הזמן ריצה (בO שלך זה תקין)
מקווה שהייתי ברור..
כניסה זוגית וכניסה איזוגית.. כמו שהיו לך 3 צבעים מקודם יהיה לך גם עכשיו 3 צבעים אבל לכל כניסה..
ככה שאם יש לך כניסה זוגית אז אשרייך כנל לגבי כניסה אי זוגית..
ככה אתה ממלא את כל הכניסות האפשריות.. גם זוגיות וגם אי זוגיות..
זה כל הקטע פה.. הבעיה במה שאמרת זה שאם אתה נותן עדיפות רק לזוגיים אז אחד לפני הזוגי יהיה גם זוגי... ואז הוא לא יספר.. ואז לא תגיע למה שאתה צריך..
יש לך כפילות במספר הקודקודים.. אבל זה בסדר מבחינת הזמן ריצה (בO שלך זה תקין)
מקווה שהייתי ברור..