דף 1 מתוך 1

שאלה בנוגע לBFS

נשלח: 16:14 11/06/2010
על ידי guygreen
אהלן כפרות! :shock:
יש לי שאלה למי שיכול לעזור...
אולי אני קצת דיקט, אבל כשלמדנו על אלגוריתם
BFS
למדנו שהוא טוב לשלושה דברים:
1.מוצא האם קודקוד V נגיש מקודקוד S
2.מה המרחק הקצר ביותר מ-S ל- V
3.מהו המסלול הקצר ביותר מ-S ל-V

השאלה שלי היא מה ההבדל בין 2 ל-3? בהתחשב בעובדה שמדובר בגרף ללא משקלות...
תודה! ושבת שלום

Re: שאלה בנוגע לBFS

נשלח: 17:09 11/06/2010
על ידי ronenhe
ששואלים מה המרחק הקצר ביותר תקבל מספר טבעי
2, 3 , 4000 תחשוב על זה בתור מרחק מהבית של לאוניברסיטה כאשר כל צלע היא בדיוק קילומטר..
ששואלים מהו המסלול הקצר ביותר זה הנקודות (קודקודים) שתעבור בדרך הכי קצרה (אחת מהן)
לדוגמא : הבית שלך, הרחוב של מושיקו, הקיוסק של דוד, רמזור ....... השומר הג'ינג'י המעצבן שמעכב כל אחד לחצי שעה, האוניברסיטה
מקווה שעזרתי..
:)

Re: שאלה בנוגע לBFS

נשלח: 18:08 11/06/2010
על ידי guygreen
עדיין לא ברור, רשום הרי אין לקשתות משקלות ולכן אי אפשר באמת להגיד שזה כמו המרחק מהבית שלי לאוניברסיטה
אם אתה מתכוון שזה פשוט מספר הקשתות... אז זה עדיין בעייתי... כי אז זה פשוט מספר הקודקודים במסלול פחות אחד...

כנראה שסתם אני מפספס פה משהו... תודה בכל אופן :mrgreen:

Re: שאלה בנוגע לBFS

נשלח: 18:16 11/06/2010
על ידי TA_Yakim
ענו לך יפה

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

Re: שאלה בנוגע לBFS

נשלח: 19:02 11/06/2010
על ידי ronenhe
סליחה שלא הייתי מספיק ברור..
עזוב עכשיו את הצלעות.. ואת הקודקודים
אתה הולך מהבית לאוניברסיטה בצעדים קבועים. (נניח בצעדים של מטר או 10 סנטימטר עם אתה ממש קטן :) )
תלך במסלול הכי קצר שכל צעד אתה סופר צעד..
צעד ראשון צעד שני צעד שלישי (חשוב ללכת רק על הקווים רק על הקווים שנעבור בהצלחה מבני נתונים)
בסוף קיבלת 95 כלומר המרחק מהבית שלך לאוניברסיטה הוא 95 צעדים.
עכשיו נניח שאתה חי בללה לנד וכל צעד אתה רואה משהו חדש קסום ונפלא. פעם אחת זה נסיכה קסומה פעם אחרת דרדס כחול פעם אחרת הנחיות חדשות לעבודה במבני..

ועכשיו לעניינינו.. הצעדים זה בעצם צלעות צלעות בין הדברים שאתה רואה כל מה שאתה רואה הוא קודקוד..
נניח מהבית שלך לאוניברסיטה יש לך 95 צלעות (בצורה המינימלית כי תמיד אתה יכול להגיע דרך חיפה ואז יהיה לך O(n^n) x צעדים כאלו..)
אז הבית שלך זה קודקוד V והאוניברסיטה זה קודקוד U.
בדרך יש קודקודים וקסמים אחרים לדוגמא הדרדס שאליו תגיע אחרי 56 צעדים (במסלול הזה שהוא המינימאלי למרות שדרך חיפה.....).
והמסלול שעברת זה בעצם כל הדברים (קודקודים) שראית בדרך
זה בעיקרון כל הקטע
מרחק זה "כמה"
מסלול זה "מה"/"מי"
משקולות זה כבר עניין אחר אבל חשוב קודם שתבין את זה..
אני מקווה שמרוב שטויות שדיברתי הבנת מה שניסיתי להסביר..
בהצלחה!

Re: שאלה בנוגע לBFS

נשלח: 23:14 11/06/2010
על ידי danny
Kudos על התשובה

Re: שאלה בנוגע לBFS

נשלח: 18:40 13/06/2010
על ידי guygreen
תודה רונן! (אם לא היית כותב את כל השטויות אין סיכוי שהייתי מבין)
:mrgreen: