📚 IB AQA Mathematics: Mastering Algorithms for Exams | IB AQA 数学：算法考点精讲
Algorithms lie at the heart of modern problem‑solving in mathematics, computer science, and logistics. In IB AQA Mathematics, the algorithm topics cover a wide range of graph theory, optimisation, and decision‑making processes. This guide breaks down the essential concepts, standard algorithms, and exam techniques you need, with clear step‑by‑step explanations. From minimum spanning trees and shortest paths to the Chinese postman problem, critical path analysis, and the simplex method, each section is crafted to build your confidence and accuracy.
算法是现代数学、计算机科学和运筹学问题求解的核心。在 IB AQA 数学中，算法考点涵盖了图论、最优化和决策过程的广泛内容。本文梳理了必备的概念、经典算法和应试技巧，并配合清晰的逐步讲解。从最小生成树和最短路径，到中国邮递员问题、关键路径分析以及单纯形法，每个小节都旨在帮助你建立信心，提高解题准确性。
1. What is an Algorithm? | 什么是算法？
An algorithm is a finite, step‑by‑step set of instructions designed to solve a specific problem or perform a computation. In mathematics, algorithms must be well‑defined: each step is unambiguous, it produces an output for given inputs, and it terminates after a finite number of operations. Common characteristics include clarity, effectiveness, and the ability to handle all valid input cases. For example, an algorithm to add two numbers is simple, but the same principles apply to complex procedures such as sorting data or finding the shortest path in a network.
算法是一组有限的、逐步执行的操作指令，旨在解决特定问题或完成某种计算。在数学中，算法必须定义清晰：每一步都是明确的，能针对给定输入产生输出，并且能够在有限次操作后终止。算法的常见特性包括明确性、有效性和能够处理所有合法输入的能力。例如，两数相加的算法很简单，但同样的原则也适用于数据排序或在网络中寻找最短路径等复杂过程。
The study of algorithms often involves comparing their efficiency – measured by the number of steps or the amount of memory used as the input size grows. Efficiency is expressed using Big‑O notation (e.g., O(n), O(n²), O(log n)). For IB exams, you need to be able to trace an algorithm, describe its steps, and apply it to given problems without formal complexity analysis, though understanding runtime helps in selecting the best method.
算法的学习常常涉及其效率的比较——即随着输入规模增长，所需步骤数或内存使用量的变化。效率常用大O符号表示（如 O(n), O(n²), O(log n)）。在 IB 考试中，你需要能够跟踪算法、描述其步骤，并将其应用于给定问题，而不要求正式进行复杂度分析，但了解运行时间有助于选择最佳方法。
2. Graph Theory Basics | 图论基础
A graph consists of vertices (nodes) connected by edges (arcs). Edges may be weighted (with numbers representing cost, distance, or time) and can be directed (arrows showing one‑way roads) or undirected. A path is a sequence of edges connecting vertices without repeating vertices; a circuit (or cycle) starts and ends at the same vertex. A graph is connected if there is a path between every pair of vertices. A tree is a connected graph with no cycles, and a spanning tree includes all vertices of the original graph with the minimum number of edges (V‑1 edges). The degree of a vertex is the number of edges incident to it.
图由顶点（节点）和连接它们的边（弧）组成。边可以带有权值（表示成本、距离或时间的数值），并且可以是有向的（箭头表示单行道）或无向的。一条路径是一系列连接顶点的边，且不重复经过顶点；回路（或圈）则是起点和终点相同的路径。如果图中任意两个顶点之间都存在路径，则该图是连通的。树是一种无圈的连通图，而一个生成树包含了原图的所有顶点，并使用最少数量的边（V‑1 条边）。顶点的度是指与该顶点相连的边的数目。
Key representations include adjacency matrices and lists. For weighted graphs, a table showing edge weights between pairs of vertices is common in exams. Understanding these fundamentals is essential for applying Kruskal’s, Prim’s, Dijkstra’s, and other graph algorithms.
常见的图表示方法有邻接矩阵和邻接表。对于带权图，考试中常用表格来展示各顶点对之间的边权。理解这些基础知识是应用 Kruskal 算法、Prim 算法、Dijkstra 算法以及其他图算法的前提。
3. Kruskal’s Algorithm for Minimum Spanning Tree | Kruskal 最小生成树算法
Kruskal’s algorithm builds a minimum spanning tree (MST) by adding edges in order of increasing weight, skipping any edge that would create a cycle. The steps are: (1) List all edges in ascending order of weight. (2) Start with an empty edge set for the tree. (3) Select the edge with the smallest weight that does not form a cycle with the edges already chosen. (4) Repeat until V‑1 edges have been added (where V is the number of vertices). The resulting tree connects all vertices with the minimum total weight.
Kruskal 算法通过按权重递增的顺序添加边来构建最小生成树，并跳过任何会形成回路的边。步骤为：(1) 将所有边按权重从小到大排列。(2) 为树初始化一个空的边集。(3) 选择权重最小且不与已选边构成回路的边。(4) 重复上述步骤，直到加入 V‑1 条边（V 为顶点数）。最终得到的树以最小的总权重连接了所有顶点。
This algorithm is particularly efficient when the graph is sparse. Exam questions often provide a table of edges and ask you to list the edges in the order they are added. You may need to draw the tree and verify the total weight. Always check for cycles by visually tracing or by noting whether both endpoints of a candidate edge are already connected in the current forest.
该算法在稀疏图中尤为高效。考试题目通常提供边的列表，要求你写出边被添加的顺序，并可能需要画出生成树并验证总权重。务必通过目视跟踪或判断候选边的两个端点是否已在当前森林中连通来检查回路。
4. Prim’s Algorithm | Prim 算法
Prim’s algorithm also finds an MST but grows the tree from a chosen starting vertex. Steps: (1) Choose any start vertex and mark it as visited. (2) Consider all edges connecting visited vertices to unvisited vertices; select the edge with smallest weight. (3) Add that edge and the new vertex to the tree. (4) Repeat until all vertices are included. If there is a tie, any smallest‑weight edge may be chosen. Prim’s is often implemented using an adjacency matrix, making it suitable for dense graphs.
Prim 算法同样可以找出最小生成树，但它从某个选定的初始顶点开始逐步扩展树。步骤为：(1) 选择任意起始顶点并将其标记为已访问。(2) 考虑所有连接已访问顶点与未访问顶点的边，并从中选出权重最小的边。(3) 将该边及新的顶点加入树中。(4) 重复直到所有顶点都被包含。如遇权重相同的边，可以任选其一。Prim 算法常用邻接矩阵实现，因此特别适合稠密图。
In exams you might be asked to apply Prim’s algorithm starting from a specific vertex, often displayed in a matrix of distances. Record the order in which vertices are added and the corresponding edge weights. The final MST will have the same total weight as the one found by Kruskal’s, but the selection order may differ.
考试中可能会要求你从某一特定顶点开始执行 Prim 算法，题目通常给出距离矩阵。记录顶点加入的顺序以及对应的边权重。最终得到的最小生成树总权重与 Kruskal 算法求得的结果相同，但边的选择顺序可能不同。
5. 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 weights. Steps: (1) Label the start vertex with distance 0 and all others with ∞. Mark all vertices as unvisited. (2) From the current vertex, consider all unvisited neighbours and update their tentative distances if a shorter path is found. (3) Mark the current vertex as visited. (4) Select the unvisited vertex with the smallest tentative distance as the new current vertex. (5) Repeat until the destination is visited or all vertices are visited. The final labels give the shortest distances.
Dijkstra 算法用于在边权为非负值的带权图中，寻找从源顶点到所有其他顶点的最短路径。步骤为：(1) 将起始顶点标注距离 0，其余顶点标注距离 ∞。所有顶点标记为未访问。(2) 从当前顶点出发，考察所有未访问邻点，若能找到更短路径则更新其临时距离。(3) 将当前顶点标记为已访问。(4) 选择临时距离最小的未访问顶点作为新的当前顶点。(5) 重复，直到目标顶点被访问或所有顶点都已访问。最终标注值即为最短距离。
Dijkstra’s algorithm is often presented in a tabular format, where each row corresponds to a vertex and columns show the distance updates. You must be able to complete such a table and trace the shortest‑path tree. The algorithm can also be used to reconstruct the actual path by recording the predecessor vertex each time a label is updated.
Dijkstra 算法常以表格形式呈现，表中每一行对应一个顶点，各列展示距离的更新情况。你必须能够填写这类表格并追溯最短路径树。此外，每当更新标注值时记录下前驱顶点，就可以重建实际路径。
6. Chinese Postman Problem | 中国邮递员问题
The Chinese Postman Problem (CPP) seeks the shortest closed walk that traverses every edge of a weighted graph at least once – ideal for postal delivery routes or street sweeping. If the graph is Eulerian (all vertices have even degree), the optimal route is simply an Eulerian circuit and the total length equals the sum of all edge weights. When there are odd‑degree vertices, the problem reduces to pairing odd vertices with the shortest additional paths so that the augmented graph becomes Eulerian. The total length is the sum of all original edges plus the lengths of the added shortest paths between paired odd vertices.
中国邮递员问题寻求一条最短的闭合行走路线，使其至少遍历带权图中的每条边一次——非常适用于邮递路线或街道清扫。如果图是欧拉图（所有顶点度数均为偶数），则最优路线就是一条欧拉回路，总长度等于所有边权之和。当存在奇度顶点时，问题转化为将奇度顶点用最短的额外路径配对，使得增广后的图成为欧拉图。总长度等于原图所有边权之和，再加上配对奇度顶点之间最短路径的总长度。
To solve CPP: (1) Identify all odd‑degree vertices. (2) Find the shortest distances between every pair of these vertices (using Dijkstra’s on the original graph). (3) Form a complete graph of odd vertices with edges weighted by the shortest distances; find a minimum weight perfect matching. (4) Duplicate the edges along the matched shortest paths. (5) Find an Eulerian circuit in the augmented graph. Exam questions typically involve small graphs where the pairing can be done by inspection rather than a full matching algorithm.
求解中国邮递员问题的步骤：(1) 找出所有奇度顶点。(2) 求这些顶点间每一对的最短距离（在原图上使用 Dijkstra 算法）。(3) 构建以奇度顶点为顶点的完全图，边权为最短距离；找出最小权完美匹配。(4) 将匹配的最短路径上的边进行复制。(5) 在增广图中寻找一条欧拉回路。考试题通常涉及小规模图，可以通过观察完成配对，而不需完整的匹配算法。
7. Travelling Salesman Problem (Nearest Neighbour) | 旅行商问题（最近邻算法）
The Travelling Salesman Problem (TSP) asks for the shortest Hamiltonian cycle – a closed tour visiting every vertex exactly once and returning to the start. The problem is NP‑hard, so exact solutions are impractical for large graphs. The nearest neighbour algorithm provides a simple heuristic to find an upper bound: (1) Start at a chosen vertex. (2) From the current vertex, go to the nearest unvisited vertex. (3) Repeat until all vertices are visited, then return directly to the start. The total distance of this tour is an upper bound for the optimal TSP length. The quality of the bound depends on the starting vertex; trying all possible starting points can help find a better bound.
旅行商问题要求找出最短的哈密顿回路——即一个访问每个顶点恰好一次并返回起点的闭合旅程。该问题是 NP‑难的，因此对于大规模图很难精确求解。最近邻算法提供了一个简单的启发式方法来寻找上界：(1) 从选定的顶点开始。(2) 从当前顶点出发，走到最近的未访问顶点。(3) 重复直到所有顶点都访问过，然后直接返回起点。该旅程的总距离即为 TSP 最优长度的一个上界。上界的优劣取决于起始顶点的选择；尝试所有可能的起始点有助于获得更紧的上界。
IB exams may also require you to find a lower bound by removing a vertex, finding the MST of the remaining graph, and adding the two smallest edges incident to the removed vertex. This gives a lower bound for the optimal tour. The gap between the upper and lower bounds indicates the quality of the nearest neighbour approximation.
IB 考试还可能要求你通过删除一个顶点，求出剩余图的最小生成树，并加上与该删除顶点关联的两条最短边，来得到最优旅程的下界。上界与下界之间的差距反映了最近邻近似解的质量。
8. Critical Path Analysis | 关键路径分析
Critical Path Analysis (CPA) is used in project management to schedule activities with dependencies. Activities are represented as vertices (in an activity‑on‑node diagram) or edges, with duration times. Key quantities: earliest start time (EST) – the earliest an activity can begin given its predecessors; latest start time (LST) – the latest it can begin without delaying the whole project; total float = LST – EST. Activities with zero float are critical; any delay in them delays the entire project. The sequence of critical activities forms the critical path.
关键路径分析应用于项目管理中，用于安排具有依赖关系的各项活动。活动可以表示为节点（在节点图示法中）或边，并标有持续时间。关键量包括：最早开始时间 (EST)——考虑紧前活动后，活动可以开始的最早时间；最迟开始时间 (LST)——在不延误整个项目的前提下，活动最迟必须开始的时间；总浮动时间 = LST – EST。浮动时间为零的活动称为关键活动；其中任何延误都会导致整个项目推迟。关键活动的序列构成关键路径。
To construct a precedence network: (1) Draw a start node and an end node. (2) For each activity, draw a node (or edge) and connect according to dependencies. (3) Perform a forward pass to compute ESTs: for each activity, EST = max(EST of all predecessors + their duration). (4) Backward pass to compute LSTs: start at the end, set LST of finish equal to its EST (project duration), then for each activity, LST = min(LST of all successors) – its duration. (5) Calculate float and identify critical path(s). Exam questions often give a table of activities and dependants; you must be able to produce a Gantt chart or network diagram and calculate the minimum project duration.
构建优先网络图的步骤：(1) 画出起始节点和结束节点。(2) 为每个活动画出节点（或边），并根据依赖关系连接。(3) 向前推算 EST：对于每个活动，EST = max(所有紧前活动的 EST + 活动持续时间)。(4) 向后推算 LST：从终点开始，令终点的 LST 等于其 EST（即项目总工期），然后对每个活动，LST = min(所有后续活动的 LST) – 活动持续时间。(5) 计算浮动时间并找出关键路径。考试题通常会给出活动及其紧前活动的表格；你需要能够绘制甘特图或网络图，并计算最短项目工期。
9. Simplex Algorithm for Linear Programming | 线性规划的单纯形法
The simplex algorithm solves linear programming (LP) problems where an objective function is maximised (or minimised) subject to linear constraints. The standard form: maximise P = c₁x₁ + c₂x₂ + … subject to constraints like a₁₁x₁ + a₁₂x₂ ≤ b₁, with xᵢ ≥ 0. Slack variables are introduced to turn inequalities into equations: a₁₁x₁ + a₁₂x₂ + s₁ = b₁. The initial simplex tableau places these equations in a matrix with an objective row: P – c₁x₁ – c₂x₂ = 0. The algorithm iterates by selecting a pivot column (most negative in the objective row for maximisation) and a pivot row (minimum ratio of RHS to pivot column positive coefficient), then performing row operations to make the pivot element 1 and other entries in that column 0. This continues until all objective row entries are non‑negative, yielding the optimal solution.
单纯形法用于求解线性规划问题，即在线性约束条件下最大化（或最小化）目标函数。标准形式为：最大化 P = c₁x₁ + c₂x₂ + …，约束条件如 a₁₁x₁ + a₁₂x₂ ≤ b₁，且 xᵢ ≥ 0。引入松弛变量将不等式转化为等式：a₁₁x₁ + a₁₂x₂ + s₁ = b₁。初始单纯形表将这些方程放在一个矩阵中，并附上目标行：P – c₁x₁ – c₂x₂ = 0。算法通过选择主元列（对最大化问题，目标行中最负的项）和主元行（右端项与主元列正系数的最小比值），然后进行行变换，使主元变为 1 且该列其他元素为零，如此迭代进行。当目标行所有条目均为非负时，迭代停止，即得最优解。
IB exams typically test the ability to set up the initial tableau from a word problem, perform one or two full iterations, and interpret the final tableau. You must be able to spot when the solution is optimal and read the values of decision variables, slack variables, and the optimal objective value. Sometimes two‑stage simplex is needed when there are “≥” constraints or artificial variables, though basic problems involve “≤” constraints only.
IB 考试通常考查根据文字应用题建立初始单纯形表、执行一至两次完整迭代以及解读最终表格的能力。你必须能够判断何时达到最优解，并读出决策变量、松弛变量的取值以及最优目标函数值。在涉及“≥”约束或人工变量时，可能需要进行两阶段单纯形法，但基础题目仅涉及“≤”约束。
10. Algorithmic Efficiency and Big‑O Notation | 算法效率与大O符号
Efficiency measures how the running time or memory usage grows with input size. Big‑O notation gives an upper bound on this growth, ignoring constant factors and lower‑order terms. For example, Kruskal’s algorithm runs in O(E log E) time (where E is the number of edges) if edges are sorted efficiently; Prim’s algorithm can run in O(V²) with a simple matrix implementation. Dijkstra’s algorithm typically runs in O(V²) when using an adjacency matrix, or O((V+E) log V) with priority queues. Understanding these differences helps in choosing the right algorithm, though IB Mathematics does not require formal proofs of complexity – only a qualitative appreciation.
效率衡量的是运行时间或内存占用随输入规模增长的变化情况。大O符号给出了这种增长的上界，忽略常数因子和低阶项。例如，若能高效排序边，Kruskal 算法的运行时间为 O(E log E)（E 为边数）；Prim 算法用简单的矩阵实现时为 O(V²)。Dijkstra 算法常用邻接矩阵时为 O(V²)，若使用优先队列则为 O((V+E) log V)。理解这些差异有助于选择合适的算法，不过 IB 数学不要求形式化的复杂度证明，只需定性了解即可。
In your written answers, you may be asked to state why one algorithm is preferred over another for a given graph (e.g., “Prim’s is faster for dense graphs” or “Kruskal’s is easier to apply when edges are listed”). Always relate your justification to the structure of the input data.
在书面作答中，你可能需要说明为什么对给定图来说某种算法比另一种更可取（例如，“对于稠密图，Prim 算法更快”或“当边以列表给出时，Kruskal 算法更容易操作”）。务必结合输入数据的结构来阐明理由。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply