הבהרת ניסוח האלגוריתם תרגיל 5 חלק ב

מנהל: TA_Isana

שלח תגובה
ayeletd
הודעות: 27
הצטרף: 19:25 17/11/2008

הבהרת ניסוח האלגוריתם תרגיל 5 חלק ב

שליחה על ידי ayeletd » 16:37 26/06/2009

היי,

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

דבר נוסף שאינו ברור בניסוח (שאגב גם המרצה בכמט לא הצליח לפענח.....) :
" לכל זוג ב A מהצורה (v,U ):
אם U לא ברשימה B מצא את הערך של U, אם העלות בערימה גבוהה יותר שנה אותה לזו של הזוג (V,U )"
* למה הכוונה במציאת ערך של איבר בודד U (לא זוג) ?
* העלות של מי בערימה יותר גבוהה?
* מה זאת אומרת שנה את העלות, לשנות את העלות של מי? ולמה יש הגיון בשינוי עלות של זוג?
* מה הרעיון בבדיקת הזוגות (v,u ) שב A , הרי אנחנו יודעים שהזוג (v,e) הוא הכי קטן....

שאלתי הרבה אני יודעת.... אבל העבודה פשוט לא מנוסחת בצורה ברורה ...

שבת שלום
איילת

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

שליחה על ידי TA_Ariel » 18:32 26/06/2009

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

לגבי "הרי אנחנו יודעים שהזוג (v,e) הוא הכי קטן...." זה לא נכון
הרי בתחילה העלות היא maxint וגם לאחר עדכון לא בהכרח מקבלים שעלות הזוג e היא המינימלית מבין כל ההשכנים של v.

ayeletd
הודעות: 27
הצטרף: 19:25 17/11/2008

שליחה על ידי ayeletd » 18:47 26/06/2009

ההסברים עדיין לא ברורים .... ומה לגבי שאר השאלות?
איילת

keller
הודעות: 1
הצטרף: 19:30 26/06/2009

הבהרת הפסדו קוד בחלק האחרון של העבודה

שליחה על ידי keller » 19:39 26/06/2009

השאלה רלוונטית גם לגבי, בעיקר לגבי "מצא את הערך של U בערמה, אם העלות בערמה גבוהה יותר שנה אותה לזו של הזוג (u,v)"

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

Biaxident
הודעות: 24
הצטרף: 18:21 26/11/2008

שליחה על ידי Biaxident » 13:45 27/06/2009

כמה שאלות לגבי האלגוריתם

1. למה האיתחול של האיברים בערמה A הוא (איבר, maxint, null) אם אנחנו מקבלים את כל הערכים האילו מקובץ הקלט?

2. מה הכוונה במשפט:
"מצא את הערך של u בערמה, אם העלות בערמה גבוהה יותר שנה אותה לזו של הזוג (u,v)"?

תודה

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

שליחה על ידי TA_Ariel » 19:32 27/06/2009

1. אין קשר בין אתחול הערימה לנתונים שמקבלים כקלט. הנתונים מהקלט משמשים רק בשביל לעכן את בערימה בכל צעד , ולבחור את הדרך האופטימלית לכל איבר . העלות של איבר בערימה מייצגת בעצם את המשקל המינמלי בין האיבר לבין השכנים שלו שכבר בB.

2. מוצאים את u בערימה ובודקים מה העלות שלו , אם העלות של v,u נמוכה יותר אז מחליפים את העלות של האיבר לזו של הזוג v,u .

העלות בערימה היא של איברים. והיא מייצגת את מה שכתבתי בתשובה ל1.

שלח תגובה

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