הרחבת האלגוריתם של Dijkstra

[gufiya]

הרחבת האלגוריתם של Dijkstra

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

 

[vinney]

הפתרון הוא רדוקציה לאלגוריתם הרגיל

תפריד את הmuxים לכמה צמתים, כל אחד הכולל את הקשתות המותרות פר קונפיגורציה, ותפעיל את האלגוריתם הרגיל.

 

[gufiya]

אבל לגבי חיבור של שני MUX אחד לשני תהיה בעיה

קודם כל חשוב להתייחס גם לנושא קיבולות, לא אמרתי את זה בשאלה המקורית. נקודה נוספת - הגרף לא מכוון. נראה לי שתהיה בעיה עם שני MUX-ים צמודים. נגיד בדוגמה המצ"ב: יש לי שני MUX-ים שמחוברים ראש בראש (out ל-out) עם קשת בקיבולת 16. לכל MUX יש שתי כניסות (in) עם קשתות לצמתים אחרים בגרף בקיבולת 4 ו-12. סה"כ 3 קשתות מחוברות לכל MUX (כאשר אסור לזרימה שמגיעה מ-in להמשיך בקשת in אחרת, וכנ"ל לגבי out כמובן). הייתי מצרף קובץ אם הפורום היה מרשה להעלות קבצים. איך היה נראה הגרף השקול? לדעתי בכל בנייה שתגדיר תהיה זרימה לא חוקית. לכן המסקנה שלי היתה לחפש פתרון מצד האלגוריתם ולא הבנייה של הגרף...

 

[vinney]

אתה תיארת גרף מכוון

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

 

[gufiya]

לא תיארתי גרף מכוון...

in ו-out זה רק לצורך המחשה. מה שחשוב הוא שיש שני *סוגים* של פורטים (פורט הוא חיבור של קשת מסוימת לצומת מסוים). אם אתה מעדיף אפשר לדבר במושגים של תקשורת נתונים - trib ו-aggregate. כעקרון ב-MUX יש כמה trib-ים, בקיבולת נמוכה, ולרוב agg אחד בקיבולת יותר גבוהה. הזרימה היא בין ה-trib ל-agg, או להיפך, כלומר אין חשיבות לכיוון, אבל לעולם לא בין שני פורטים מאותו סוג (agg ל-agg או trib ל-trib).

 

[vinney]

אז מה השאלה?

האלגוריתם יודע מאיפה הוא הגיע, הוא יתפשט רק בקשתות מהסוג ההפוך.

 

[gufiya]

הבעיה היא

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

 

[vinney]

אז תשנה את האלגוריתם שיבדיל

מה הבעיה?

 

[gufiya]

זאת בדיוק הבעיה: איך עושים את זה?

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

 

[vinney]

למה זה לא טריויאלי?

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

 

[gufiya]

אולי

ייתכן. אני צריך לחשוב על זה יותר לעומק ואולי זה באמת פשוט מאד. מצד שני לא רוצה להמציא את הגלגל ומכאן השאלה שלי. תודה בכל אופן !