אלגוריתמים, רשתות ותכנון לינארי
הוצג| English | משמעות |
|---|---|
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | עץ פריסה מינימלי |
הרשת הזולה ביותר או הדרך הקצרה ביותר?
- בית ספר צריך לחבר בניינים באמצעות כבל. הדרך הקצרה ביותר בין שני בניינים והרשת הזולה ביותר הן בעיות שונות.
- שיעור זה לומד עץ כיסוי מינימלי: רשת מחוברת ללא מחלקות המכסה כל קודקוד עם משקל קצה כולל מינימלי אפשרי.
בחר את המבנה המתמטי
- קרסקאל בוחר קצוות במשקל עולה תוך הימנעות ממחלקות. דייקסטרה מעדכן מרחקים זמניים קצרים מקודקוד התחלה. תכנון ליניארי אופטימיזציה פונקציית מטרה ליניארית על אזור תפקודי; בדוק קודקודים והגבלות שלמות כאשר נדרש.
- ציין את הקלט המותר והיחידות לפני החישוב. משוואה צריכה לבטא את הקשר, ולא רק לתעד כניסה למחשבון.
אלגוריתמי קרסקאל וקצר-מסלול נתנו סך כולל של 6 ברשת הדוגמה. מדוע דבר אינו הופך אותם להחלפתים?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
המטרות שונות: עץ כיסוי מחבר את כל הקודקודים (n-1 קשתות, ללא מחלקות), בעוד שמסלול קצר אופטימיזי מסלול מקור-יעד יחיד. תשובות שוות כאן הן מקרה.
עבור על מקרה שנבדק
- בדוק את התוצאה מול הכמויות ההתחלתיות. הצב את התוצאה במשוואה המקורית, או השוו את הגרף לתשובה המספרית כאשר מתאים.
עבור קודקודים A,B,C,D וקשתות AB=2, BC=3, AC=4, CD=1, BD=5, Kruskal בוחר CD,AB,BC לסך כולל 6. המסלול הקצר ביותר מ-A ל-D הוא A-B-C-D, גם כן 6, אך שוויון זה מקרי. מקסמו 3x+2y עם x+y≤4, x≤2, x,y≥0: הקודקוד הטוב ביותר הוא (2,2), הערך 10.
אלגוריתמים, רשתות ותכנון לינארי
קרוסקל בוחר קשרים במשקל עולה תוך הימנעות מציקלים
השוו בין הדגם לבין המקרה המוצר והסבר שינוי אחד.
מצאו את משקל עץ הכיסוי המינימלי לדוגמת הרשת.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
קרוסקל בוחר משקלי קשרים 1,2,3 ללא ציקל, המקשרים כל ראש: סך הכל 6.
בדיקת קיצור דרך מפתה
- עץ כיסוי אינו מכיל מחלקות ומכסה את כל הקודקודים. הקצה היחיד הגדול ביותר אינו נשלל אוטומטית מכל פתרון מיטבי. אלגוריתם מרחק קצר לא יכול להחליף אלגוריתם עץ כיסוי מינימלי.
- כאשר קיצור דרך נכשל, זיהה את ההנחה שהוא מפר. שמור על ערך מדויק עד לעיגול הסופי המבוקש.
מרחק קצר ביותר בין שני קודקודים חייב להיות גם עץ כיסוי מינימלי של כל הרשת. טענה זו שגויה. הסבר האילו הגדרה או הנחה היא מפרה.
מצאו את המקסימום של 3x+2y עבור אזור האפשריות לדוגמה.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
בדקו את הראשים האפשריים: (2,2) נותן 3×2+2×2=10, הערך הגבוה ביותר לפונקציית המטרות.
מסלול הקצר ביותר בין שני ראשים חייב להיות גם עץ כיסוי מינימלי לכל הרשת.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
עץ כיסוי אינו מכיל ציקלים ומחבר את כל הראשים. הקו הבודד הארוך ביותר אינו מושלם באופן אוטומטי מכל פתרון אופטימלי. אלגוריתם מסלול קצר לא יכול להחליף אלגוריתם עץ כיסוי מינימלי.
פרשן מצב חדש
- עבור מסילות קריטיות, חשב את הזמנים המוקדמים והמאוחרים ביותר לאירועים וזהה פעילויות עם זמן שינוי אפסי. ציין יחידות ופרש את האופטימום. הארכיון הקיים אינו מכיל זוגות D1, ולכן משימות מקוריות אלו אינן מקימות בנק עמודי מבחן D1 מאומת.
- פתרון מלא נותן את התוצאה המתמטית ומסביר את משמעותה. בדוק האם הדבר אפשרי בהקשר המפורש.
כמה קשרים יש לעץ כיסוי על 4 ראשים?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
עץ על n ראשים בעל n-1 קשרים, ולכן ארבעה ראשים זקוקים לשלושה.
התאם כל אלגוריתם לכלל שלו.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
כל אלגוריתם הוא מדויק לקטגוריית הבעיה שלו; מעקב אחרי הכלל הנ stated, כולל טיפול במקרים שווים, הוא מה שמביא נקודות.
השתמש בזה בקורס שלך
- מתמטיקה IAL של אדקסל; יחידה רשמית D1. עושר מיוחדות אחרות מזוהה בסקירת ההיקף; הוא אינו דרישה לתוספת תשלום.
- תן את השיטה לפני התשובה הסופית, והשתמש בכללי המחשבון והנוסחות של המבחן. סקור תשובה שגויה על ידי מיקום השלב הראשון שאינו תקין.
רשת מחוברת ללא מחזוריות המחברת כל צומת עם משקל קצה כולל מינימלי ככל האפשר. בחר את הקשר, הצג את השיטה, בדוק את ההנחות ופרש את התוצאה.