Sorting, packing and network algorithms
引入| English | 释义 | 拼音 |
|---|---|---|
| route inspection | 路线检查 | lù xiàn jiǎn chá |
| algorithm/ˈælɡərɪθəm/ | 算法 | suàn fǎ |
| sorting/ˈsɔːtɪŋ/ | 排序 | pái xù |
| bin packing/bɪn ˈpækɪŋ/ | 装箱 | zhuāng xiāng |
| pivot/ˈpɪvət/ | 基准 | jī zhǔn |
| optimal/ˈɒptɪml/ | 最优的 | zuì yōu de |
| degree/dɪˈɡriː/ | 度 | dù |
| heuristic/hjuːˈrɪstɪk/ | 启发式的 | qǐ fā shì de |
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).
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$\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?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$[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.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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.