Amit (guest) 20 Jun 2011 19:45
שלום,
בבחינה של מיכה שריר סמסטר ב' תשסו, מועד א', שאלה 2.
יש שאלה שבה צריך למצוא מסלולים קל ביותר מצומת S לכל צומת V בגרף לא מכוון, באורך של מספר הצמתי חלקי 10 בדיוק.
הפתרון שלי לשאלה (לפחות לסעיף הראשון) הוא פיצול כל צומת לv/10 בדיוק כפי שעשינו בשעורי הבית, אומנם בסעיף ב' מבקשים למצוא את כל המסלולים בין כל הצמתי כלומר APSP באורך הנ"ל.
האם הפתרון הוא לעשות FAST APSP על הצמתים המפוצלים וכאשר עוברים את החזקה המדוברת לחפש בינארית עד שמגיעים לחזקת V/10? ואז להתסכל על כל המסלולים בין v0 - u(v/10? מדובר ב מטריצה בגודל v^4!
איך אני יכול לשמור על מסלול באורך מדויק? יש סריקת פתרון של סטודנט ששם הוא עושה כפל בוליאני תוך כדי שמירה על המרחקים אבל זה עדיין בדיוק אותו הדבר.. אני לאו דווקא מבטיח שהמסלול יהיה באורך המדוייק אלא רק חסם עליון (אם קיים מסלול קצר יותר).
תודה!!
עמית.
