Sorting, packing and network algorithms
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| algorithm/ˈælɡərɪθəm/ | 算法 | suàn fǎ |
Is a fast packing method always optimal?
- A packing method quickly fills boxes, but a fast valid arrangement need not use the smallest number of boxes.
- This lesson studies algorithm 算法: A finite set of ordered instructions that solves a defined class of problems.
快速装箱法是否总是最优？
- 装箱法能快速填满箱子，但一种合法且快速的排列方式未必使用最少数量的箱子。
- 本课研究算法：一套有限且有序的指令集，用于解决某一类特定问题。
Choose the mathematical structure
- Trace the named algorithm exactly, including its tie rules. In first-fit packing, place each item in the first available bin that can hold it. First-fit decreasing sorts before applying first-fit. A heuristic may be valid without being optimal.
- State the allowed inputs and units before calculating. An equation should express the relationship, not just record a calculator entry.
选择数学结构
- 严格按照命名算法执行，包括其平局处理规则。在第一适配装箱中，将每个物品放入第一个能容纳它的可用箱中。第一适配递减排序法先排序再应用第一适配。启发式方法可能有效但不一定是最优解。
- 计算前请先明确允许的输入项和单位。方程应表达关系本身，而不仅仅是记录计算器按键过程。
Which description correctly defines algorithm?
A finite set of ordered instructions that solves a defined class of problems.
Work through a checked case
- Check the result against the starting quantities. Substitute into the original relation, or compare the graph and numerical answer where appropriate.
With bin capacity 10 and items 6,5,4,3,2 in that order, first-fit places 6 and 4 in bin 1, then 5,3,2 in bin 2. It uses 2 bins. The total size is 20, so the lower bound is ceil(20/10)=2; this arrangement is optimal for this instance.
通过验证案例进行推导
- 将结果与初始量进行比对。代入原始关系式，或在适当情况下对比图表与数值答案。
当箱子容量为 10、物品按顺序为 6,5,4,3,2 时，第一适配法将 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?
The first-fit arrangement fills two bins, each with total size 10.
Test a tempting shortcut
- 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.
- When a shortcut fails, identify the assumption it breaks. Keep an exact value until the requested final rounding.
A packing heuristic that works well on one example must always be optimal. This claim is false. Explain which definition or assumption it violates.
检验一个诱人的捷径
- 某个例子的成功并不能证明启发式方法总是最优。在排序追踪过程中请保留中间列表，不要直接从输入跳到已排序的最终列表。若需输出具体路线，最短路径更新必须保留前驱信息。
- 当捷径失效时，找出其违背的假设。保留精确值直到题目要求的最终舍入步骤。
某种装箱启发式方法在一个例子上表现良好，就必然总是最优解。此说法错误。请说明它违背了哪一定义或假设。
Find the lower bound on bins for total size 20 and capacity 10.
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.
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.
Interpret a new situation
- For Dijkstra, choose the smallest unsettled tentative label and update its neighbours. For route-inspection problems, distinguish a closed route from an open one and identify odd vertices before pairing them.
- A complete solution gives the mathematical result and explains what it means. Check that it is possible in the stated context.
解读新情境
- 对于迪杰斯特拉算法，选择最小的未定临时标签并更新其邻居。对于路线检查问题，区分闭合路线与开放路线，并在配对前识别奇度顶点。
- 完整解答需给出数学结果并解释其含义。检查其在所述背景下是否可行。
Find space remaining in a bin containing items 5,3,2 with capacity 10.
Unused capacity=10-(5+3+2)=0.
Match each part of a complete solution to its purpose.
An assumption justifies the model; a check tests the result; interpretation connects it to the question.
Use this in your course
- edexcel IAL further mathematics; official unit D1. Other-unit enrichment is identified in the scope review; it is not an extra cash-in requirement.
- Give the method before the final answer, and use the paper's calculator and formula rules. Review a wrong answer by locating the first invalid step.
A finite set of ordered instructions that solves a defined class of problems. Choose the relationship, show the method, check its assumptions and interpret the result.
将其应用于你的课程
- Edexcel IAL高等数学；官方单元D1。其他单元的补充内容已在范围审查中标识；这并非额外的加分要求。
- 在给出最终答案前先展示解题方法，并遵循试卷的计算器及公式使用规则。通过定位第一个无效步骤来复盘错误答案。
一组有限且有序的指令，用于解决某一类特定问题。需明确关系、展示方法、检验假设并解释结果。