A-Level Edexcel D1 Decision Mathematics: Full Topic Guide | Edexcel D1 决策数学全面考点指南

📚 A-Level Edexcel D1 Decision Mathematics: Full Topic Guide | Edexcel D1 决策数学全面考点指南

Welcome to the ultimate revision guide for Edexcel Decision Mathematics 1 (D1). This module explores algorithmic thinking, networks, critical paths, and optimisation – essential skills for modern problem-solving. We cover every topic from the specification with clear explanations and worked examples.

欢迎阅读Edexcel 决策数学1 (D1) 终极复习指南。本模块探索算法思维、网络、关键路径和优化——这些都是现代问题解决的基本技能。我们覆盖考纲中的每一个主题，提供清晰的解释和实例。

1. What is Decision Mathematics? | 什么是决策数学？

Decision Mathematics deals with discrete problems and algorithms that find optimal solutions. It applies to logistics, scheduling, networks, and resource allocation. Unlike continuous mathematics, D1 focuses on finite structures and step-by-step procedures.

决策数学处理离散问题以及寻找最优解的算法。它应用于物流、调度、网络和资源分配。与连续数学不同，D1 侧重于有限结构和逐步执行的过程。

Typical problems include finding the shortest route, minimising cost, packing items efficiently, and scheduling tasks. Every algorithm is defined precisely, and you must be able to trace its execution on given data.

典型问题包括寻找最短路径、最小化成本、高效装箱以及安排任务。每个算法都有精确定义，你必须能在给定数据上追踪其执行过程。

---

2. Algorithms and Flow Charts | 算法与流程图

An algorithm is a finite sequence of unambiguous instructions that terminates with a result. In D1, you are expected to understand, describe, and trace algorithms using flow charts and written steps.

算法是一系列明确且有限的指令，执行后会得到结果。在 D1 中，你需要理解、描述并使用流程图和文字步骤来追踪算法。

Flow chart symbols: an oval for Start/End, a rectangle for a process, a diamond for a decision, and a parallelogram for input/output. These symbols help visualise the logic before implementing an algorithm.

流程图符号：椭圆形表示开始/结束，矩形表示处理步骤，菱形表示判断，平行四边形表示输入/输出。这些符号有助于在实现算法前可视化逻辑。

Tracing an algorithm involves completing a trace table that records variable values at each step. This is essential for verifying correctness and understanding how data changes.

追踪算法需要填写追踪表，记录每一步的变量值。这对于验证正确性和理解数据变化至关重要。

---

3. Bin Packing Algorithms | 装箱算法

The bin packing problem aims to pack items of given sizes into bins of fixed capacity using as few bins as possible. A lower bound for the number of bins is ⌈(sum of item sizes) / (bin capacity)⌉.

装箱问题旨在将给定大小的物品装入固定容量的箱子，并使使用的箱子数量尽可能少。箱子数量的下界是 ⌈(物品总大小) / (箱子容量)⌉。

First-fit algorithm: place each item into the first bin that has enough remaining space. It is fast but may not give the optimal solution.

首次适应算法：将每件物品放入第一个有足够剩余空间的箱子。它速度快，但未必给出最优解。

First-fit decreasing: sort items into descending order, then apply first-fit. This often produces better results because larger items are packed first.

降序首次适应：先将物品按大小降序排列，再使用首次适应。由于先处理大件物品，通常能得到更好的结果。

Full-bin packing: look for combinations of items that exactly fill a bin, pack those, then use first-fit for the remainder. This heuristic reduces waste and can lead to optimal solutions in simple cases.

满箱策略：寻找能恰好装满一个箱子的物品组合，优先装入，再对剩余物品使用首次适应。这种启发式方法减少浪费，在简单情况中可能得到最优解。

---

4. Sorting Algorithms | 排序算法

Sorting algorithms arrange data into order. In D1 you need to know bubble sort, shuttle sort (insertion sort), and quick sort, along with their efficiencies.

排序算法将数据按顺序排列。D1 中你需要了解冒泡排序、穿梭排序（插入排序）和快速排序，以及它们的效率。

Bubble sort: repeatedly compare adjacent items and swap if they are in the wrong order. After each pass, the largest unsorted element bubbles to the end. The maximum number of comparisons is n(n – 1)/2.

冒泡排序：重复比较相邻项，如果顺序错误则交换。每趟之后最大的未排元素会“冒泡”到末尾。最大比较次数为 n(n – 1)/2。

Shuttle sort (insertion sort): build a sorted sublist by inserting each new item into its correct place. In the worst case it also requires O(n²) comparisons but is efficient for nearly sorted data.

穿梭排序（插入排序）：通过将每个新项插入到正确位置来逐步构建有序子列表。最坏情况下也需要 O(n²) 次比较，但对近乎有序的数据非常高效。

Quick sort: select a pivot, partition the list into items less than the pivot and items greater than the pivot, then recursively sort each sublist. Average case is O(n log₂ n); worst case with poor pivot choice is O(n²).

