היי,

נתון לי גרף לא מכוון של ערים, בין כל עיר ועיר קיים מרחק בק"מ על הקשתות.

אני צריך למצוא את המסלולים מעיר V לעיר S , שאורכם שווה בדיוק ל-M(אורך בקילומטר) נתון.

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

למישהו אולי יש רעיון /כיוון באיזה אלגוריתם ניתן להשתמש/לשפר על מנת לקבל את הפתרון?

(ראיתי בstackoverflow גם כן הצעות דומות לעשות שימוש בדייקסטרה וDFS, אבל שם היה מדובר על מסלול שמספר הערים(צמתים) בו הוא M)

תודה!!

מדובר בבעיה שהיא NP-complete, דהיינו לא ניתן למצוא לה פתרון יעיל. אפשר למצוא פתרון (די פשוט) בסיבוכיות V*M (כאשר V = מספר הערים).

אוקיי תודה,המספר צמתים V הוא כמובן איזה מספר סופי , של ערים אפשרויות במסלול מסויים.

ואיך ניתן להגיע לסיבוכיות שציינת?זה על ידי אלגוריתם קיים כלשהו?

אתה יכול למצוא מסלול מינימלי ואם הוא קטן מ-M לפסול אותו ולבדוק שוב.

למה זה יעזור? איך "תפסול" מסלול?

ואיך ניתן להגיע לסיבוכיות שציינת?זה על ידי אלגוריתם קיים כלשהו?

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

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

חשבתי במידה ואורך המסלול המינימלי שונה מ-M לשנות את אחת הקשתות עליו לINF אבל זה יפסול מסלולים אחרים גם אז זה לא אפשרי.

ושניצל, מה שאתה מתכוון בשאלה זה מסלולים שאורכם (סכום המשקלים שעל הקשתות) זוגי?

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

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

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

יש מצב לעזרה?

תודה!!

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

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