Sorting, packing and network algorithms
Introduzido| English | Significado |
|---|---|
| route inspection | Finding the shortest closed route that travels along every edge of a network at least once. |
| algorithm/ˈælɡərɪθəm/ | algoritmo |
| sorting/ˈsɔːtɪŋ/ | Putting a list of items into order, such as ascending order. |
| bin packing/bɪn ˈpækɪŋ/ | Fitting items of given sizes into the fewest bins of a fixed capacity. |
| pivot/ˈpɪvət/ | The item chosen in quick sort, around which the list is split into smaller and larger items. |
| optimal/ˈɒptɪml/ | Describes the best possible solution to a problem. |
| degree/dɪˈɡriː/ | An angular unit equal to one three-hundred-and-sixtieth of a full turn. |
| heuristic/hjuːˈrɪstɪk/ | Describes a method that finds a good solution quickly but does not guarantee the best one. |
The Chinese postman, 1960
- In 1960, Kwan Mei-Ko (Guan Meigu), a young lecturer at Shandong Normal University, asked how a postman can walk along every street at least once and return to the post office by the shortest route. The problem is still called the Chinese postman problem, or route inspection 路线检查.
- D1 also has algorithms for sorting 排序 lists and for bin packing 装箱 — fitting items into the fewest containers.
Sorting algorithms
- Bubble sort compares neighbours and swaps them if they are in the wrong order; one pass moves the largest item to the end. A pass on $5, 1, 4, 2, 8$ gives $1, 4, 2, 5, 8$.
- Quick sort chooses a pivot 基准, puts smaller items before it and larger items after it, then repeats on each part. It usually needs far fewer comparisons.
Give the list $7, 3, 9, 1, 5$ after one pass of bubble sort (ascending).
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Swap 7/3, keep 7/9, swap 9/1, swap 9/5: the largest moves to the end.
Bin packing
- A lower bound for the number of bins is $\dfrac{\text{total size}}{\text{bin capacity}}$, rounded up.
- First fit puts each item in the first bin with room. First fit decreasing sorts the items from largest to smallest first, and usually does better.
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.
Items total 47 kg and each bin holds 10 kg. Find the lower bound for the number of bins.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
$\tfrac{47}{10} = 4.7$, rounded up to 5.
Worked example: packing boxes
Boxes of heights 4, 8, 3, 7, 5, 6, 2 m are stacked in containers of height 10 m. Find a lower bound, then pack with first fit and with first fit decreasing.
- Lower bound: total $= 35$, so at least $\lceil 3.5 \rceil = 4$ containers.
- First fit: $[4, 3, 2]$, $[8]$, $[7]$, $[5]$, $[6]$ — 5 containers.
- First fit decreasing: sort to $8, 7, 6, 5, 4, 3, 2$: $[8, 2]$, $[7, 3]$, $[6, 4]$, $[5]$ — 4 containers, equal to the lower bound, so it is optimal 最优的.
Pack $6, 5, 4, 4, 3, 3, 2, 2, 1$ into bins of size 12 using first fit decreasing. How many bins are used?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
$[6, 5, 1]$, $[4, 4, 3]$, $[3, 2, 2]$ — 3 bins, equal to $\lceil 30/12 \rceil$.
Route inspection
- A route along every edge that returns to the start exists without repeats only if every vertex has even degree 度.
- If two vertices are odd, repeat the shortest path between them. With four odd vertices, try all three pairings and choose the shortest total.
A network in which every vertex has even degree has a closed route that uses every edge exactly once.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Even degree everywhere means you can always leave a vertex you enter.
Route inspection in practice
- Network $AB = 5$, $BC = 4$, $CD = 6$, $DA = 3$, $AC = 7$: $A$ and $C$ have degree 3. The shortest $A$–$C$ path is $AC = 7$ (not $ABC = 9$ or $ADC = 9$).
- So the shortest closed route is $25 + 7 = 32$, with $AC$ walked twice.
A network has four odd vertices $P, Q, R, S$. Shortest paths: $PQ = 5$, $RS = 6$, $PR = 4$, $QS = 8$, $PS = 7$, $QR = 3$. Which pairing should be repeated?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Compare all three pairings: 11, 12 and 10. All four odd vertices must be paired.
Assuming the algorithm's answer is the best one. First fit and first fit decreasing are heuristic 启发式的: they give a good answer quickly, but not always the best. You can only call a packing optimal when it equals the lower bound or you show that no fewer bins can work.
First fit decreasing always gives the smallest possible number of bins.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
It is a heuristic: good, but not guaranteed optimal.
Bubble sort swaps neighbours pass by pass; quick sort splits around a pivot. For bin packing, find the lower bound, then use first fit or first fit decreasing; a packing that meets the bound is optimal. For route inspection, pair the odd vertices and repeat the shortest paths between them.
Use quick sort, taking the middle item as pivot, to sort $8, 3, 6, 1, 9, 4, 7$ into ascending order. Show each pass.
Pivot, split, repeat.