快速排序：选择一个枢轴，将列表划分为小于枢轴的元素和大于枢轴的元素，然后递归排序每个子列表。平均情况为 O(n log₂ n)；枢轴选择不佳时最坏为 O(n²)。

A comparison summary helps choose the right algorithm:

以下对比有助于选择合适的算法：

Algorithm	Worst-case comparisons	Stable?
Bubble sort	½ n(n – 1)	Yes
Shuttle sort	½ n(n – 1)	Yes
Quick sort	O(n²)	Not necessarily

Table: Sorting algorithm comparison | 排序算法对比

---

5. Graphs and Networks | 图与网络

A graph consists of vertices (nodes) connected by edges (arcs). A network is a weighted graph where edges carry numbers like distance or cost. Key terms include degree of a vertex, path, cycle, tree, and complete graph Kₙ.

图由顶点（节点）和连接它们的边（弧）组成。网络是带权图，边带有距离或成本等数值。关键术语包括顶点的度、路径、回路、树以及完全图 Kₙ。

A tree is a connected graph with no cycles. A spanning tree connects all vertices without cycles. Complete graph Kₙ has n vertices with every pair connected by a unique edge; it has n(n – 1)/2 edges.

树是连通且无回路的图。生成树连接所有顶点且无回路。完全图 Kₙ 有 n 个顶点，每对顶点间都有唯一一条边相连，共有 n(n – 1)/2 条边。

Bipartite graphs have vertices that split into two disjoint sets, with edges only between sets. They are used in matching problems.

二分图的顶点可分成两个不相交的集合，边只存在于不同集合之间。它们用于匹配问题。

Handshaking lemma: the sum of degrees of all vertices equals twice the number of edges. This is used to determine Eulerian trails.

握手引理：所有顶点的度之和等于边数的两倍。它用于判断欧拉路径的存在性。

---

6. Minimum Spanning Trees | 最小生成树

A minimum spanning tree (MST) finds a tree that connects all vertices with the smallest total edge weight. Two standard algorithms are Kruskal and Prim.

最小生成树（MST）寻找连接所有顶点且边权总和最小的树。两种标准算法是克鲁斯卡尔算法和普里姆算法。

Kruskal’s algorithm: list all edges in ascending order of weight. Select the smallest edge that does not create a cycle. Repeat until (n – 1) edges are chosen. This works well when edges are given as a list.

克鲁斯卡尔算法：按权重升序列出所有边。选择不构成回路的最小边，重复直到选出 (n – 1) 条边。当边以列表形式给出时，此方法很有效。

Prim’s algorithm: start at any vertex and grow the tree by repeatedly adding the cheapest edge that connects a tree vertex to a non-tree vertex. You may use a table or a matrix to record the process.

普里姆算法：从任意顶点开始，不断添加连接树内顶点与树外顶点的最便宜边，从而扩展生成树。可使用表格或矩阵记录过程。

Both algorithms always produce the same minimum total weight, though the tree may differ if there are equal weights. In D1 exams you must show steps clearly.

两种算法总能得到相同的最小总权重，但若存在权重相等的边，得到的树可能不同。在 D1 考试中你必须清晰地展示步骤。

---

7. Dijkstra’s Shortest Path Algorithm | 迪杰斯特拉最短路径算法

Dijkstra’s algorithm finds the shortest path from a start node to all other nodes in a weighted graph. Edge weights must be non-negative. It uses working values (temporary labels) and permanent labels.

迪杰斯特拉算法用于在带权图中寻找从起点到所有其他节点的最短路径。边的权重必须非负。它使用工作值（临时标签）和永久标签。

Box method: at each vertex you record the order of permanent labelling, the shortest distance from start, and the preceding vertex. The algorithm repeatedly selects the unvisited vertex with the smallest working value, makes it permanent, and updates neighbours.

方框法：在每个顶点处记录永久标签的次序、从起点出发的最短距离和前任顶点。算法反复选择未访问且工作值最小的顶点，将其永久化，并更新其邻居。

The process continues until the destination is permanently labelled. You can then read off the shortest path and its length. A trace of all working values is essential for full marks.

持续该过程直到目标顶点被永久标记。然后可读出最短路径及其长度。展示所有工作值的追踪是获得满分的关键。

If a graph has negative weights, Dijkstra fails; but D1 only considers non-negative weights.

若图中有负权重，迪杰斯特拉算法会失败；但 D1 只考虑非负权重。

---

8. Route Inspection Problem | 路径检查问题

The route inspection (Chinese postman) problem seeks the shortest walk that traverses every edge at least once, starting and ending at the same vertex. It is solvable by examining the degrees of vertices.

路径检查（中国邮递员）问题要求找出遍历每条边至少一次且起点和终点重合的最短行走路线。可通过检查顶点度数来求解。

If all vertices have even degree, the graph is Eulerian and the optimal route is any Eulerian circuit; total length equals sum of all edge weights.

