נושא הפרוייקט
מספר פרוייקט
מחלקה
שמות סטודנטים
אימייל
שמות מנחים
בחינת יעילות אלגוריתמים לפתרון בעיות המסלול הקצר ביותר בגרפים דו קריטריונים
Analyzing the Effciency of Algorithms for Solving the Bicriteria Shortest Path Problem
תקציר בעיברית
בעיית הנתיב הקצר ביותר ברשת חד קריטריונית נחקרה באופן מעמיק בספרות. חוקרים רבים פיתחו אלגוריתמים יעילים (בעלי זמן ריצה פולינומיאלי) לפתרון בעיה זו, כגון: Dijkstra (1959) ו- Bellman (1958). בתרחישים רבים בעולם האמיתי, קבלת החלטות כרוכה לעתים קרובות בהתחשבות במספר קריטריונים או יעדים. לדוגמה, בעת תכנון מסלול, ייתכן שיהיה צורך לקחת בחשבון גורמים כמו מרחק, זמן, עלות או השפעה סביבתית. מציאת הדרך הקצרה ביותר בגרפים עם קריטריונים שונים מאפשרת למקבלי החלטות לייעל את הבחירות שלהם בהתבסס על מספר קריטריונים בו זמנית. אפליקציות רבות עושות שימוש באלגוריתמים למציאת המסלול הקצר ביותר. כגון: Waze- המחפשת את הנסיעה הקצרה ביותר מנקודת מוצא ליעד, Roadnet- המחפשת את מסלול השילוח הקצר ביותר עבור סחורות ממרלו"ג למספר נקודות יעד. בפרויקט זה, בחנו את בעיית המסלול הקצר ביותר עבור שני קריטריונים (משך ועלות). הקלט לבעיה זו מכיל גרף מחובר עם צומת מקור וצומת יעד כאשר על כל קשת נתונים שני פרמטרים: מרחק המעבר ועלות המעבר לאורך הקשת. המטרה בבעיה הינה למצוא את הנתיב הקצר ביותר מהמקור ליעד במגבלות תקציב. בעייה זו ידועה כבעייה השייכת לקבוצת הבעיות ה NP קשות ולכן לא קיים אלגוריתם יעיל לפתרונה. מטרת הפרויקט הינה (i) למידת מספר אלגוריתמים לפתרון הבעיה (ii) בניית אלגוריתם יוריסטי לפתרון הבעיה (iii) תכנות כלל האלגוריתמים (iv) בחינת הביצועים של כלל האלגוריתמים בשני מישורים: זמן ריצת האלגוריתמים ואיכות ערך הפתרון. בחנו שלושה אלגוריתמים: (i) אלגוריתם מדויק – אלגוריתם דינמי המוצא את הפתרון האופטימלי באופן רקורסיבי בזמן ריצה פסאדו פולינומיאלי (ii) אלגוריתם יוריסטי שפותח במסגרת הפרויקט ומבוסס על יוריסטיקת משקול איטרטיבית של שני הקריטריונים והפיכתם לגרף בעל קריטריון יחיד. (iii) אלגוריתם קירוב FPTAS – המוצא פתרון לפי יחס קירוב 0<ε<1 המוגדר מראש, כאשר ככל ש- ε גדל כך הפתרון המתקבל מתרחק מהפתרון האופטימלי בעוד שזמן הריצה שלו קטן. כלל האלגוריתמים תוכנתו בסביבת Java-Eclipse. לאחר מכן בוצע מחקר ניסויי לבחינת איכות האלגוריתמים. ראינו שהאלגוריתם המדויק מסוגל למצוא את הפתרון האופטימלי עבור "קלט סטנדרטי" של 3,000 צמתים תוך כ- 23 דקות. עבור אלגוריתם קירוב FPTAS, זיהינו כי ישנו הבדל משמעותי בין יחס הקירוב התיאורטי (ε) לבין איכות הפתרון הממוצעת של האלגוריתם. למעשה, האלגוריתם עובד בצורה מאוד טובה כאשר מוגדר בקלט ε גדול. זאת מכיוון שבקיצור משמעותי של זמן ריצה נקבל פתרון מאוד קרוב לפתרון האופטימלי. עבור האלגוריתם היוריסטי האיטרטיבי, ראינו כי האלגוריתם יכול להתמודד עם קלטים כמעט בלתי מוגבלים בגודלם, היות והוא מתכנס מהר אך איכות הפתרון שלו פחות טובה ביחס לאלגוריתם הקירוב FPTAS. למשל, עבור "קלט סטנדרטי" של 3,000 צמתים זמן הריצה הינו כ- 2.5 שניות. בבחינה נוספת שערכנו, הבחנו כי עבור קלטים של עד 200 צמתים, תוך כעשר איטרציות בממוצע האלגוריתם מתכנס לפתרון. לסיכום, הבחנו כי האלגוריתמים הנחקרים מסוגלים לתת פתרון כמעט לכל גודל פרקטי של בעיה, בין אם בצורה מדויקת ובין אם בצורה מקורבת.
תקציר באנגלית