שאלה בנוגע לBFS

מנהל: TA_Isana

שלח תגובה
guygreen
הודעות: 3
הצטרף: 18:46 28/10/2009

שאלה בנוגע לBFS

שליחה על ידי guygreen » 16:14 11/06/2010

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

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

ronenhe
הודעות: 182
הצטרף: 10:27 28/10/2009

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

שליחה על ידי ronenhe » 17:09 11/06/2010

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

guygreen
הודעות: 3
הצטרף: 18:46 28/10/2009

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

שליחה על ידי guygreen » 18:08 11/06/2010

עדיין לא ברור, רשום הרי אין לקשתות משקלות ולכן אי אפשר באמת להגיד שזה כמו המרחק מהבית שלי לאוניברסיטה
אם אתה מתכוון שזה פשוט מספר הקשתות... אז זה עדיין בעייתי... כי אז זה פשוט מספר הקודקודים במסלול פחות אחד...

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

TA_Yakim
הודעות: 53
הצטרף: 19:54 03/06/2010

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

שליחה על ידי TA_Yakim » 18:16 11/06/2010

ענו לך יפה

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

ronenhe
הודעות: 182
הצטרף: 10:27 28/10/2009

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

שליחה על ידי ronenhe » 19:02 11/06/2010

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

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

danny
הודעות: 64
הצטרף: 12:32 23/10/2009

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

שליחה על ידי danny » 23:14 11/06/2010

Kudos על התשובה
Error is Created. Truth is Eternal. Error, or Creation, will be Burned up, & then, & not till Then, Truth or Eternity will appear

guygreen
הודעות: 3
הצטרף: 18:46 28/10/2009

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

שליחה על ידי guygreen » 18:40 13/06/2010

תודה רונן! (אם לא היית כותב את כל השטויות אין סיכוי שהייתי מבין)
:mrgreen:

שלח תגובה

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