一、引言一核心概念定义本文覆盖软考高级系统架构设计师 “数学与经济管理” 知识模块两大核心领域一是图论应用包含最小生成树、最短路径、网络最大流量三类典型网络优化问题二是决策理论包含不确定型决策、风险型决策决策树两类决策分析方法。上述内容均属于考试大纲要求的定量分析方法每年必考 1-2 道计算题分值占比 2-4 分是必须掌握的得分点。二历史发展脉络图论相关算法起源于 20 世纪中期1956 年克鲁斯卡尔提出最小生成树的边选择算法同年普里姆提出顶点扩展的最小生成树算法1959 年迪杰斯特拉发表最短路径标号算法1956 年福特 - 富尔克森提出网络最大流的增广路径求解方法。决策理论发展同步推进19 世纪提出拉普拉斯等可能准则20 世纪 40 年代形成萨维奇后悔值准则、赫尔维茨折中准则20 世纪 50 年代决策树方法开始应用于工业决策场景。三知识体系定位上述知识点属于系统架构设计师 “项目管理与经济分析” 能力范畴是架构方案选型、资源优化配置、技术路线决策的核心定量工具既要求掌握算法原理也要求具备真题场景下的快速计算能力。本文将按照算法原理、操作步骤、真题案例、易错点分析的逻辑展开覆盖全部考试题型。二、图论应用最小生成树算法一核心原理最小生成树是连通无向图中连接所有顶点、总边权最小的树结构满足三个特性包含全部 n 个顶点、边数为 n-1、无回路。两类经典算法的核心逻辑如下克鲁斯卡尔Kruskal算法属于边贪心策略按边权从小到大遍历所有边每次选择不形成回路的边加入生成树直到所有顶点连通。判断回路通常采用并查集数据结构时间复杂度为 O (ElogE)适用于边稀疏的图。普里姆Prim算法属于顶点贪心策略从任意初始顶点出发每次选择与当前生成树相连的权值最小的边将对应顶点加入树中直到覆盖所有顶点时间复杂度为 O (n²)适用于顶点少、边密集的图。二真题计算步骤以 2022 年软考真题 “小区燃气管道铺设” 为例7 栋楼房作为顶点楼间可铺设管道的长度作为边权求连通所有楼房的最小总长度。克鲁斯卡尔算法操作步骤1将所有边按权值从小到大排序如边 1-21、边 3-42、边 2-53、边 4-63、边 5-74、边 2-35、边 1-36……2依次选取边用并查集判断顶点是否连通选边 1-2连通顶点 1、2、选边 3-4连通顶点 3、4、选边 2-5连通顶点 1、2、5、选边 4-6连通顶点 3、4、6、选边 5-7连通顶点 1、2、5、7、选边 2-3连通所有 7 个顶点。3总权值求和12334518 百米即最小总长度为 1800 米。两类算法对比对比维度克鲁斯卡尔算法普里姆算法核心对象边顶点时间复杂度O(ElogE)O(n²)适用场景边稀疏、顶点多的网络如通信基站组网边密集、顶点少的网络如园区管道规划回路判断需要并查集支持无需额外判断最小生成树两种算法执行流程示意图左为克鲁斯卡尔边选择过程右为普里姆顶点扩展过程三考试易错点需注意最小生成树的总权值唯一但树的结构可能不唯一若存在多条相同权值的边选择不同边可能得到不同结构的生成树但总权值一致。三、图论应用最短路径标号法一核心原理最短路径问题是求有向 / 无向图中从起点到终点的总权值最小的路径软考中采用迪杰斯特拉标号法求解适用于边权非负的场景。算法核心是动态规划思想维护起点到每个顶点的最短距离数组每次选择未访问顶点中距离最小的顶点更新其邻接顶点的距离直到到达终点。二真题计算步骤以 2021 年软考真题 “城市间最小运输费用” 为例起点为城市 s终点为城市 t路段费用为边权求最小运输费用。标号法操作步骤1初始化起点 s 标号为 0其余顶点标号为无穷大标记所有顶点为未访问。2第一轮从未访问顶点中选标号最小的 s更新其邻接点 a费用 2、b费用 5标记 s 为已访问。3第二轮从未访问顶点中选标号最小的 a2更新其邻接点 c235、bmin (5,22)4标记 a 为已访问。4第三轮从未访问顶点中选标号最小的 b4更新其邻接点 t41014、cmin (5,415)标记 b 为已访问。5第四轮从未访问顶点中选标号最小的 c5更新其邻接点 tmin (14,57)12标记 c 为已访问。6终点 t 标号为 12即最小费用为 12 单位。算法扩展若存在负权边需采用贝尔曼 - 福特算法或 SPFA 算法但软考中仅考查迪杰斯特拉标号法。最短路径标号法执行过程示意图标注每一轮的顶点标号更新过程三考试易错点注意区分 “最短路径总权值” 和 “路径经过的顶点”题目可能要求输出路径顶点或总权值需根据题干要求作答若存在多条相同总权值的最短路径只需输出任意一条即可。四、图论应用网络最大流量增广路径法一核心原理网络最大流量问题是在有容量限制的有向图中求从源点到汇点的最大传输能力核心依据是福特 - 富尔克森定理网络的最大流量等于最小割集的容量。软考采用增广路径法求解核心逻辑是反复寻找从源点到汇点的可增流路径更新剩余容量直到不存在增广路径。二真题计算步骤以 2023 年软考真题 “物流运输网最大运量” 为例源点为①汇点为⑥各路段容量标注在边旁求最大运输能力。增广路径法操作步骤1初始化各边剩余容量等于初始容量总流量为 0。2第一次增广寻找路径①→②→⑤→⑥路径上最小剩余容量为 min (6,7,21)6总流量增加 6更新剩余容量①→②剩余 0、②→⑤剩余 1、⑤→⑥剩余 15反向边②→①剩余 6、⑤→②剩余 6、⑥→⑤剩余 6。3第二次增广寻找路径①→③→⑤→⑥路径上最小剩余容量为 min (10,14,15)10总流量增加 10更新剩余容量①→③剩余 0、③→⑤剩余 4、⑤→⑥剩余 5反向边③→①剩余 10、⑤→③剩余 10、⑥→⑤剩余 16。4第三次增广寻找路径①→④→⑥路径上最小剩余容量为 min (10,5)5总流量增加 5更新剩余容量①→④剩余 5、④→⑥剩余 0反向边④→①剩余 5、⑥→④剩余 5。5第四次增广寻找路径①→④→③→⑤→⑥路径上最小剩余容量为 min (5,2,4,5)2总流量增加 2更新剩余容量①→④剩余 3、④→③剩余 0、③→⑤剩余 2、⑤→⑥剩余 3反向边④→①剩余 7、③→④剩余 2、⑤→③剩余 12、⑥→⑤剩余 18。6无新的增广路径总流量为 6105223 万吨 / 小时即最大运量。关键规则增广后正向边容量减去增广流量反向边容量加上增广流量用于实现流量的回退调整。网络最大流量增广过程示意图标注每一轮增广后的剩余容量变化三考试易错点注意反向边的容量更新若忽略反向边会导致计算结果偏小若题干给出的是无向图每条边等价于两条方向相反、容量相同的有向边。五、决策理论不确定型决策准则一核心原理不确定型决策适用于决策者不知道各自然状态发生概率的场景需依据不同决策准则选择最优方案软考考查 5 种标准准则均属于行业通用决策规范。二准则应用方法以 2020 年软考真题 “投资策略选择” 为例三种投资策略对应三种经济状态的收益如下表分别采用不同准则决策策略 / 状态不景气不变景气积极策略50150500稳健策略100200300保守策略300250200乐观主义准则大中取大1取每个方案的最大收益积极 500、稳健 300、保守 300。2选择最大收益对应的方案积极策略。悲观主义准则小中取大1取每个方案的最小收益积极 50、稳健 100、保守 200。2选择最大最小收益对应的方案保守策略。折中主义准则赫尔维茨准则1设定折中系数 α0≤α≤1α 越接近 1 越乐观如 α0.6计算每个方案的折中收益 α× 最大收益 (1-α)× 最小收益。2计算结果积极 0.6×5000.4×50320、稳健 0.6×3000.4×100220、保守 0.6×2500.4×200230选择折中收益最大的积极策略。等可能准则拉普拉斯准则1假设各状态发生概率相等计算每个方案的期望收益积极 (50150500)/3≈233.3、稳健 (100200300)/3200、保守 (300250200)/3250。2选择期望收益最大的保守策略。后悔值准则萨维奇准则1计算各状态下的最大收益不景气 300、不变 250、景气 500。2计算每个方案在各状态下的后悔值 该状态最大收益 - 该方案在该状态的收益得到后悔值矩阵策略 / 状态不景气不变景气最大后悔值积极策略2501000250稳健策略20050200200保守策略003003003选择最大后悔值最小的方案稳健策略。不确定型决策 5 种准则计算流程对比表包含决策逻辑、计算步骤、适用场景三考试易错点注意后悔值计算的是 “该状态下的最大收益减去当前方案收益”而非方案间的收益差折中系数 α 会由题目明确给出无需自行设定。六、决策理论决策树期望收益计算一核心原理决策树适用于风险型决策场景即各自然状态发生概率已知通过计算各方案的期望收益或期望成本选择最优方案属于系统架构方案评估的核心工具符合《系统架构设计师考试大纲》中 “技术方案经济性评估” 的要求。二真题计算步骤以 2019 年软考真题 “系统建设方案选择” 为例四种建设方案的成本及对应概率如下计算各方案的期望成本决策树构成包含决策节点方形、方案分支、状态节点圆形、概率分支、收益 / 成本叶节点计算从叶节点向根节点回溯。计算过程1自行开发方案成功概率 0.3成本 38 万元失败概率 0.7成本 45 万元。期望成本 0.3×38 0.7×4542.9 万元。2复用构件方案需求匹配概率 0.4成本 27.5 万元需求不匹配概率 0.6其中少量调整概率 0.2 成本 31 万元、大量改造概率 0.8 成本 49 万元。期望成本 0.4×27.5 0.6×(0.2×31 0.8×49)38.24 万元。3购买成品方案适配成功概率 0.7成本 21 万元适配失败概率 0.3成本 30 万元。期望成本 0.7×21 0.3×3023.7 万元。4外包方案交付达标概率 0.6成本 35 万元交付不达标概率 0.4成本 50 万元。期望成本 0.6×35 0.4×5041 万元。5选择期望成本最低的购买成品方案。多阶段决策若涉及多阶段决策如前 2 年试运营、后 5 年扩建需分段计算各阶段的期望收益再求和得到总收益。多阶段决策树结构示意图标注节点类型、概率分支、期望计算过程三考试易错点注意区分 “期望收益” 和 “期望成本”收益取最大值成本取最小值若涉及多阶段的时间价值题目会明确给出折现系数需按折现后的收益计算。七、总结与备考建议一核心知识点提炼最小生成树克鲁斯卡尔按边权从小到大选边避回路普里姆从顶点扩展选相邻最小边适用于组网、管道规划等场景。最短路径标号法每次选未访问顶点中距离最小的点更新邻接点适用于路径规划、费用优化等场景。网络最大流量增广路径法反复找可增流路径更新剩余容量直到无增广路径适用于运输、网络带宽规划等场景。不确定型决策5 种准则分别对应不同风险偏好需严格按照计算步骤操作。决策树从叶节点回溯计算各方案期望收益适用于风险型方案评估。二软考考试重点提示高频考点最小生成树总权值计算、最短路径总长度计算、最大流量计算、后悔值准则应用、决策树期望收益计算上述考点近 5 年考试出现频率均超过 80%。易错点最大流反向边更新、后悔值矩阵计算、多阶段决策树的分段收益计算是考生失分的重灾区需重点练习。三备考与实践建议备考策略优先练习近 10 年真题中的相关计算题熟练掌握每类题型的固定计算步骤控制每道题的解题时间在 3 分钟以内。实践应用上述方法可直接应用于架构设计中的资源调度、成本核算、方案选型场景如微服务集群的网络规划、云资源的成本优化、技术路线的决策评估等实现考试知识点与实际架构工作的打通。图论与决策论考点真题题型分布与分值占比统计图