שלום לכולם, חידה שלא הצלחתי

[XVertex]

שלום לכולם, חידה שלא הצלחתי

נתון גרף עם משקלים על הצלעות, בעל מבנה כמו בתמונה. צריך למצא את המסילה בעלת המשקל המינימלי מקודקוד START ל FINISH. הבעיה היא... שצריך לעשות את זה לינארית...

רעיונות?

 

[XVertex]

המשקלים אי-שליליים

המשקלים בציור לדוגמה בלבד - צריך פתרון כללי..

 

[ron369]

תפרק את זה לקלקים לינאריים בגודלם.

 

[asparagos]

לא הבנתי למה אתה מתכוון...

קלקים = חלקים? לאיזה חלקים? ואחרי שזה מפורק מה עושים עם החלקים?

 

[ron369]

סליחה, "חלקים", באותו רגע די מיהרתי

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

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

 

[XVertex]

../images/Emo5.gif עכשיו הכל ברור

 

[ron369]

מצטער, עכשיו הראש שלי לא בהסברים

אולי מחר אני אחשוב יותר טוב איך להסביר זאת

 

[rmn86]

לינארית במה?

זמן לינארי במספר הצמתים\הקשתות? במה? ומאיזה קורס זה לקוח? חבל שאני אבזבז את הזמן שלי על משהו שאני לא אמור לדעת לפתור =]

 

[ron369]

לינארי בגודל הקלט, כנהוג במתמ' ../images/Emo13.gif

(חכה חכה לחישוביות)

 

[XVertex]

קורס אלגוריתמים

לינארי במספר הקשתות/צמתים במקרה הזה זה אותו דבר. שים לב לתלות לינארית בין מספר הקודקודים לקשתות. מספר הקשתות - E מספר הקודקודים - V E = V + (V-2)/2 אני חושב שאולי אלגוריתם דיקסטרה כפשוטו עובד על גרפים מהצורה הזו בסיבוכיות לינארית... בינתיים אני לא מצליח להוכיח את זה...

 

[ברונסקי]

...

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