📚 Decision Mathematics 1: Core Algorithms and Network Methods | 决策数学 1：核心算法与网络方法
Decision Mathematics 1 (D1) introduces the algorithmic ideas behind sorting, searching, optimisation and network analysis. It is assessed in several A Level and Further Mathematics specifications and rewards precise, logical working rather than symbolic manipulation.
决策数学 1（D1）介绍排序、查找、优化和网络分析背后的算法思想。它在多个 A Level 和进阶数学考试大纲中占有一席之地，考查的是严谨、有条理的过程，而不是符号运算。
1. Algorithmic Thinking and Order of Complexity | 算法思维与复杂度阶数
An algorithm is a finite sequence of unambiguous instructions that produces a required output for a given input. In D1, algorithms are usually traced step by step, showing the state of lists, labels or tables after each iteration.
算法是一组有限的、无歧义的指令，对给定输入产生所需输出。在 D1 中，算法通常需要逐步跟踪，展示每次迭代后列表、标签或表格的状态。
The efficiency of an algorithm is described by its order of complexity. Common orders used in D1 include O(n²) for bubble sort and O(n log n) for quick sort in the average case, where n is the number of items.
算法的效率用复杂度阶数描述。D1 中常见的阶数包括冒泡排序的 O(n²) 和快速排序平均情况下的 O(n log n)，其中 n 是项目数量。
Key idea: for decision problems, an algorithm must be finite, deterministic and clearly presented; marks are often awarded for correct intermediate passes and comparisons.
关键思想：对于决策问题，算法必须有限、确定且表达清晰；答题时中间遍数和比较次数往往是给分点。
2. Sorting Algorithms: Bubble Sort and Quick Sort | 排序算法：冒泡排序与快速排序
Bubble sort compares adjacent pairs and swaps them if they are in the wrong order. After the first pass the largest value is guaranteed to be in its final position, so later passes can ignore the sorted tail.
冒泡排序比较相邻元素，如果顺序错误就交换。第一遍结束后，最大值一定处于最终位置，因此后续遍数可以忽略已排好的尾部。
Quick sort uses a pivot, usually the middle value, and partitions the list into values smaller than, equal to, and greater than the pivot. Each sublist is then sorted recursively.
快速排序使用一个枢轴（通常是中间值），将列表划分为小于、等于和大于枢轴的三部分，然后递归地对每个子列表排序。
When tracing quick sort, write the pivot clearly and keep the relative order of equal or remaining values stable unless the question states otherwise.
在跟踪快速排序时，要清楚地写出枢轴，并保持其余相等或剩余值的相对顺序稳定，除非题目另有说明。
3. Binary Search and Bin Packing | 二分查找与装箱问题
Binary search locates a target value in an ordered list by repeatedly eliminating half of the remaining items. At each step compare the target with the middle item; if it is lower, search the left half, otherwise search the right half.
二分查找通过反复排除剩余项目的一半来在有序列表中定位目标值。每一步将目标值与中间项比较；如果目标更小，就查找左半部分，否则查找右半部分。
of n items is the smallest integer k such that 2ᵏ ≥ n. For n = 100, this is 7 comparisons.
对于包含 n 个项目的列表，最多需要的比较次数是满足 2ᵏ ≥ n 的最小整数 k。例如 n = 100 时，最多为 7 次比较。
Bin packing places items of given sizes into bins of fixed capacity using heuristics such as first-fit, first-fit decreasing and full-bin combinations. D1 questions usually ask for the number of bins produced by each heuristic and may ask for the optimal lower bound ⌈total size ÷ capacity⌉.
装箱问题将给定大小的物品装入固定容量的箱子，使用首次适应、首次适应递减和满箱组合等启发式算法。D1 题目通常要求给出每种启发式使用的箱子数，并可能要求最优下界 ⌈总大小 ÷ 容量⌉。
4. Graphs, Paths and Cycles | 图、路径与回路
A graph consists of vertices connected by edges. A path visits vertices without repeating an edge; a cycle is a closed path. A tree is a connected graph with no cycles, so a tree with n vertices has exactly n − 1 edges.
图由顶点和连接顶点的边组成。路径经过顶点且不重复边；回路是闭合路径。树是没有回路的连通图，因此有 n 个顶点的树恰好有 n − 1 条边。
Graphs can be directed or undirected, weighted or unweighted. In D1, weighted undirected graphs are common in minimum connector and route inspection problems.
图可以是有向或无向的，也可以带权或不带权。在 D1 中，带权无向图常见于最小连接问题和路线检查问题。
A complete graph Kₙ has every pair of vertices joined by an edge and contains ½n(n − 1) edges. A bipartite graph can be split into two sets so that every edge joins a vertex in one set to a vertex in the other.
完全图 Kₙ 的每对顶点之间都有边相连，共有 ½n(n − 1) 条边。二分图可以分成两个集合，使得每条边都连接一个集合中的顶点与另一个集合中的顶点。
5. Minimum Spanning Trees: Kruskal and Prim | 最小生成树：Kruskal 与 Prim
A minimum spanning tree (MST) connects all vertices in a weighted graph with the smallest possible total edge weight. Both Kruskal's and Prim's algorithms build the MST by adding safe edges without forming a cycle.
最小生成树（MST）用尽可能小的总边权连接带权图中的所有顶点。Kruskal 和 Prim 算法都通过添加不会形成回路的安全边来构造最小生成树。
Kruskal's algorithm sorts all edges by increasing weight and selects the lightest unused edge that does not create a cycle, continuing until n − 1 edges are chosen. Use a list of chosen edges and reject edges that would complete a cycle.
Kruskal 算法将所有边按权重递增排序，然后选择不产生回路的最轻未使用边，直到选出 n − 1 条边为止。答题时列出已选边，并拒绝会形成回路的边。
Prim's algorithm grows the tree from a starting vertex. At each step add the cheapest edge connecting the current tree to a vertex not yet in the tree. If a table of distances is given, show the updated candidate edges and selected vertex at each step.
Prim 算法从起始顶点开始生长树。每一步添加连接当前树与还未在树中的顶点的最便宜边。若给出距离表，需展示每一步更新的候选边和选中的顶点。
6. Dijkstra's Shortest Path Algorithm | Dijkstra 最短路算法
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It maintains temporary labels representing the shortest known distance and makes the smallest temporary label permanent.
Dijkstra 算法在边权非负的带权图中，求从源顶点到所有其他顶点的最短路径。它维护表示当前已知最短距离的临时标签，并将最小临时标签变为永久标签。
At each iteration, the smallest temporary label is made permanent. Then every unvisited neighbour is updated if the new path through the permanent vertex is shorter. Record the order of permanent labels and the working values in a table.
每次迭代，把最小临时标签变为永久标签。然后更新每个未访问邻居：如果经由刚定点的路径更短，就替换其临时标签。答题时在表格中记录永久标签顺序和工作值。
The shortest path from source to any vertex is read backwards from the final labels, and its length equals the permanent label at that vertex. Exam answers often require both the route and its total weight.
从源到任意顶点的最短路径由最终标签倒推得到，其长度等于该顶点的永久标签。考试答案通常要求写出路线及其总权重。
7. Route Inspection Problem | 路线检查问题
The Chinese postman problem asks for the shortest closed walk that traverses every edge of a graph at least once. If the graph is Eulerian (all vertices have even degree), the optimal route is an Eulerian circuit and its length equals the sum of all edge weights.
中国邮递员问题要求找出一条经过图中每条边至少一次的最短闭合行走路线。如果图是欧拉图（所有顶点度为偶数），最优路线就是一条欧拉回路，其长度等于所有边权之和。
When a graph has exactly two odd vertices, the optimal route is found by adding the shortest path between those two odd vertices as a repeated route. The total length is the sum of all edges plus that shortest path length.
当图恰好有两个奇度顶点时，最优路线通过重复这两个奇度顶点之间的最短路径来找到。总长度等于所有边权之和加上该最短路径长度。
For more than two odd vertices, pair odd vertices so that the total added repeated paths is minimised, then add these paths to the original total. State clearly which edges are repeated.
当奇度顶点超过两个时，将奇度顶点配对，使添加的重复路径总长度最小，然后将这些路径加到原始总长度上。答题时要明确说明重复了哪些边。
8. Critical Path Analysis | 关键路径分析
Critical path analysis models a project as an activity network where activities are represented by arcs and events by vertices. Each activity has a duration and dependency constraints; dummy activities may be needed to show correct precedence.
关键路径分析将项目建模为一个活动网络，其中活动用弧表示，事件用顶点表示。每个活动有工期和依赖约束；可能需要虚拟活动来表示正确的先后关系。
The forward pass gives the earliest event times. The project duration is the earliest time of the sink event. The backward pass gives the latest event times, found by subtracting activity durations from the sink backwards.
正向推演给出事件的最早时间。项目工期是终点事件的最早时间。逆向推演给出事件的最迟时间，从终点向后减去活动工期得到。
tart − duration. Critical activities cannot be delayed without delaying the whole project.
关键路径由总时差为零的活动组成，其中总时差 = 最迟完成时间 − 最早开始时间 − 工期。关键活动一旦延误，整个项目就会被推迟。
9. Linear Programming: Graphical Method | 线性规划：图解法
Linear programming maximises or minimises a linear objective function subject to linear inequalities. In D1, the feasible region is drawn on a graph and the optimal point is found by sliding an objective profit line or testing vertices.
线性规划在若干线性不等式的约束下最大化
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图