Algorithms, networks and linear programming
Introducido| English | Significado |
|---|---|
| Dijkstra's algorithm/ˈdeɪkstrəz ˈælɡərɪθəm/ | A shortest-path algorithm that makes the smallest temporary distance permanent, then updates neighbours; edge weights must be non-negative. |
| algorithms/ˈælɡərɪθəmz/ | A finite sequence of precise steps for solving a problem or carrying out a task. |
| networks/ˈnetwɜːks/ | A set of connected devices or nodes that can exchange information. |
| edges/ˈedʒɪz/ | Connections between vertices in a graph, or boundary segments of a geometric shape. |
| spanning tree | A tree that joins every vertex of a network, with no cycles. |
| vertices/ˈvɜːtɪsiːz/ | The nodes of a graph; in geometry, the corner points where edges meet. |
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | árbol generador mínimo |
| objective function/ɒbˈdʒektɪv ˈfʌŋkʃn/ | The quantity expressed as a function of decision variables that is to be maximised or minimised. |
| constraints/kənˈstreɪnts/ | A condition or limit that a valid solution must satisfy. |
| feasible region | The set of points that satisfy all the constraints of a linear programming problem. |
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?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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$ y $ST$. The next shortest edge is $PR$. What happens to it?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
$P$ y $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.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
$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$ hasta $D$.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
$A$–$C$–$D$ es $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$.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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.