תכנון דינאמי-מסלול קצר ביותר מ- s לכל v שעובר דרך קשת צהובה אחת בדיוק

[guy81]

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

הרעיון שלי הוא כזה:

נסתכל על v ועל כל הקשתות מהצורה (u,v) כלומר הקשת האחרונה במסלול.קיימות 2 אפשרויות: או שהיא צהובה או שהיא שחורה.

אם היא שחורה, נחפש opt(u) בגרף g.

אחרת אנחנו צריכים את opt(u) אבל בגרף g', שזהו הגרף g לאחר שהוסרו ממנו כל הצלעות הצהובות.

opt(v)=min{ opt(u) in g+w(u,v) for each black edge , opt(u) in g' +w(u,v) for each yellow edge} zz]

עכשיו, איך מובטח לי כאן, שתבחר בוודאות קשת צהובה?

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

[Maor_Splinter]

יעזור לנו מאוד אם תגדיר במדויק מהי "קשת צהובה" ומהי "קשת שחורה" בתור התחלה.

כתבת שאין מעגלים בגרף. האם הכוונה היא למעגלים שליליים או למעגלים בכלל?

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

[n = מס' הקודקודים בגרף, m = מס' הקשתות]

בניגוד לבלמן-פורד שבו יש (n-1) איטרציות שבכל אחת מהן מבצעים m פעולות Relax על הקשתות (עוברים על כל הקשתות בכל איטרציה), וכך מקבלים זמן ריצה של (n*m);

אם הגרף אציקלי, ניתן לפתור את הבעיה כך:

נשים לב שאם מבצעים את פעולות ה-Relax בסדר הקשתות שעל המסלול הקצר ביותר במשקל מ-s ל-v אז במעבר אחד מקבלים את התוצאה הנכונה עבור v ולכן מספיק לעבור על כל קשת פעם אחת.

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

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

נקבל זמן ריצה שהוא (n+m).

עריכה - במחשבה שנייה, יכול להיות שהפתרון שכתבתי בעזרת מיון טופולוגי הוא "התכנות הדינאמי" עבור הנוסחה הרקורסיבית שלך?

[guy81]

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