Algorithms, networks and linear programming
引入| English | 释义 | 拼音 |
|---|---|---|
| Dijkstra's algorithm/ˈdeɪkstrəz ˈælɡərɪθəm/ | 迪杰斯特拉算法 | dí jié sī tè lā suàn fǎ |
| algorithms/ˈælɡərɪθəmz/ | 算法 | suàn fǎ |
| networks/ˈnetwɜːks/ | 网络 | wǎng luò |
| edges/ˈedʒɪz/ | 边 | biān |
| spanning tree | 生成树 | shēng chéng shù |
| vertices/ˈvɜːtɪsiːz/ | 顶点 | dǐng diǎn |
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | 最小生成树 | zuì xiǎo shēng chéng shù |
| objective function/ɒbˈdʒektɪv ˈfʌŋkʃn/ | 目标函数 | mù biāo hán shù |
| constraints/kənˈstreɪnts/ | 约束条件 | yuē shù tiáo jiàn |
| feasible region | 可行域 | kě xíng yù |
Twenty minutes in an Amsterdam café, 1956
- One morning in 1956, the Dutch computer scientist Edsger Dijkstra was shopping in Amsterdam with his fiancée. Sitting at a café terrace, he designed in about twenty minutes a method for finding the shortest route between two cities — without pen and paper. Satellite navigation still uses Dijkstra's algorithm 迪杰斯特拉算法.
- D1 studies algorithms 算法 on networks 网络 (graphs with weights on the edges), and linear programming for choosing the best plan.
Networks and spanning trees
- A network has vertices 顶点 joined by weighted edges 边. A spanning tree 生成树 joins every vertex with no cycles; for $n$ vertices it has $n - 1$ edges.
- A minimum spanning tree 最小生成树 (MST) has the smallest total weight — the cheapest way to connect every town to a cable network.
How many edges does a spanning tree on 9 vertices have?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
A tree on $n$ vertices has $n - 1$ edges.
Kruskal's and Prim's algorithms
- Kruskal: list the edges in order of weight and add the shortest one each time, unless it makes a cycle.
- Prim: start at any vertex and repeatedly add the shortest edge joining a new vertex to the tree. Prim also works from a distance matrix.
Algorithms, networks and linear programming
Kruskal selects edges in increasing weight while avoiding cycles
Compare the model with the worked case and explain one change.
Kruskal's algorithm has chosen $PQ$, $QR$ and $ST$. The next shortest edge is $PR$. What happens to it?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
$P$ and $R$ are already joined through $Q$.
Worked example: Kruskal and Dijkstra
A network has edges $AB = 4$, $AC = 2$, $BC = 1$, $BD = 5$, $CD = 8$, $CE = 10$, $DE = 2$. Find an MST, and the shortest route from $A$ to $E$.
- Kruskal: $BC\ (1)$ ✓, $AC\ (2)$ ✓, $DE\ (2)$ ✓, $AB\ (4)$ ✗ (cycle $ABC$), $BD\ (5)$ ✓ — four edges for five vertices, total weight 10.
- Dijkstra from $A$: label $A = 0$, then $C = 2$, $B = \min(4, 2 + 1) = 3$, $D = \min(3 + 5, 2 + 8) = 8$, $E = \min(2 + 10, 8 + 2) = 10$.
- Route: trace back from $E$: $E \leftarrow D \leftarrow B \leftarrow C \leftarrow A$, so $A$–$C$–$B$–$D$–$E$, length 10.
Edges: $AB = 3$, $AC = 5$, $BC = 4$, $BD = 6$, $CD = 2$. Find the weight of the minimum spanning tree.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$CD\ 2$, $AB\ 3$, $BC\ 4$ — then every vertex is joined: $2 + 3 + 4 = 9$.
How Dijkstra's algorithm works
- Give the start a permanent label 0. Update the working values of its neighbours, then make the smallest working value permanent, and repeat from that vertex.
- When the destination is permanent, trace back through edges whose weight equals the difference of the labels.
In the same network, find the shortest distance from $A$ 到 $D$.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$A$–$C$–$D$ is(是) $5 + 2 = 7$; $A$–$B$–$D$ is 9 and $A$–$B$–$C$–$D$ is 9.
Linear programming
- Write variables, an objective function 目标函数 to maximise or minimise, and constraints 约束条件. For example: maximise $P = 2x + 3y$ subject to $x + y \le 4$, $x + 3y \le 6$, $x, y \ge 0$.
- The best point is at a vertex of the feasible region 可行域. Testing $(0, 0)$, $(4, 0)$, $(3, 1)$ and $(0, 2)$ gives $P = 0, 8, 9, 6$, so the maximum is 9 at $(3, 1)$.
Maximise $P = x + 2y$ subject to $x + y \le 5$, $y \le 3$, $x, y \ge 0$. Find the maximum value of $P$.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Vertices $(0, 0), (5, 0), (2, 3), (0, 3)$ give $0, 5, 8, 6$.
In a linear programming problem, the optimal value can be at a point inside the feasible region but not on its edge.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
A linear objective is best at a vertex (or along an edge) of the region.
Adding the shortest edges without checking for cycles. In the worked example, the next shortest edge after $BC$, $AC$ and $DE$ is $AB = 4$, but $A$ and $B$ are already joined through $C$. Adding it makes a cycle, so it is rejected — a tree never has cycles.
A minimum spanning tree joins all vertices with least total weight: Kruskal adds the shortest edge that makes no cycle, and Prim grows a tree from one vertex. Dijkstra finds shortest routes by making the smallest working label permanent each time, then tracing back. In linear programming, the optimum lies at a vertex of the feasible region.
Use Prim's algorithm, starting at $A$, on the network $AB = 4$, $AC = 2$, $BC = 1$, $BD = 5$, $CD = 8$, $CE = 10$, $DE = 2$. List the edges in the order chosen and give the total weight.
Grow the tree one vertex at a time.