📚 Decision Mathematics 1: Key Concepts | 决策数学1 知识点精讲
Decision Mathematics 1 (D1) introduces students to the systematic study of algorithms, networks, and optimisation. It covers essential techniques for solving practical problems such as finding the shortest route, scheduling tasks, packing items efficiently, and matching resources. This article provides a comprehensive revision of all core topics, with step‑by‑step explanations and examples to support exam success.
决策数学1（D1）向学生介绍算法、网络与优化的系统研究。它涵盖了解决实际问题的基本技术，例如寻找最短路径、任务调度、高效装箱以及资源匹配。本文对全部核心主题进行全面复习，提供逐步解释与示例，助力考试成功。
1. Algorithmic Thinking and Complexity | 算法思维与复杂度
An algorithm is a finite sequence of well‑defined instructions for solving a problem. In D1, we analyse algorithms by counting the number of fundamental operations, typically comparisons and swaps. The order of an algorithm describes how its running time grows with the size of the input, n. Common orders include linear, O(n), and quadratic, O(n²).
算法是用于解决问题的、定义明确的有限指令序列。在 D1 中，我们通过计算基本操作（通常是比较和交换）的次数来分析算法。算法的阶描述了其运行时间如何随输入规模 n 的增长而改变。常见阶包括线性 O(n) 和二次 O(n²) 等。
For instance, a simple linear search through an unsorted list has order n in the worst case, whereas a bubble sort on n items takes up to ½ n(n−1) comparisons, giving a worst‑case quadratic order. Understanding complexity helps us select the most efficient approach for a given problem.
例如，简单的无序列表线性查找在最坏情形下阶为 n，而 n 个元素的冒泡排序最多需要 ½ n(n−1) 次比较，给出最坏情形下的二次阶。理解复杂度有助于针对给定问题选择最高效的方法。
2. Sorting Algorithms: Bubble Sort and Quick Sort | 排序算法：冒泡排序与快速排序
Bubble sort repeatedly passes through the list, comparing adjacent pairs and swapping them if they are in the wrong order. After each pass, the largest unsorted element settles into its final position. The algorithm continues until a complete pass requires no swaps, indicating the list is ordered.
冒泡排序反复遍历列表，比较相邻对并在顺序错误时交换它们。每趟遍历后，最大的未排序元素沉入最终位置。算法持续进行，直到一整趟无需任何交换，表明列表已有序。
Quick sort uses a pivot element to partition the array into two sub‑lists: items less than the pivot and items greater than the pivot. The sub‑lists are then recursively sorted. Quick sort, on average, has complexity O(n log n), making it significantly faster than bubble sort for large data sets.
快速排序使用一个枢轴元素将数组划分为两个子列表：小于枢轴的项和大于枢轴的项。然后递归地对子列表排序。快速排序平均复杂度为 O(n log n)，使其在大数据集上远比冒泡排序快。
Both algorithms are fully examinable, and you should be able to perform them manually on small lists, showing each pass and tracking comparisons and swaps. In the worst case, quick sort can degrade to O(n²) if poor pivots are chosen consistently.
这两种算法都是考试内容，你应能在小型列表上手动执行它们，展示每一趟并跟踪比较与交换。在最坏情况下，如果始终选择糟糕的枢轴，快速排序可能退化至 O(n²)。
3. Bin Packing: Heuristics and Optimality | 装箱问题：启发式与最优性
The bin packing problem asks to pack a set of items of given sizes into the minimum number of bins of fixed capacity. Since finding the exact optimum is computationally hard, we use heuristic algorithms. The first‑fit algorithm places each item into the first bin that has enough space; if no such bin exists, a new bin is opened.
装箱问题要求将给定尺寸的一组物品装入固定容量的最少箱子中。由于精确最优解计算难度高，我们使用启发式算法。首次适应算法将每件物品放入第一个有足够空间的箱子；如果没有这样的箱子，就开一个新箱。
First‑fit decreasing is an improved version that first sorts the items into descending order of size and then applies first‑fit. This often produces a solution with fewer bins. A useful lower bound for the number of bins is the ceiling of the total size divided by the bin capacity.
降序首次适应是改进版，首先将物品按尺寸降序排列，再应用首次适应。这通常能得到使用更少箱子的解。箱子数量的有用下界是总尺寸除以箱子容量的上取整。
When tackling exam questions, always state the order of items, show each allocation step clearly, and check whether your solution meets the lower bound, which may demonstrate optimality.
解答考试题目时，务必说明物品顺序，清楚展示每一步分配，并检查解是否达到下界，这可以证明最优性。
4. Graph Theory Foundations | 图论基础
A graph consists of vertices (nodes) connected by edges. In a weighted graph, each edge carries a numerical weight, representing cost, distance or time. A path is a sequence of edges connecting vertices; a cycle is a closed path. A tree is a connected graph with no cycles, and a spanning tree connects all vertices without cycles.
图由通过边连接的顶点（节点）组成。在赋权图中，每条边带有一个数值权重，代表成本、距离或时间。路径是连接顶点的一系列边；回路是一条封闭路径。树是无环连通图，生成树是连接所有顶点且无环的子图。
Directed graphs, or digraphs, have edges with a specific direction. Networks are graphs that have weights and often a source and a sink. These concepts are the building blocks for algorithms such as Prim’s, Dijkstra’s and the Chinese postman algorithm.
有向图（或有向网络）的边具有特定方向。网络是具有权重且通常有发点和收点的图。这些概念是普里姆算法、迪杰斯特拉算法和中国邮递员算法等的基础。
You need to be comfortable with terms including degree (number of edges incident to a vertex), even/odd vertices, complete graphs, and bipartite graphs. The degree of a vertex is critical in route inspection, as odd‑degree vertices determine where repeated edges are needed.
你需要熟练掌握诸如度（与顶点关联的边数）、偶/奇顶点、完全图和二分图等术语。顶点的度在路由检查中至关重要，因为奇度顶点决定了需要添加重复边的位置。
5. Minimum Spanning Trees: Kruskal and Prim | 最小生成树：克鲁斯卡尔与普里姆算法
A minimum spanning tree (MST) is a spanning tree of a weighted, connected graph that has the smallest possible total weight. Two classic algorithms find an MST: Kruskal’s and Prim’s. You must be able to execute both and know when each is more convenient.
最小生成树（MST）是赋权连通图的总权重尽可能小的生成树。寻找 MST 有两种经典算法：克鲁斯卡尔算法和普里姆算法。你必须会执行这两种算法，并知道何时哪种更方便。
Kruskal’s algorithm sorts all edges by weight, then selects the smallest edge that does not create a cycle. It builds the tree by adding edges one by one until all vertices are connected. This method is efficient when the graph is sparse.
克鲁斯卡尔算法将所有边按权重排序，然后选择不形成回路的最小边。它通过逐一添加边来构建树，直到所有顶点连通。当图稀疏时该方法高效。
Prim’s algorithm starts from any vertex and repeatedly adds the cheapest edge that connects a vertex already in the tree to a vertex outside it. It can be implemented using a table for the distance matrix. Prim’s is particularly quick on dense graphs.
普里姆算法从任意顶点开始，反复添加连接树内顶点与树外顶点的最小权重边。它可以借助距离矩阵用表格来实现。普里姆算法在稠密图上尤其快速。
Exam questions may ask you to draw the MST, state the order of selected edges, or compare the two algorithms. Always check that the final tree has exactly (V−1) edges for V vertices.
考试题目可能要求你画出 MST、陈述边的选择顺序或比较两种算法。务必检查最终的树对于 V 个顶点恰好有 (V−1) 条边。
6. Dijkstra's Shortest Path Algorithm | 迪杰斯特拉最短路径算法
Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non‑negative edge weights. It uses labels (distance, previous vertex) that are updated as better paths are discovered. Starting at the source with permanent label 0, it iteratively makes the smallest temporary label permanent and updates adjacent vertices.
迪杰斯特拉算法在边权重非负的赋权图中找出从源顶点到所有其他顶点的最短路径。它使用标签（距离，前一顶点），当发现更优路径时进行更新。从源点开始，永久标签为 0，迭代地将最小的临时标签变为永久，并更新相邻顶点。
The working values are typically displayed in a table. The order of permanently labelled vertices gives the shortest path tree. To recover the route to a specific vertex, trace back from that vertex using the previous vertex information. Dijkstra’s algorithm is fundamental in logistics and network routing.
工作值通常显示在表格中。永久标签顶点的顺序给出了最短路径树。要恢复到达特定顶点的路径，利用前一顶点信息从该顶点回溯。迪杰斯特拉算法在物流和网络路由中是基础性算法。
When you present your solution, show the full table with columns for each vertex, clearly indicating when a label becomes permanent. If the graph has a large number of vertices, it is acceptable to use a systematic boxed method.
展示解答时，要为每个顶点展示完整表格列，清楚地表明标签何时变为永久。如果图有大量顶点，可以使用系统的框格法。
7. Route Inspection: The Chinese Postman Problem | 路由检查：中国邮递员问题
The route inspection problem seeks a closed walk that traverses every edge at least once, minimising total distance. If a graph is Eulerian (all vertices even degree), an Eulerian circuit gives the optimum route without repeated edges. When odd‑degree vertices exist, we must add duplicate edges along paths pairing them up.
路由检查问题寻找一条至少遍历每条边一次的闭行走，并最小化总距离。若图是欧拉图（所有顶点度数为偶），则一条欧拉回路给出无需重复边的最优路线。当存在奇度顶点时，我们必须沿配对路径添加重复边。
The procedure: identify all odd vertices, find the shortest paths between each pair using a matrix, then use a minimum weight matching of the odd vertices to determine which paths should be doubled. Adding these extra edges makes all degrees even, after which an Eulerian circuit can be found.
操作步骤：找出所有奇顶点，用矩阵求出每对间的最短路径，然后对奇顶点做最小权重匹配，以确定哪些路径应加倍。添加这些额外边使所有度数变为偶数，随后可找到一条欧拉回路。
In exams, you will be given the shortest distances between odd vertices and then need to select the combination of pairings that yields the least extra length. Always state the repeated edges and the total length of the route.
在考试中，会给出奇顶点间的最短距离，你需要选择产生最少额外长度的配对组合。务必说明重复边和路线的总长度。
8. Critical Path Analysis | 关键路径分析
Critical path analysis helps schedule activities in a project to determine the minimum completion time. Activities are represented by nodes or by edges on an activity‑on‑arc network. From a precedence table, you construct the network, ensuring correct dependencies and using a single start and finish node.
关键路径分析有助于安排项目中的活动，以确定最短完成时间。活动用节点或在箭线网络中通过边表示。根据前导表构建网络，确保依赖关系正确且仅用单个开始节点和结束节点。
Once the network is drawn, perform forward pass to calculate earliest start times (EST) and earliest finish times. The project duration is the earliest finish time of the end activity. Then carry out a backward pass to find latest start times (LST). Total float for an activity is LST − EST. Activities with zero total float are critical.
网络画成后，进行正推计算最早开始时间（EST）和最早完成时间。项目工期为结束活动的最早完成时间。然后进行反推，求出最迟开始时间（LST）。活动的总时差为 LST − EST。总时差为零的活动是关键活动。
A critical path is a path of critical activities from start to finish. Identifying it allows project managers to focus resources on tasks that directly impact the deadline. You must be able to produce a straight cascade chart showing floats and critical activities.
关键路径是从开始到结束的一系列关键活动路径。识别它使项目经理能将资源集中于直接影响截止时间的任务。你必须能够绘制展示时差和关键活动的直瀑式图表。
9. Linear Programming: Formulation and Graphical Solution | 线性规划：建模与图解法
Linear programming (LP) is used to maximise or minimise a linear objective function subject to linear inequality constraints. Typical problems involve allocating limited resources such as materials, time, or money. The decision variables are the unknowns we can control.
线性规划（LP）用于在线性不等式约束下最大化或最小化线性目标函数。典型问题涉及分配有限资源，如材料、时间或资金。决策变量是我们可以控制的未知量。
To solve a two‑ an isoprofit line for the objective function and slide it parallel until it leaves the region at the optimal vertex. Read the coordinates and evaluate the objective.
要用图解法求解双变量线性规划，先画出由约束（包括 x ≥ 0, y ≥ 0）定义的可行域。然后画出目标函数的等值线，平行移动直到离开可行域处的那个顶点即为最优。读取坐标并计算目标值。
If the optimal vertex does not have integer coordinates and integer solutions are required, inspect the integer points near the boundary. The optimal integer solution is the one that satisfies all constraints and gives the best objective value. Always test neighbouring points.
若最优顶点坐标非整数而要求整数解，需检查边界附近的整数点。满足所有约束并给出最佳目标值的整数点即为最优整数解。务必测试相邻点。
10. Matching in Bipartite Graphs | 二分图匹配
A bipartite graph consists of two disjoint sets of vertices, with edges only joining vertices from the different sets. A matching is a set of edges with no shared vertices. A maximum matching contains the largest possible number of edges, and a complete matching pairs every vertex from one set.
二分图由两个不相交的顶点集组成，边只连接不同集合的顶点。匹配是一组无公共顶点的边。最大匹配包含尽可能多的边，完全匹配则使得其中一个集合的所有顶点都配对。
The alternating path algorithm is used to find a maximum matching. Start from an initial matching (perhaps empty). For each unmatched vertex, try to find an alternating path that ends at another unmatched vertex. If such a path exists, swap the matched and unmatched edges along it to increase the size of the matching by one.
应用交替路径算法来寻找最大匹配。从初始匹配（可能为空）开始。对每个未匹配顶点，尝试寻找一条结束于另一个未匹配顶点的交替路径。如果存在这样的路径，交换路径上的匹配边与未匹配边，使匹配的边数增加 1。
Continue until no further alternating paths can be found. At this point the matching is maximal. In exam problems, you will be required to demonstrate a complete matching where possible, or to state the size of the maximal matching and justify that no improvement exists.
持续进行直到无法找到更多交替路径。此时的匹配即为最大匹配。在试题中，你可能需要演示一个完整匹配（若可能），或陈述最大匹配的大小并证明不存在改进余地。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图