📚 Edexcel AS and A level Further Mathematics Decision Mathematics 1 Textbook + e-book Knowledge Points | Edexcel AS与A Level进阶数学决策数学1教材+电子书知识点精讲
Decision Mathematics 1 (D1) is a core component of the Edexcel AS and A level Further Mathematics specification, introducing students to algorithms and mathematical modelling for real‑world optimisation problems. This article provides a systematic breakdown of every major topic in the official textbook, covering algorithms, graph theory, network optimisation, critical path analysis, linear programming and matchings. Each section is presented as clear revision notes, with English explanation followed immediately by its Chinese equivalent to support bilingual learners.
决策数学1（D1）是Edexcel AS与A Level进阶数学的核心组成部分，向学生介绍用于现实世界优化问题的算法和数学建模。本文系统梳理了官方教材中的每个主要知识点，涵盖算法、图论、网络优化、关键路径分析、线性规划及匹配。每节以清晰的双语复习笔记呈现，英文讲解后紧接相对应的中文解释，以便双语学习者使用。
1. Introduction to Algorithms | 算法入门
An algorithm is a finite sequence of step‑by‑step instructions designed to solve a problem. In D1, algorithms are described using flowcharts or written instructions, and their efficiency is measured by the number of operations or the order of complexity.
算法是一组为解决问题而设计的有限步骤指令。在D1中，算法通过流程图或文字说明来描述，其效率通过操作次数或复杂度阶数来衡量。
Algorithms must be precise, unambiguous and must terminate after a finite number of steps. The key measures are the number of comparisons and swaps, and the order of an algorithm gives an upper bound on how the running time grows with the size of the input.
算法必须精确、无歧义，并在有限步后终止。关键度量是比较和交换的次数，算法的阶数给出了运行时间随输入规模增长的上界。
Common orders encountered in D1 include constant O(1), linear O(n), quadratic O(n²) and cubic O(n³). Bubble sort, for example, is O(n²).
D1中常见的阶包括常数O(1)、线性O(n)、二次O(n²)和三次O(n³)。例如冒泡排序是O(n²)。
| Order 阶 | Typical example 典型例子 |
|---|---|
| O(1) | Checking the first item of a list |
| O(n) | Linear search |
| O(n²) | Bubble sort, insertion sort |
| O(n³) | Floyd’s algorithm (n = number of nodes) |
2. Sorting Algorithms | 排序算法
The textbook covers three sorting algorithms: bubble sort, shuttle sort (also known as insertion sort) and quick sort. Each algorithm arranges a list of numbers into ascending or descending order.
教材涵盖三种排序算法：冒泡排序、穿梭排序（又称插入排序）和快速排序。每个算法将数列按升序或降序排列。
In bubble sort, adjacent elements are compared and swapped if they are in the wrong order. After each pass, the largest unsorted element ‘bubbles’ to its correct position. The number of comparisons is ½n(n−1) and the maximum number of swaps is the same.
冒泡排序中，比较相邻元素，若顺序错误则交换。每趟扫描后，最大未排序元素会“冒泡”到正确位置。比较次数为½n(n−1)，最大交换次数相同。
Shuttle sort builds a sorted sublist by taking the next element and inserting it into the correct place among the already sorted items. It is more efficient than bubble sort for partially sorted lists.
穿梭排序通过取出下一个元素并将其插入已排序子列表的正确位置来构建有序序列。对于部分有序的列表，它比冒泡排序更高效。
Quick sort uses a pivot value; all smaller items are placed before the pivot and larger items after, then the process is repeated recursively on the sublists. The number of comparisons depends on the choice of pivot.
快速排序使用一个基准值；所有小于基准的项放在其前，大于的放在其后，然后对子列表递归重复该过程。比较次数取决于基准的选择。
3. Bin Packing Algorithms | 装箱算法
Bin packing deals with allocating items of given sizes into fixed‑capacity bins, aiming to minimise the number of bins used. Three heuristic algorithms are studied: first‑fit, first‑fit decreasing and full‑bin packing.
装箱问题处理将给定大小的物品分配到固定容量的箱子中，目标是最小化使用的箱子数。研究三种启发式算法：首次适应、首次适应递减和满箱装箱。
First‑fit takes items in the order given and places each item into the first bin that has enough remaining capacity. It is simple but may leave many bins partly filled.
首次适应按给定顺序取物品，将每件物品放入第一个有足够剩余容量的箱子。它简单但可能留下许多部分填充的箱子。
First‑fit decreasing sorts items into descending order of size before applying first‑fit. This typically uses fewer bins because larger items are packed first.
首次适应递减在应用首次适应前将物品按尺寸降序排序。这通常使用更少的箱子，因为大件先被装入。
Full‑bin packing looks for combinations of items that exactly fill a bin, removing them, then applies first‑fit to the rest. It sometimes gives an optimal solution but is not guaranteed.
满箱装箱寻找能恰好装满一个箱子的物品组合，将其移除，然后对剩余物品应用首次适应。它有时能给出最优解，但不保证。
The lower bound for the number of bins is given by the ceiling of the sum of item sizes divided by bin capacity. No heuristic can ever use fewer bins than this bound.
箱子数量的下界由物品尺寸总和除以箱容量并向上取整得到。任何启发式算法都不可能使用少于这个下界的箱子数。
4. Graphs and Networks | 图与网络基础
A graph consists of vertices (nodes) connected by edges (arcs). In D1, graphs are used to model relationships, road networks, communication links and project activities.
图由顶点（节点）通过边（弧）连接组成。在D1中，图用于建模关系、道路网络、通信链接和项目活动。
A graph is simple if it has no loops and no multiple edges between the same pair of vertices. A path is a sequence of edges connecting vertices without repeating vertices; a cycle is a closed path.
如果一个图没有环且同一对顶点之间没有重边，则称为简单图。路径是连接顶点的边序列且不重复顶点；回路是闭合路径。
A tree is a connected graph with no cycles. A spanning tree of a graph is a subgraph that contains all vertices but is a tree. A minimum spanning tree (MST) minimises the total weight of edges.
树是一个无回路的连通图。图的生成树是包含所有顶点的树子图。最小生成树（MST）使边的总权重最小。
A digraph (directed graph) has directed edges, represented by arrows. A network is a graph where each edge carries a numerical weight such as distance, time or cost.
有向图具有带方向的边，用箭头表示。网络是每条边带有数值权重（如距离、时间或成本）的图。
5. Minimum Spanning Trees (Kruskal and Prim) | 最小生成树（Kruskal和Prim算法）
Two algorithms are used to find a minimum spanning tree: Kruskal’s algorithm and Prim’s algorithm. Both work on a connected, weighted graph.
寻找最小生成树有两种算法：Kruskal算法和Prim算法。两者都适用于连通加权图。
Kruskal’s algorithm sorts all edges by weight in increasing order, then adds edges one by one provided they do not form a cycle, until all vertices are connected. It is efficient when implemented with a union‑find data structure but in D1 it is applied by inspection.
Kruskal算法将所有边按权重递增排序，然后逐一添加边，只要不形成回路，直到所有顶点连通。使用并查集数据结构时效率很高，但在D1中通过观察应用。
Prim’s algorithm starts from any vertex and repeatedly adds the shortest edge that connects a vertex in the tree to a vertex not yet in the tree. This grows the tree step by step.
Prim算法从任意顶点开始，重复添加连接树内顶点与树外顶点的最短边，逐步扩展生成树。
Both algorithms always produce a minimum spanning tree; the total weight is unique if all edge weights are distinct. They may give the same set of edges or different ones with the same total weight.
两种算法总能产生最小生成树；若所有边权互异，总权重唯一。它们可能给出相同的边集，也可能给出总权重相同的不同边集。
Kruskal: sort edges (weight ascending) → add edge if no cycle
Kruskal：将边按权重升序排序 → 若不形成回路则添加
6. Dijkstra’s Shortest Path Algorithm | Dijkstra最短路径算法
Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a network with non‑negative edge weights. It uses a labelling procedure, updating temporary labels with a permanent label for the closest temporary node.
Dijkstra算法在边权非负的网络中寻找从源节点到所有其他节点的最短路径。它使用标号过程，为最近临时节点标上永久标签并更新临时标签。
Steps: (1) Assign the source a permanent label 0 and all others a temporary label ∞. (2) For the most recent permanent node, consider its neighbours; if a shorter distance is found, update their temporary labels. (3) Choose the node with the smallest temporary label, make it permanent, and repeat until the destination is permanently labelled.
步骤：(1) 为源节点标永久标签0，所有其他节点标临时标签∞。(2) 对最新的永久节点，考察其邻点；若找到更短距离，则更新其临时标签。(3) 选择临时标签最小的节点，设为永久，重复直至目标节点被永久标号。
The order of permanently labelling nodes gives the shortest distance to each. The route can be traced back using the working values recorded on the diagram. Dijkstra’s algorithm fails if any edge weight is negative.
永久标号的顺序给出了到每个节点的最短距离。路径可通过记录在工作图上的值逆向追踪。若存在负权边，Dijkstra算法失效。
7. Floyd’s Algorithm | Floyd算法
Floyd’s algorithm finds the shortest distances between every pair of nodes in a network. It is an O(n³) algorithm that systematically updates a distance matrix and a route matrix.
Floyd算法找出网络中每一对节点之间的最短距离。它是一种O(n³)算法，系统性地更新距离矩阵和路径矩阵。
Start with an initial distance matrix D₀ where D₀[i][j] is the direct weight from i to j (∞ if not directly connected). For each intermediate node k, update Dₖ[i][j] = min(Dₖ₋₁[i][j], Dₖ₋₁[i][k] + Dₖ₋₁[k][j]).
从初始距离矩阵D₀开始，其中D₀[i][j]为从i到j的直接权重（若不直接相连则为∞）。对于每个中间节点k，更新Dₖ[i][j] = min(Dₖ₋₁[i][j], Dₖ₋₁[i][k] + Dₖ₋₁[k][j])。
The route matrix R is updated alongside D to record the immediate predecessor or the next node. After n iterations, the final matrices give all shortest paths and their lengths.
路径矩阵R随D一起更新，记录直接前驱或下一个节点。经过n次迭代后，最终矩阵给出所有最短路径及其长度。
Floyd’s algorithm works even with negative weights, provided there are no negative cycles. It is invaluable for solving complete communication or transport system analyses.
Floyd算法即使在负权下也有效，前提是没有负回路。它对于求解完整的通信或运输系统分析十分有用。
8. Route Inspection (Chinese Postman) | 路线检查（中国邮递员问题）
The route inspection problem seeks the shortest closed walk that traverses every edge of a graph at least once. When the graph is Eulerian (all vertex degrees even), an Eulerian circuit is exactly a solution with no repeated edges.
路线检查问题寻求至少遍历图中每条边一次的最短闭合行走。当图为欧拉图（所有顶点度数为偶数）时，欧拉回路恰好是不重复边的解。
If a graph is not Eulerian, some edges must be traversed twice. The problem reduces to finding a set of additional journeys (repeated edges) between odd‑degree vertices that minimises total extra length. These extra paths are found by considering pairings of odd vertices using the shortest distances.
若图不是欧拉图，则某些边必须行走两次。问题归结为寻找一组奇数度顶点间的附加路径（重复边），使额外总长度最小。这些额外路径通过考虑奇数度顶点的配对并使用最短距离来找到。
Algorithm: identify all odd nodes, find the shortest paths between them using Dijkstra or a given table, then find a minimum weight perfect matching of the odd nodes to determine which edges to repeat. After adding the repeated edges, an Eulerian trail can be formed starting and finishing at the same vertex.
算法：找出所有奇节点，用Dijkstra或给定表格找出它们之间的最短路径，然后找到奇节点的最小权完美匹配以确定需重复的边。添加重复边后，可从同一起点出发并返回的欧拉路径即可构造。
9. Critical Path Analysis | 关键路径分析
Critical path analysis (CPA) is used to schedule a project consisting of activities with durations and precedence constraints. It identifies the minimum project duration and activities that cannot be delayed without affecting the total time.
关键路径分析（CPA）用于调度由具有持续时间和前后约束的活动组成的项目。它确定最小项目工期以及那些若延迟就会影响总时间的活动。
An activity‑on‑node (precedence) network is drawn where nodes represent activities and directed edges show dependencies. Dummy activities (duration 0) are used to express complex dependencies or to maintain unique start/finish nodes.
绘制节点活动（前导）网络，其中节点表示活动，有向边表示依赖关系。虚活动（持续时间为0）用于表达复杂依赖或保持唯一的开始/结束节点。
Forward pass calculates the earliest start time (EST) and earliest finish time (EFT) for each activity. Backward pass gives the latest start time (LST) and latest finish time (LFT) based on the project completion time from the forward pass.
前推法计算每个活动的最早开始时间（EST）和最早完成时间（EFT）。后推法根据前推法得出的项目完成时间给出最迟开始时间（LST）和最迟完成时间（LFT）。
Total float = LST − EST = LFT − EFT. Activities with total float = 0 are critical; they form one or more critical paths. Critical path(s) determine the overall project duration.
总时差 = LST − EST = LFT − EFT。总时差为0的活动是关键活动；它们构成一条或多条关键路径。关键路径决定项目总持续时间。
Gantt (cascade) charts are used to present the schedule visually, showing how activities can be shifted within their float to smooth resource usage.
甘特图（级联图）用于直观呈现进度安排，显示活动如何在时差内移动以平顺资源使用。
10. Linear Programming: Formulating Problems | 线性规划：问题建模
Linear programming (LP) is used to optimise (maximise or minimise) a linear objective function subject to a set of linear inequalities (constraints). Decision variables represent quantities to be determined.
线性规划（LP）用于在一组线性不等式（约束）下优化（最大化或最小化）线性目标函数。决策变量代表待定的数量。
Typical steps: define the decision variables clearly, write the objective function as a linear expression, and formulate each constraint as a linear inequality (or equality). Non‑negativity constraints x ≥ 0, y ≥ 0 are usually included.
典型步骤：明确定义决策变量，将目标函数写为线性表达式，并将每个约束表示为线性不等式（或等式）。通常包含非负约束x ≥ 0, y ≥ 0。
When variables can only take integer values, the problem becomes an integer programming problem, but in D1 the graphical method often assumes continuous variables; the integer solution is then found by checking integer points near the optimum.
当变量只能取整数值时，问题变为整数规划问题，但在D1中图解法通常假设连续变量；然后通过检查最优解附近的整点来寻找整数解。
11. Graphical Solution of Linear Programming | 线性规划图解法
For two decision variables, the feasible region is drawn on a graph as the intersection of the half‑planes defined by the constraints. The optimal solution must lie at a vertex (corner) of the feasible region, provided one exists.
对于两个决策变量，可行域作为由约束定义的半平面的交集画在图上。最优解必须位于可行域的顶点（角点）上，如果存在的话。
Draw each constraint as a line (solid if ≤ or ≥, dashed if < or >), shade out the unwanted region, and identify the feasible region. Plot an objective line equal to a constant, then slide it parallel to itself in the direction of improvement until the last point of contact with the feasible region.
将每个约束画为直线（≤或≥用实线，<或>用虚线），排涂不需要的区域，确定可行域。画一条等于常数的目标线，然后沿改进方向平行移动，直至与可行域最后一个接触点。
The coordinates of the optimal vertex are found either by reading from the graph or by solving the simultaneous equations of the intersecting constraints. If the objective line is parallel to a boundary, there may be multiple optimal solutions along that edge.
最优顶点的坐标可从图上读取，或通过解相交约束的联立方程组求得。若目标线与某边界平行，则该边界上可能存在多个最优解。
To find integer solutions, test integer coordinate points near the optimal vertex, ensuring they stay within the feasible region and minimise or maximise the objective.
要寻找整数解，需在最优顶点附近测试整数坐标点，确保它们在可行域内，并能最小化或最大化目标值。
12. Matchings | 匹配问题
A matching in a bipartite graph pairs elements of one set with elements of another set so that no vertex is used more than once. A maximal matching is one to which no further edge can be added; a maximum matching contains the greatest possible number of edges.
二分图中的匹配将一集合的元素与另一集合的元素配对，使得每个顶点最多使用一次。极大匹配是指无法再添加边的匹配；最大匹配包含尽可能多的边。
The alternating path algorithm (Hungarian algorithm light version) is used to improve an initial matching to a maximum matching. An alternating path starts at an unmatched vertex, alternates between unmatched and matched edges, and ends at another unmatched vertex. Swapping the status of edges along this path increases the matching size by one.
交错路径算法（简化的匈牙利算法）用于将初始匹配改进为最大匹配。交错路径从未匹配顶点开始，在未匹配边和已匹配边之间交替，并结束于另一个未匹配顶点。交换该路径上边的状态可使匹配大小增加1。
If no such alternating path can be found, the matching is maximum. The algorithm requires systematically constructing an alternating tree from an unmatched vertex to find augmenting paths.
若找不到这样的交错路径，则匹配已是最大匹配。该算法需要从未匹配顶点系统地构建交错树以寻找增广路径。
Applications include allocating tasks to workers, students to projects, or pairing computational elements, always subject to compatibility constraints.
应用包括将任务分配给工人、学生分配给项目，或在兼容性约束下配对计算元素。
Published by TutorHao | Decision Mathematics 1 Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply