📚 Decision Maths 1: Core Topics A & B Revision | 决策数学1：AB核心知识点精讲
Decision Mathematics 1 forms an essential part of A-level Further Maths, introducing algorithms, graph theory, critical path analysis, and linear programming. This article covers the core A and B topics you need to master: from sorting and searching to network optimisation and resource allocation. Every concept is broken down with clear steps and paired bilingual explanations to help you revise efficiently.
决策数学1是A-level进阶数学的重要组成部分，主要介绍算法、图论、关键路径分析和线性规划。本文梳理了必须掌握的AB核心知识点，从排序与搜索到网络优化和资源分配。每个概念都配有清晰的步骤和中英双语讲解，帮助你高效复习。
1. What is an Algorithm? | 什么是算法？
An algorithm is a finite sequence of step-by-step instructions designed to solve a specific problem. Every algorithm must have a clear input and output, be precisely defined, and terminate after a finite number of steps. In Decision Maths, we evaluate algorithms by their efficiency – often using the number of comparisons or swaps required.
算法是解决特定问题的一系列有限步骤的指令。每一个算法必须有明确的输入和输出，定义精确，并且在有限步数内结束。在决策数学中，我们通常通过比较或交换的次数来评估算法的效率。
We often express worst-case time complexity using 'big O' notation. For example, bubble sort has O(n²) complexity, while binary search runs in O(log n) time. Understanding complexity helps you choose the best algorithm for a given set of data.
我们常用“大O”表示法来描述最坏情况下的时间复杂度。例如，冒泡排序的复杂度是O(n²)，而二分搜索的运行时间为O(log n)。理解复杂度有助于你为给定数据选择最佳算法。
2. Sorting Algorithms | 排序算法
Bubble sort repeatedly compares adjacent items and swaps them if they are in the wrong order. After each pass, the largest unsorted element 'bubbles up' to its final position. You stop when a complete pass makes no swaps.
冒泡排序反复比较相邻元素，若顺序错误则交换它们。每完成一趟，最大的未排序元素就会“浮”到最终位置。如果某一趟没有发生任何交换，算法终止。
Quick sort selects a pivot and partitions the list into elements less than the pivot and those greater. It then recursively sorts the sublists. The pivot is placed in its correct final position between the two sublists. Using the middle item as pivot often gives consistent results in exam problems.
快速排序选择一个基准值，将列表分为小于基准值和大于基准值的两部分，然后递归地对子列表排序。基准值最终落在两个子列表之间的正确位置。考试题目中通常以中间项作为基准值，结果更稳定。
3. Binary Search & Bin Packing | 二分搜索与装箱问题
Binary search applies to an ordered list. You repeatedly compare the target with the middle item. If it matches, the search ends. If the target is smaller, you discard the upper half; if larger, discard the lower half. Each comparison halves the size of the remaining list, giving O(log n) time.
二分搜索适用于有序列表。你反复将目标值与中间项比较。若相等则搜索结束。若目标值较小，则舍弃较大的那一半；若较大，则舍弃较小的那一半。每次比较后剩余列表长度减半，时间复杂度为O(log n)。
Bin packing is the problem of placing items of given sizes into bins of fixed capacity, aiming to minimise the number of bins used. The first-fit algorithm takes each item in turn and places it into the earliest bin with enough space. First-fit decreasing sorts items into descending order first, which usually yields a better solution. These are heuristic algorithms – they work quickly but do not guarantee an optimal outcome.
装箱问题是将给定大小的物品放入定容量的箱子中，力求使用最少数量的箱子。首次适应算法依次将每个物品放入第一个能容纳它的箱子。降序首次适应则先将物品按大小降序排列，通常能得到更优解。这些是启发式算法——速度快但不保证最优结果。
4. Graphs & Networks | 图与网络
A graph consists of vertices (nodes) connected by edges (arcs). Graphs can be directed or undirected; a network is a graph where each edge carries a weight, representing distance, time, or cost. A tree is a connected graph with no cycles. A spanning tree connects all vertices using a subset of edges.
图由顶点（节点）和边（弧）构成。图可以是有向或无向的；网络是每条边都带有权重（如距离、时间或成本）的图。树是不含环的连通图。生成树是用一部分边连接所有顶点的树。
A path is a sequence of vertices where each adjacent pair is joined by an edge. A cycle is a path that starts and ends at the same vertex. The degree of a vertex is the number of edges incident to it. In a simple graph, the sum of all vertex degrees is twice the number of edges – this is the handshaking lemma.
路径是一串顶点，其中相邻顶点之间都有边相连。环是起点和终点相同的路径。顶点的度是与其相连的边的数量。在简单图中，所有顶点度之和等于边数的两倍——这就是握手引理。
5. Minimum Spanning Trees – Kruskal & Prim | 最小生成树–克鲁斯卡尔与普里姆算法
Kruskal's algorithm builds a minimum spanning tree by considering edges in order of increasing weight. It selects an edge if it connects two vertices not yet in the same component, using a union-find process. Repeat until all vertices are connected.
克鲁斯卡尔算法按权重递增顺序考虑每条边，若该边连接两个尚未属于同一分量的顶点，则选中它。重复进行直到所有顶点都连通。
Prim's algorithm grows the tree from an arbitrary start vertex. At each step, it adds the shortest edge connecting a vertex already in the tree to a vertex not yet in the tree. Both Kruskal and Prim produce the same total weight if all edge weights are distinct, but they may construct different trees.
普里姆算法从一个任意起始顶点开始生长生成树。每一步选取连接树内顶点和树外顶点的最短边。如果所有边权重互异，两种算法得到的最小总权重相同，但生成的树可能不同。
Total weight of MST = sum of selected edge weights
MST总权重 = 所选边权重之和
6. Shortest Path – Dijkstra’s Algorithm | 最短路径–迪杰斯特拉算法
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a network with non-negative weights. You maintain a list of temporary distances, initialised to infinity except the source (0). At each step, select the unvisited vertex with the smallest temporary label, mark it as visited, and update the distances of its neighbours.
迪杰斯特拉算法用于在所有权重非负的网络中寻找从源顶点到其余各顶点的最短路径。维护一个临时距离列表，除源点设为0外，其余初始化为无穷。每一步选取未访问顶点中临时标号最小的，标记为已访问，然后更新其邻居的距离。
Update rule: if d(u) + w(u, v) < d(v), then replace d(v) with d(u) + w(u, v). The algorithm stops when all vertices are visited, or when the destination is permanently labelled.
更新规则：如果 d(u) + w(u, v) < d(v)，则用 d(u) + w(u, v) 代替 d(v)。当所有顶点都被访问过，或目标顶点已获得永久标号时，算法结束。
After the algorithm finishes, the shortest path can be traced back from the destination using the recorded predecessors. On exam papers, you are often required to show the working in a table or a diagram with boxes.
算法完成后，可通过记录的前驱顶点从终点回溯出最短路径。考试中通常要求以表格或方框图展示计算过程。
7. Route Inspection Problem | 路径检查问题（中国邮递员）
The route inspection problem aims to find the shortest route that traverses every edge at least once, returning to the start. For a network with all even vertex degrees, an Eulerian circuit exists and covers every edge exactly once – the optimal route is just the sum of all edge weights.
路径检查问题要求找到一条至少遍历每条边一次并回到起点的最短路线。对于所有顶点度数均为偶数的网络，存在欧拉回路恰好经过每条边一次——最优路线长度就是所有边权重之和。
If the graph has odd-degree vertices, they must appear in pairs. You pair these odd vertices to add extra shortest paths between them, duplicating those edges. The total route length is the sum of all original edge weights plus the minimum sum of duplicated lengths to make all degrees even.
如果图中有奇数度顶点，它们必须成对出现。你需要将这些奇点两两配对，添加它们之间的最短路径（即复制那些边）。总路线长度等于原有边权重之和加上为实现全偶度而复制的最小路径长度。
8. Critical Path Analysis | 关键路径分析
A project is modelled as an activity network, where activities (arrows or nodes) have durations and precedence constraints. The earliest start time (EST) of an activity is the earliest time it can begin, computed by a forward pass. The latest finish time (LFT) is the latest time it can finish without delaying the project, found by a backward pass.
项目可建模为活动网络，活动（用箭线或节点表示）具有持续时间及先后约束。最早开始时间（EST）为活动可以开始的最早时刻，通过顺推计算。最迟完成时间（LFT）为不延误整个项目的前提下活动可以完成的最迟时刻，通过逆推求得。
The total float of an activity is LFT – EST – duration. Activities with zero total float form the critical path – any delay on these activities directly delays the whole project. Identifying the critical path helps managers focus resources on the tasks that truly matter.
活动的总浮动时间为 LFT – EST – 持续时间。总浮动时间为零的活动构成关键路径——这些活动一旦延误，整个项目就会延期。找出关键路径有助于管理者将资源集中到真正重要的任务上。
Scheduling can be represented on a Gantt chart or a resource histogram. In Decision Maths exams, you may need to draw a cascade diagram or schedule workers with limited availability.
调度可用甘特图或资源直方图表示。在决策数学考试中，你可能需要绘制级联图或安排有限数量的工人。
9. Linear Programming | 线性规划
Linear programming formulates decision problems involving constraints written as linear inequalities. The feasible region is the set of points satisfying all constraints. If the problem involves two variables, you can graph the inequalities and shade the unwanted regions, leaving the feasible region clear.
线性规划将约束条件写成线性不等式来构建决策问题。可行域是所有满足约束条件的点的集合。如果问题包含两个变量，可以画出不等式图形，将不可行区域去掉，留下清晰的可行域。
e at each vertex and select the best one. The objective line method involves drawing a line of the form ax + by = P and sliding it parallel until it reaches the last point of the feasible region.
最优解（最大化或最小化目标函数）出现在可行域的顶点处。计算每个顶点处的目标函数值，选择最优的。目标线法是画出 ax + by = P 形式的直线，并向可行域边界平行滑动，直到触及可行域的最后一个点。
Integer solutions are required when the variables represent discrete items. You list integer points near the optimal vertex and test them to find the one that satisfies all constraints while giving the best objective value.
当变量代表离散物品时，需要整数解。列出最优顶点附近的整数点并逐一检验，找到满足所有约束且使得目标函数最优的那个解。
10. Matchings in Bipartite Graphs | 二分图匹配
A bipartite graph has two disjoint sets of vertices, and every edge joins a vertex from one set to the other. A matching is a set of edges with no shared vertices. A maximal matching cannot be improved by simply adding another edge, while a maximum matching contains the largest possible number of edges.
二分图有两组互不相交的顶点，每条边都连接来自不同组的一个顶点。匹配是一组互不共享顶点的边。极大匹配无法通过简单添加一条边来改进，而最大匹配包含尽可能多的边数。
The alternating path algorithm improves a matching by finding an alternating path that starts and ends at unmatched vertices. By swapping the status of edges along this path, the size of the matching increases by one. This process is repeated until no such path exists, giving a maximum matching.
交替路径算法通过寻找一条从未匹配顶点出发并结束于另一未匹配顶点的交替路径来改进匹配。沿着这条路径交换边的匹配状态，匹配的规模就会加一。重复此过程直到不存在这样的路径，即可得到最大匹配。
Matchings are applied to assignment problems, such as allocating tasks to workers or students to projects. The initial matching can often be found using a greedy approach, then refined with the alternating path method.
匹配应用于指派问题，例如将任务分配给工人或学生分配到项目。初始匹配通常可用贪心法获得，然后通过交替路径方法进行优化。
Published by TutorHao | Further Maths Decision Maths 1 Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图