Sorting, packing and network algorithms
הוצג| English | משמעות |
|---|---|
| algorithm/ˈælɡərɪθəm/ | אלגוריתם |
האם שיטת אריזה מהירה היא תמיד אופטימלית?
- שיטת אריזה ממלאת קופסאות במהירות, אך סידור תקף מהודר אינו חייב להשתמש במספר הקופסאות המינימלי.
- שיעור זה עוסק באלגוריתם: קבוצה סופית של הוראות מסודרות פותרת מחלקה מוגדרת של בעיות.
בחר את המבנה המתמטי
- עקוב אחר האלגוריתם המצוין במדויק, כולל כללי פיצול שוויון. באריזה First-Fit, הנח כל פריט בקופסה הראשונה הזמינה שתוכל להכיל אותו. First-Fit Decreasing ממיין לפני יישום First-Fit. היוריסטיקה עשויה להיות תקפה מבלי להיות אופטימלית.
- ציין את הקלט המותר והיחידות לפני החישוב. משוואה צריכה לבטא את הקשר, ולא רק לתעד כניסה למחשבון.
First-fit used 2 bins for 6,5,4,3,2 with capacity 10, matching the lower bound. What may be concluded?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Meeting the lower bound proves optimality for this case only. A heuristic’s success on one example says nothing about worst cases - other item lists make first-fit exceed the bound.
עבור על מקרה שנבדק
- בדוק את התוצאה מול הכמויות ההתחלתיות. הצב את התוצאה במשוואה המקורית, או השוו את הגרף לתשובה המספרית כאשר מתאים.
עם קיבולת קופסה 10 ופריטים 6,5,4,3,2 בסדר זה, First-Fit מניח את 6 ו-4 בקופסה 1, ולאחר מכן 5,3,2 בקופסה 2. היא משתמשת ב-2 קופסאות. הסך הכל של הגודל הוא 20, ולכן הגבול התחתון הוא ceil(20/10)=2; סידור זה הוא אופטימלי לדוגמה זו.
Sorting, packing and network algorithms
Trace the named algorithm exactly, including its tie rules
Compare the model with the worked case and explain one change.
How many bins does the worked first-fit arrangement use?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The first-fit arrangement fills two bins, each with total size 10.
בדיקת קיצור דרך מפתה
- דוגמה להצלחה אינה מוכיחה שהיוריסטיקה היא תמיד אופטימלית. שמור רשימות ביניים בתרגול מיון; אל תדלג מכניסה לרשימה מסודרת סופית. עדכון מסלול קצר חייב לשמור על מידע מדורג אם נדרש מסלול.
- כאשר קיצור דרך נכשל, זיהה את ההנחה שהוא מפר. שמור על ערך מדויק עד לעיגול הסופי המבוקש.
היוריסטיקת אריזה שעובדת היטב בדוגמה אחת חייבת להיות תמיד אופטימלית. טענה זו שגויה. הסבר איזה הגדרה או הנחה היא מפרה.
Find the lower bound on bins for total size 20 and capacity 10.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Every bin holds at most 10, so at least ceiling(20/10)=2 bins are needed.
A packing heuristic that works well on one example must always be optimal.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
An example of success does not prove a heuristic is always optimal. Keep intermediate lists in a sorting trace; do not jump from input to a sorted final list. A shortest-path update must retain predecessor information if a route is requested.
פרשן מצב חדש
- עבור אלגוריתם דייקסטר, בחרו את התווית הזמנית הלא-מעובדת הקטנה ביותר ועדכנו את השכנים שלה. בבעיות בדיקת מסלול, הבדילו בין מסלול סגור לפתוח וזהו קודקודים זרים לפני ההתאמה.
- פתרון מלא נותן את התוצאה המתמטית ומסביר את משמעותה. בדוק האם הדבר אפשרי בהקשר המפורש.
Find space remaining in a bin containing items 5,3,2 with capacity 10.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Unused capacity=10-(5+3+2)=0.
Match each packing rule to its action.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Trace the algorithm exactly as defined; the lower bound judges how good a packing could possibly be.
השתמש בזה בקורס שלך
- מתמטיקה IAL של אדקסל; יחידה רשמית D1. עושר מיוחדות אחרות מזוהה בסקירת ההיקף; הוא אינו דרישה לתוספת תשלום.
- תן את השיטה לפני התשובה הסופית, והשתמש בכללי המחשבון והנוסחות של המבחן. סקור תשובה שגויה על ידי מיקום השלב הראשון שאינו תקין.
סט סופי של הוראות מסודרות הפותר מחלקה מוגדרת של בעיות. בחרו את הקשר, הצגו את השיטה, בדקו את ההנחות והעלו תוצאה.