决策数学D1：算法、图论与关键路径 | Decision Maths D1: Algorithms, Graph Theory and Critical Paths

决策数学D1：算法、图论与关键路径

决策数学（Decision Mathematics 1，简称 D1）是 A-Level 进阶数学（Further Mathematics）中最特别的一门单元：它不考微积分，而是考"如何用算法高效地解决问题"。这些算法广泛应用在计算机科学、物流调度与工程管理之中，是理解"机器如何做决策"的入门课。本文带你系统梳理 D1 的核心算法：排序、装箱、图论、最短路径、关键路径分析与线性规划，并给出每类算法的标准解题格式，助你在考试中稳拿过程分。

Decision Mathematics 1 (D1) is the most distinctive module in A-Level Further Mathematics: instead of calculus, it tests how to solve problems efficiently using algorithms. These algorithms are widely used in computer science, logistics and project management, making D1 an introduction to how machines make decisions. This guide walks through the core D1 algorithms, from sorting and bin packing to graph theory, shortest paths, critical path analysis and linear programming, and gives the standard layout for each one so you can secure the method marks in the exam.

一、什么是决策数学？| What is Decision Mathematics?

决策数学（Decision Mathematics）研究的是"离散"的问题：如何用最少的步骤完成排序、如何在网络中找到最短路径、如何安排工程工序使总工期最短。与纯数学（Pure Mathematics）研究连续的函数与微积分不同，决策数学的每一个问题都可以用清晰的算法（Algorithm）一步步求解，因此它也被称为"离散数学"（Discrete Mathematics）。它的应用场景非常具体：快递路线规划、工厂排产、网络布线都用到了 D1 里的算法。学习 D1 的重点不是心算，而是理解算法背后的逻辑并正确执行它。

Decision Mathematics studies discrete problems: how to sort a list in the fewest steps, how to find the shortest path through a network, and how to schedule activities so a project finishes in the shortest time. Unlike Pure Mathematics, which studies continuous functions and calculus, every problem here can be solved by a clear, step-by-step algorithm, which is why the subject is also called Discrete Mathematics. Its applications are concrete: delivery route planning, factory scheduling and network cabling all use the algorithms in D1. The focus of D1 is not mental arithmetic but understanding and correctly executing the logic behind each algorithm.

二、算法的概念与冒泡排序 | Algorithms and Bubble Sort

算法（Algorithm）是一套精确的指令序列，用于完成特定任务。在 D1 中，你不仅要会执行算法，还要学会用"追踪表"（Trace Table）记录每一步的状态。冒泡排序（Bubble Sort）是最基础的排序算法：它反复比较相邻的两个元素，若顺序错误就交换位置，每一轮都能把当前最大的元素"冒"到末尾。对一个有 n 个元素的列表，冒泡排序最多需要 n-1 轮比较；最坏情况下总的比较次数为 n(n-1)/2 次。

An algorithm is a precise sequence of instructions that completes a specific task. In D1 you must not only execute algorithms but also record the state after every step using a trace table. Bubble Sort is the simplest sorting algorithm: it repeatedly compares adjacent elements and swaps them when they are in the wrong order, so the largest remaining element bubbles to the end in each pass. For a list of n items, Bubble Sort needs at most n-1 passes, and in the worst case the total number of comparisons is n(n-1)/2.

三、快速排序与二分查找 | Quick Sort and Binary Search

快速排序（Quick Sort）选择一个"枢轴"（Pivot），把小于枢轴的数放在它的左边、大于枢轴的数放在右边，再对左右两部分递归重复这一过程，直到每部分只有一个元素。快速排序的平均复杂度为 O(n log n)，明显快于冒泡排序。二分查找（Binary Search）只适用于已排序的列表：每次取中间元素与目标值比较，若目标更小就只搜索左半部分，反之搜索右半部分。每比较一次都能排除一半的元素，效率远高于逐个查找。

Quick Sort selects a pivot, places every number smaller than the pivot on its left and every larger number on its right, then repeats the process recursively on each half until every part has a single element. Its average complexity is O(n log n), noticeably faster than Bubble Sort. Binary Search works only on sorted lists: it compares the target with the middle element each time, discarding half the list after every comparison. Each comparison eliminates half the remaining items, making it far more efficient than searching one item at a time.

四、装箱问题与 First-Fit 算法 | Bin Packing and the First-Fit Algorithm

