דף 1 מתוך 1

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

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

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

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

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

שבת שלום

נשלח: 18:32 26/06/2009
על ידי TA_Ariel
לא מכניסים את הרשימה לערימה , מכניסים את האיברים השונים בזוגות
כלומר אם מקבלים את הזוג a,b אז מכניסים שני איברים לערימה ולא אחד.
איבר בערימה (בניגוד לזוגות ) הוא שלשלה כמו שמתואר בעבודה,
כשהמיון של הערימה הוא לפי עלות.

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

נשלח: 18:47 26/06/2009
על ידי ayeletd
ההסברים עדיין לא ברורים .... ומה לגבי שאר השאלות?

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

נשלח: 19:39 26/06/2009
על ידי keller
השאלה רלוונטית גם לגבי, בעיקר לגבי "מצא את הערך של U בערמה, אם העלות בערמה גבוהה יותר שנה אותה לזו של הזוג (u,v)"

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

נשלח: 13:45 27/06/2009
על ידי Biaxident
כמה שאלות לגבי האלגוריתם

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

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

תודה

נשלח: 19:32 27/06/2009
על ידי TA_Ariel
1. אין קשר בין אתחול הערימה לנתונים שמקבלים כקלט. הנתונים מהקלט משמשים רק בשביל לעכן את בערימה בכל צעד , ולבחור את הדרך האופטימלית לכל איבר . העלות של איבר בערימה מייצגת בעצם את המשקל המינמלי בין האיבר לבין השכנים שלו שכבר בB.

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

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