קיים אלג' פולי' למסלול קצר ביותר ?

[johnny d]

קיים אלג' פולי' למסלול קצר ביותר ?

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

 

[yuvalmadar]

BFS? דייקסטרה? בלמן פורד?

(תלוי במשקלות)

 

[johnny d]

במקרה הכללי.

האלגוריתמים האלו, פותרים תתי בעיות של הבעיה: BFS - uncapacitated dijkstra - non-negative weights bellman-ford - no negative cycles

 

[yuvalmadar]

הממ.. שכחתי את המעגלים באמת ../images/Emo13.gif

תודה!

 

[johnny d]

nevermind that, its NP-hard

 

[yuvalmadar]

יש בזה מן ההגיון עכשיו כשמדובר גם

בגרפים עם מעגלים שליליים. האם כפל כל המשקלות במינוס 1 לא יהווה רדוקציה מבעיה אחת לשניה? (או שאני מפספס משהו?)

 

[ron369]

אתה מפספס משהו ../images/Emo13.gif

קח את המסלול הכי קצר, כפול את כל הקשתות ב-1, ותקבל את המסלול הכי ארוך, נכון?

 

[ron369]

או שלא ../images/Emo10.gif

 

[vinney]

../images/Emo6.gif

 

[ron369]

להגנתי,

אם לוקחים min-cut, ומוסיפים קשתות שליליות, מקבלים רדוקציה מאד פשוטה ל-max-cut, שהיא בעיית NPC

 

[ron369]

ובמחשבה שניה!

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

 

[ron369]

ובמחשבה שלישית, זה בדיוק מה שיובל

אמר. אני מאד מאד איטי היום, ככל הנראה.

 

[vinney]

תרחיב זכרון

עושה פלאים למהירות

 

[ron369]

../images/Emo6.gif

אני די משוכנע שפעולה כזו לא תהיה קלה

 

[johnny d]

דווקה כן

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

 

[johnny d]

החלק המעניין זה ההוכחה

ללא הנתון כי הבעיה הנגדית קשה

 

[yuvalmadar]

תועיל לשתף אותי בהוכחה? ../images/Emo13.gif

(לא למדתי עדיין אף קורס בחישוביות/סיבוכיות, אגב)

 

[johnny d]

התכוונתי שמעניין לנסות להבין לעומק

את העניין. הוכחות לא חסר, ההוכחה הכי פשוטה היא עם מעגל המילטון. יש גם גרסה של רדוקציה לTSP, ואחת שע"י מסחק עם תוכנית בשלמים הופכת את knapsack ל- longest path. העסק הזה ממש מבלבל, אבל הוא גם מעניין באותה המידה.

 

[yuvalmadar]

מסכים, אני לא יכול שלא לחכות

עד שאלמד את זה.

 

[אמיתי ר]

באלגוריתמיקה, תלמד קצת

בנושא. אני מצאתי את הנושא מאוד מרתק

בהחלט יהיה לך כיף כקורס קיץ