משקל הקשת = עלות הקמה. בוחרים אילו מסילות לסלול כדי לחבר את כל נקודות הציון בעלות הקמה מינימלית.
המספרים = עלות הקמה של כל מסילה אפשרית
לחצו על «הצג פתרון» כדי לראות אילו מסילות נבחרות, מסומנות על הגרף.
✅ פתרון
תרגום לבעיה מוכרתעץ פורש מינימלי (MST)
אלגוריתםקרוסקל (או פרים)
יעילותO(E·log V)
משקל הקשת = זמן נסיעה (דק'). מוצאים את המסלול המהיר ביותר בין נקודת מוצא לנקודת יעד נתונות.
המספרים = זמן נסיעה בכל מסילה
לחצו על «הצג פתרון» כדי לראות את המסלול המהיר מסומן על הגרף.
✅ פתרון
תרגום לבעיה מוכרתמסלול קל ביותר בין זוג נקודות
אלגוריתםA* — הרחבת דייקסטרה עם פונקציית הערכה (היוריסטיקה) ליעד
יעילותעם היוריסטיקה קבילה, A* סורק פחות קודקודים מדייקסטרה
משקל הקשת = קיבולת (אלפי נוסעים/שעה). כמה אנשים יגיעו מהמוצא ליעד — מקסימום? המסילות כאן מכוונות בכיוון הזרימה.
המספרים = קיבולת המסילה · בפתרון: זרימה / קיבולת
◆ מוצא · ● יעדנוסעים זורמיםתווית: זרימה / קיבולת
לחצו על «הצג פתרון» כדי לראות את הנוסעים זורמים מהמוצא ליעד.
התשובה
15
אלף נוסעים בשעה יכולים להגיע מהמוצא ליעד
עובי המסילה ומספר הנוסעים הזורמים בה יחסיים לכמות הזרימה. כיצד מוצאים ניתוב מיטבי כזה ביעילות? זה בדיוק הנושא הבא.
🚀 הנושא הבא: זרימה מקסימלית ברשת
תרגום לבעיהזרימה מקסימלית ברשת
אלגוריתםפורד־פלקרסון / אדמונדס־קארפ
כמה יגיעו?עד 15 אלף נוסעים בשעה מהמוצא ליעד