לא מבין מה רוצים ממני

[אופסשםמשתמש]

לא מבין מה רוצים ממני

שאלה 4.ג . השאלה ממש קלה, סתם להריץ bfs , ולבדוק אם הקשת היתה איפשהו בהרצה או לא .. אבל העניין הוא, שהם רוצים שימוש ב א וב' , אין מצב שהם התכוונו לפתרון טריוויאלי כמו bfs .. מה הם רוצים ?

 

[vinney]

הם כן התכוונו

סעיפים א. וב. מוכיחים שכל קשת במסלול הקצר ביותר היא קשת חשובה. מה שנשאר לך להראות הוא שקיימת צומת כלשהי בגרף שe נמצאת על המסלול הקצר ביותר בינה לבין s.

 

[אופסשםמשתמש]

במילים אחרות

צריך לעשות BFS אם קשת E מתקבלת באחד מהמסלולים לאחד מהצמתים היא חשובה, ואם היא לא אז לא ?

 

[vinney]

משהו כזה ../images/Emo13.gif

 

[אופסשםמשתמש]

אני לא מצליח להבין איך לנסח את זה

אני עדיין מאבד את הקשר לסעיף א' וב'.. קשת חשובה, קשת שנמצאת על המסלול הקצר ביותר.. אז ברור שכל קשת על המסלול הקצר ביותר היא חשובה, זה ההגדרה שלה.. איפה נכנס א' וב' , בכלל זה אמור להיות קשה, ואצלי זה שורה אחת של פתרון. "נריץ BFS אם זה בקשתות של העץ הפורש זאת קשת חשובה" זהו

 

[ron369]

אבל שים לב, שיכול להיות

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

 

[אופסשםמשתמש]

אני לא בטוח שאני מבין

אתה אומר יכול להיות יותר ממסלול קצר ביותר אחד לצומת מסויימת , ואני עלול לפספס מסלול נוסף , אבל מה אני אפספס במקרה הזה? רק את הקשת האחרונה לצומת הזאת ? ככה אני מבין לפחות את הריצה של bfs. אז נניח בכל צומת אני אשמור את המרחק שלה ,עכשיו , אם אני בצומת שמרחקה נניח 5, ויש קשת לצומת שנמצאה כבר, אבל הצומת ההיא במרחק 6 אז אני אבדוק גם את הקשת שמחברת את 2 הצמתים.. זה אמור להביא לי את כל המסלולים הקצרים לכל הצמתים מצומת S מסויימת (אלא אם כן יש דוגמא נגדית שלא מצאתי) בקיצור אני טוען כעת שזה הרצת DFS+הבדיקה אם הצומת הבאה היא ב1 יותר רחוקה או לא .. לצערי לא הבנתי את ההסבר שלך , ובמיוחד לא הבנתי איך א' וב' קשור לעניין

 

[אופסשםמשתמש]

הקפצה

מישהו ?

 

[ron369]

לא בהכרח, יכול להיות למשל שיש לך

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

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

 

[אופסשםמשתמש]

תודה ../images/Emo13.gif

 

[lionsh]

רעיון לפתרון

נתון לך s וקשת e. לקשת e יש שני צמתים u,v. המק"ב בין s לצומת t (נקח לדוגמא) הוא המק"ב בין s ל -v ועוד המק"ב מ-v לt. כלומר: d[s,t] = d[s,v]+d[v,t] אם שני תתי מסלולים אלה הם הקלים ביותר אז גם הסכום שלהם הוא המסלול הקל ביותר (סעיף א').

 

[אופסשםמשתמש]

עוד שאלה , שנראה לי שפתרתי

רק אני צריך שמישהו יגיד שזה נראה לו הגיוני, כמו שזה נראה לי .. אני אפילו לא נדרש להוכחת נכונות (איזה מזל)