装箱问题（Bin Packing）问的是：给定一批不同大小的物品和容量固定的箱子，最少需要多少个箱子才能全部装下？First-Fit（首次适应）算法按物品到达的顺序处理，把每件物品放进第一个装得下的箱子，若都放不下就开一个新箱子。First-Fit Decreasing（FFD）则先把物品按大小降序排列，再套用 First-Fit。经验表明，先放大件再放小件的 FFD 通常比单纯 First-Fit 用到的箱子更少，更接近最优解。

The Bin Packing problem asks how many boxes of fixed capacity are needed to hold a set of items of different sizes. The First-Fit algorithm processes items in arrival order, placing each item into the first box with enough space and opening a new box only when none fits. First-Fit Decreasing (FFD) first sorts the items into descending order of size and then applies First-Fit. In practice, packing the large items first means FFD usually uses fewer boxes than plain First-Fit and stays closer to optimal.

五、图论基础：节点、边与度 | Graph Theory Basics: Vertices, Edges and Degree

图（Graph）由节点（Vertex）和连接节点的边（Edge）组成，是 D1 许多问题的建模工具。一个节点的"度"（Degree）是与它相连的边的条数；所有节点的度数之和等于边数的两倍，这就是"握手定理"（Handshake Lemma）。如果存在一条经过每条边恰好一次的路线，图称为"欧拉图"（Eulerian）；若存在一条经过每个节点恰好一次的路线，则称为"哈密顿图"（Hamiltonian）。特别地，一棵树（Tree）是连通的且没有回路，有 n 个节点的树恰好有 n-1 条边。

A graph consists of vertices and the edges connecting them, and it is the modelling tool behind many D1 problems. The degree of a vertex is the number of edges meeting it, and the sum of all degrees equals twice the number of edges, which is the Handshake Lemma. A graph is Eulerian if there is a route using every edge exactly once, and Hamiltonian if there is a route visiting every vertex exactly once. In particular, a tree is a connected graph with no cycles, and a tree with n vertices has exactly n-1 edges.

六、最小生成树：Kruskal 与 Prim 算法 | Minimum Spanning Trees: Kruskal's and Prim's Algorithms

最小生成树（Minimum Spanning Tree，MST）是连接图中所有节点、且总权重最小的树，现实中的"用最短电缆连接所有基站"就是这类问题。Kruskal 算法把边按权重从小到大排序，依次加入不构成回路的边，直到所有节点都被连接。Prim 算法则从任意一个节点出发，每次添加连接"已选集合"与"未选集合"的最小权重边。两种算法最终得到相同的总权重，但执行的步骤不同。

A minimum spanning tree (MST) connects every vertex of a graph with the smallest possible total weight, and a real example is joining all base stations with the shortest cable. Kruskal's algorithm sorts the edges by weight and adds each edge in turn, provided it does not create a cycle, until all vertices are joined. Prim's algorithm starts from any vertex and repeatedly adds the lowest-weight edge linking the chosen set to the unchosen set. Both give the same total weight but follow different processes.

七、Dijkstra 最短路径算法 | Dijkstra's Shortest Path Algorithm

Dijkstra 算法求的是从起点到其他所有节点的最短路径。它为每个节点维护一个"临时标签"（Working Value），从起点开始，每次选择当前临时标签最小的节点使其"永久化"（Permanent），再用它更新相邻节点的临时标签。重复这一过程，直到终点被永久化，然后从终点逆向回溯，读出最短路径及其长度。注意：Dijkstra 算法要求所有边的权重都为非负。

Dijkstra's algorithm finds the shortest path from a start vertex to every other vertex. It maintains a working value for each vertex and repeatedly makes permanent the vertex with the smallest working value, then uses it to update the working values of its neighbours. When the destination becomes permanent, you trace backwards from it to read off the shortest path and its length. Note that Dijkstra's algorithm requires all edge weights to be non-negative.

八、路线检查与中国邮递员问题 | Route Inspection and the Chinese Postman Problem

路线检查问题（Route Inspection Problem），又称"中国邮递员问题"（Chinese Postman Problem），问的是：邮递员要走遍每条街道、每条边至少一次，怎样走总路程最短？如果图是欧拉图，一次遍历每条边即可。若图不是欧拉图（存在奇度节点），就需要在某些边上"重复走"，把奇度节点两两配对，使重复边的总权重最小。找出奇度节点并用 Dijkstra 求它们之间的最短路径来配对，是解题的关键。