如果所有顶点的度均为偶数，则图是欧拉图，最优路线为任意欧拉回路，总长度等于所有边权重之和。

If exactly two vertices have odd degree, the graph is semi-Eulerian. You must find all possible pairings of odd vertices, add the shortest paths between them as repeated edges, and choose the pairing that adds the minimum extra weight.

若恰好有两个顶点的度为奇数，则图是半欧拉图。你需要找出所有奇度顶点的配对方案，将两两之间的最短路径作为重复边添加，然后选择增加额外权重最小的配对。

When there are more than two odd-degree vertices, list all possible pairings, calculate the extra distance for each, and select the minimum. The solution then follows an Eulerian trail on the modified graph.

当奇度顶点多于两个时，列出所有可能的配对方式，计算每种配对新增的距离，并选取最小值。然后在修改后的图上沿欧拉路径行走即可。

---

9. Critical Path Analysis | 关键路径分析

Critical path analysis (CPA) helps schedule activities in a project to minimise its overall duration. Activities are represented as edges on a precedence diagram or as nodes in an activity-on-node network.

关键路径分析（CPA）用于安排项目中的活动，以最小化整体持续时间。活动可用前导图中的边或节点网络中的节点表示。

Each activity has a duration and depends on predecessors. The earliest start time (EST) and earliest finish time (EFT) are computed by a forward pass. The latest finish time (LFT) and latest start time (LST) come from a backward pass.

每个活动都有持续时间并取决于前导活动。最早开始时间（EST）和最早完成时间（EFT）通过前推计算得出。最晚完成时间（LFT）和最晚开始时间（LST）通过后推计算得出。

Total float = LFT – EFT (or LST – EST). Activities with zero total float are critical; any delay in them delays the whole project. The critical path is the longest path through the network.

总浮动时间 = 最晚完成时间 – 最早完成时间（或最晚开始时间 – 最早开始时间）。总浮动时间为零的活动为关键活动；它们的任何延误都会延误整个项目。关键路径是网络中最长的路径。

A Gantt chart gives a visual timeline but is not required for all CPA questions. Scheduling with limited resources may require adjusting non-critical activities within their float.

甘特图提供可视时间线，但并非所有 CPA 题目都要求。在资源受限的情况下调度，可能需要利用非关键活动的浮动时间来调整。

---

10. Linear Programming | 线性规划

Linear programming (LP) formulates an optimisation problem with a linear objective function and linear constraints. It is a powerful tool for maximising profit or minimising cost subject to limited resources.

线性规划（LP）用线性目标函数和线性约束来表述优化问题。它是受限于有限资源时最大化利润或最小化成本的强大工具。

Steps: define decision variables (e.g., x and y), write the objective function (maximise or minimise), list constraints as inequalities (e.g., 2x + 3y ≤ 24), and state non-negativity (x ≥ 0, y ≥ 0).

步骤：定义决策变量（如 x 和 y），写出目标函数（最大化或最小化），将约束列为不等式（如 2x + 3y ≤ 24），并声明非负条件（x ≥ 0, y ≥ 0）。

Draw the feasible region by graphing each inequality. The optimal solution lies at a vertex of the feasible region. Use an objective line or test all vertex coordinates to find the optimum.

通过为每个不等式作图画出可行域。最优解位于可行域的顶点处。使用目标直线或检验所有顶点坐标来找到最优解。

If integer solutions are required, search around the continuous optimum and check all integer points within the feasible region.

若需要整数解，则在连续最优解附近搜索，并检查可行域内的所有整数点。

Objective: Maximise P = 5x + 4y subject to x + 2y ≤ 10, 3x + y ≤ 12, x, y ≥ 0

目标：最大化 P = 5x + 4y，约束为 x + 2y ≤ 10, 3x + y ≤ 12, x, y ≥ 0

---

11. Matchings in Bipartite Graphs | 二分图匹配

A matching pairs vertices from two disjoint sets such that no vertex is used more than once. A maximal matching is one where no more edges can be added without violating the matching property. A complete matching (perfect matching) pairs every vertex from the smaller set.

匹配将两个不相交集合的顶点进行配对，使得每个顶点最多使用一次。极大匹配是指无法再添加边而不违反匹配性质的匹配。完全匹配（完美匹配）则将较小集合中的每个顶点都配对。

The alternating path algorithm starts from an unmatched vertex on one side and builds an alternating path (edges not in matching / in matching) to another unmatched vertex. Augmenting the path flips edge statuses and increases the size of the matching by one.

交替路径算法从一侧未匹配的顶点出发，构建一条交替路径（未匹配边 / 匹配边交替）到达另一未匹配顶点。增广路径会翻转边的状态，使匹配规模增加一。

This algorithm is applied repeatedly until no alternating path can be found. The resulting matching is a maximum matching.

Published by TutorHao | A-Level Mathematics Revision Series | aleveler.com

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