שאלה לגבי עבודה 6

מנהל: TA_Isana

שאלה לגבי עבודה 6

הודעהעל ידי Brk » 16:49 11/07/2010

שאלה לגבי עבודה 6 תרגיל 3 סעיף ד': כול המשקולות הם 2 או 3
בתשובות שפורסמו בכלל אין התייחסות למשקל 3 או 2 ולא ברור איך לפתור את זה? זה נראה כאילו נרשם פיתרון כללי או פיתרון שלא קשור לסעיף ד'
אם אפשר הסבר יותר מובן לפיתרון הבעיה אני אשמח תודה :o
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: שאלה לגבי עבודה 6

הודעהעל ידי ronenhe » 18:19 11/07/2010

קצת קשה להסביר רקורסיות אבל אני אנסה..
תנסה להסתבכל על השאלה כעל מעגלים כאשר קודקוד S נמצא באמצע
אחריו יש עוד מעגל בו נמצאים כל הקודקודים במרחק 1 ברור למעשה כי כל שכן ישיר נמצא במרחק הכי קצר לS ולא משנה מה המרחק שלו..
שאתה מגיע לשורה שנייה התמונה משתנה. נסתכל נגיד על קודקוד V איך תדע מה המסלול הכי קצר ל S אתה פשוט תראה מבין השכנים שלו שנמצאים במעגל הראשון מי במרחק הכי קצר.. אני אנסה לרשום את זה למרות שזה קצת קשה
S
וברמה הראשונה נמצאים הקודקודים עם המשקלים הבאים:
3 2 3 3 3
ולצורך העניין V מקושר לכולם.. ברור כי עדיף לנו לעבור דרך הקודקוד באורך 2
ככה למעשה אנחנו מכסים עוד מעגל ועוד מעגל
ככה שבמעגל ה K כולם מעודכנים..
ואז שיש לך קודקוד במרחק K+1 אתה הולך באותה דרך.. בודק מבין השכנים שלו ברמה K מי הכי קצר... זה מה שאני הבנתי אז קח את זה בעירבון מוגבל..
אני מאמין שהבנתי נכון אבל אני אשמח אם יתקנו אותי.. את הניתוח רשמו שם ואני מאמין שאם תבין את מה שאמרתי יהיה לך קל להבין את הניתוח זמן ריצה..
שיהיה לך המון בהצלחה במועד ב!
ronenhe
 
הודעות: 182
הצטרף: 10:27 28/10/2009

Re: שאלה לגבי עבודה 6

הודעהעל ידי Brk » 18:26 11/07/2010

שאלה נוספת לגבי שאלה 5 סעיף א':תארו אלגוריתם המוצא האם יש מסלול מs לt באורך אי זוגי?
לא כול כך מובן הפיתרון ומדוע צריך להסתבך כול כך עם בניית גרף חדש. לא עדיף לשנות את הBFS במקצת כשייתן עדיפות למסלולים אי זוגיים מינימלים מאשר מסלולים זוגיים מינימלים.
כלומר אם נתחיל סריקת BFS מקודקוד s ונגיע לקודקוד t כשהוא אפור ונבדוק שהמרחק שנבחר עבורו (d(t,הוא זוגי אז נבדוק אם הקודקוד שאנחנו עומדים עליו V המרחק שלו מ-s
פלוס אחד יתן לנו מרחק אי זוגי של t לs.
בכול אופן לא הבנתי את הפיתרון הרשום,אם מישהוא יוכל להסביר לי ,אני אשמח :D .

תודה לבחור שענה לי למעלה :lol:
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: שאלה לגבי עבודה 6

הודעהעל ידי ronenhe » 18:40 11/07/2010

אני אנסה להסביר גם את השאלה הזאת יש לך גרף חדש ובכל קודקוד יש לך שני כניסות
כניסה זוגית וכניסה איזוגית.. כמו שהיו לך 3 צבעים מקודם יהיה לך גם עכשיו 3 צבעים אבל לכל כניסה..
ככה שאם יש לך כניסה זוגית אז אשרייך כנל לגבי כניסה אי זוגית..
ככה אתה ממלא את כל הכניסות האפשריות.. גם זוגיות וגם אי זוגיות..
זה כל הקטע פה.. הבעיה במה שאמרת זה שאם אתה נותן עדיפות רק לזוגיים אז אחד לפני הזוגי יהיה גם זוגי... ואז הוא לא יספר.. ואז לא תגיע למה שאתה צריך..
יש לך כפילות במספר הקודקודים.. אבל זה בסדר מבחינת הזמן ריצה (בO שלך זה תקין)
מקווה שהייתי ברור..
ronenhe
 
הודעות: 182
הצטרף: 10:27 28/10/2009


חזור אל - מבני נתונים 2010

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 2 אורחים