The Route Inspection Problem, also called the Chinese Postman Problem, asks how a postman can cover every street at least once with the shortest total distance. If the graph is Eulerian, a single route using every edge exactly once works. If not, some edges must be traversed twice; you pair up the odd-degree vertices and choose the repeated edges with the smallest total weight. The key is to find the odd vertices and use Dijkstra's algorithm to find the shortest routes pairing them up.

九、关键路径分析：活动网络与浮动时间 | Critical Path Analysis: Activity Networks and Float

关键路径分析（Critical Path Analysis，CPA）用于规划工程中相互依赖的活动。每项活动（Activity）用一条弧表示，节点代表事件（Event）。通过"正向扫描"（Forward Pass）计算每个事件的最早发生时间（Earliest Event Time），再通过"逆向扫描"（Backward Pass）计算最晚发生时间（Latest Event Time）。浮动时间（Float）为零的活动构成"关键路径"（Critical Path），它决定了整个工程的最短工期，任何延误都会直接拖长工期。当两项活动没有先后关系、却要表示依赖时，需要引入"虚活动"（Dummy Activity）。

Critical Path Analysis (CPA) is used to plan activities that depend on one another. Each activity is shown as an arc and each node represents an event. A forward pass computes the earliest event time of each event, and a backward pass computes the latest event time. The activities with zero float form the critical path, which determines the shortest duration of the whole project, and any delay on it delays the project itself. A dummy activity is introduced when a dependency must be shown between activities that otherwise have no ordering.

十、线性规划的图解法 | Linear Programming: The Graphical Method

线性规划（Linear Programming）在若干不等式约束下，求目标函数的极大值或极小值。图解法先画出每条约束对应的直线，确定"可行区域"（Feasible Region），再画出目标函数的等值线并平移，直到它到达可行区域的边界。最优解总是出现在可行区域的某个顶点上。D1 只要求处理两个变量的图解法，若题目要求整数解，还需检查顶点附近的整数格点。

Linear programming maximises or minimises an objective function subject to a set of inequality constraints. The graphical method draws the line for each constraint, identifies the feasible region, then slides a line of the objective function until it reaches the boundary of the region. The optimal solution always occurs at a vertex of the feasible region. D1 only requires the graphical method for two variables, and if an integer solution is required you must also check the integer points near each vertex.

十一、配对问题与最大匹配 | Matchings and Maximum Matching

配对问题（Matching）研究如何把两组对象（如工人与任务）一一配对，其中每个工人只能胜任部分任务。在二分图（Bipartite Graph）中，一条"匹配"是一组互不共享节点的边。通过沿"交替路径"（Alternating Path）不断改进，可以找到"最大匹配"（Maximum Matching），也就是能让最多工人同时被分配到任务的方案。当一边的每个对象都能被配上时，称为"完全匹配"（Complete Matching）。

Matching problems ask how to pair two sets of objects, such as workers and tasks, where each worker can do only some of the tasks. In a bipartite graph, a matching is a set of edges that share no vertices. By repeatedly improving along alternating paths, we can find a maximum matching, the arrangement that lets the largest possible number of workers be assigned at once. When every object on one side can be matched, the result is a complete matching.

十二、D1 考试提分要点 | D1 Exam Tips for Higher Marks

D1 考试最看重"过程"而非只看答案。做追踪表（Trace Table）时每一步都要完整、清晰，因为阅卷人按步骤给分；排序、最短路径和关键路径题务必画图，图上的标注（权重、标签、最早与最晚时间）本身就是得分点。常见失分点包括：忘记写初始状态、遗漏最后的回溯步骤、以及把"浮动时间"算错。建议把每类算法的标准格式背熟，考前用真题反复练手，并严格控制每道题的时间，先拿下过程分。

D1 exams reward process far more than the final answer. Trace tables must show every step clearly, since marks are awarded per step; always draw diagrams for sorting, path and critical path questions, because the labels and annotations themselves carry marks. Common mistakes include omitting the initial state, skipping the final trace-back, and miscalculating float. Learn the standard layout for each algorithm by heart, practise repeatedly with past papers before the exam, and time each question carefully so you secure the method marks first.

需要专业A-Level辅导？
16621398022
同微信 | 免费咨询课程规划
访问 aleveler.com 了解更多

更多咨询请联系16621398022（同微信）