网络放大器设置问题：贪心算法与数据结构课程设计全解析

简介山东大学数据结构与算法课程设计实验中的网络放大器设置问题完整实现与学习资料面向正在学习图算法、准备课程设计的高校学生。资源使用C语言编写以加权有向无环图建模汽油传送网络求解在最小压力约束下放置最少数量的压力放大器代码包含详细注释并提供多组测试样例便于验证算法正确性。压缩包共9个文件内含2个C源文件、6个文本记录测试样例、方案运行时间和1个Markdown分析文档整体仅4KB结构紧凑适合下载后直接阅读与复用。已有262人学习下载。资源重点对比了BFS与DFS两种求解思路的时间性能BFS复杂度为O(n²)DFS因遍历所有情况高达O(2^n)并用图表直观显示差异同时指出贪心局部最优策略不一定得到全局最优解有助于深入理解算法设计复杂度与适用边界。1. 网络放大器设置问题一门数据结构课设到底在考你什么某高校的《数据结构与算法》课程设计里“网络放大器设置问题”几乎是每年都被挑走的一场大作业。拿到题的第一反应通常是网络、链路、放大器那不上最短路、最小生成树真把样例手算一遍就发现它考的不是图算法而是你愿不愿意先把问题抽象成一条带衰减的链路再用最朴素的顺序表和一次线性扫描去解决它。题目的显式输入是节点数、初始信号功率和每段的衰减量隐式要求是在最少的位置布置放大器让整条链路上所有节点的信号都不低于某个阈值。这套方案按需求建模、数据结构设计、算法选型、C 实现到验收答辩的顺序展开覆盖从敲第一行代码到讲清楚“为什么对”的全过程。2. 需求与数据建模先定输入输出再谈算法2.1 题目还原信号衰减、阈值与放大器的定义经典描述是一条链式通信线路节点 1 是信号源节点 2 到节点 n 是逐级中继接收端。信号每经过一条边就会衰减固定数值例如经过衰减量为 3 的一段信号就减 3。当信号降到某个阈值以下接收端就无法正确解码链路作废。放大器的作用是把到达该节点时的信号恢复到初始功率之后信号继续沿链路向下传播。这里有一个容易理解错的地方放大器到底放在“边上”还是“节点上”。课程设计里默认放在节点上且一个节点最多放一个。放完之后该节点接收到的信号变成初始功率而不是在原有信号上叠加。目标函数有两个放大器数量最少以及在这个数量下把每个放大器的位置输出。如果题目不要求输出唯一解那么我一般和导师确认一次位置取“尽量靠后”还是“尽量靠前”样例通常按“尽量靠后”的贪心结果给。除了基本语义题目还隐含一个可行性约束如果某一段的衰减量大于初始功率减阈值那么即使这一段两端都放放大器也可能无解因为中间没有节点可以恢复。实验题的数据通常保证单段衰减不超过这个差值但代码里仍然要检查遇到不合法数据直接输出 -1。2.2 输入输出格式与必测样例输入通常是多组样例读到文件尾结束。每组第一行是节点数 n第二行是初始功率 P 和阈值 R第三行给出 n-1 个整数代表每段链路的衰减量。输出一般是放大器总数、放置的节点编号以及每个节点的最终信号值。5 10 2 3 4 1 3手工推演一遍节点 1 信号 10过衰减 3 到节点 2 剩 7过衰减 4 到节点 3 剩 3过衰减 1 到节点 4 剩 2恰好等于阈值如果再直接过衰减 3节点 5 就要变成 -1链路失败。所以必须在节点 4 放一个放大器节点 4 的信号恢复为 10再过 3 的衰减到节点 5 剩 7。答案是 1 个放大器位置第 4 号节点。这个样例我建议学生全部手算一遍再编码。因为下标特别容易错衰减数组只有 n-1 个元素但在代码里遍历时却要和节点编号 i 对齐。如果从 0 开始读边从 1 开始数节点经常会出现“该放大的是节点 3代码输出节点 4”的半对结果。2.3 数据结构设计Node 与 Edge 的字段约定线性链路的建模不一定非要上邻接表顺序表就够。我这里一般定义两个结构体Edge 负责描述一条边Node 负责描述节点状态。字段设计如下字段类型含义Edge.fromint边起点编号从 1 开始Edge.toint边终点编号Edge.decaylong long这条边带来的信号衰减量Node.powerlong long信号到达该节点时的强度Node.amplifiedbool该节点是否被放置了放大器为什么用 long long 而不是 int因为课程设计数据看上去不大但一旦做压力测试例如 n 到十万、每段衰减量上万累加值很快超过 int 范围。用 long long 只是多写两个字母却能避免答辩时被随机大数据问倒。如果是树形网络的扩展场景才需要把顺序表换成邻接表以及做一次 DFS。线性链路的本质是单一路径顺序表加下标访问就是最自然的结构不必为了“显得高级”强行引入图结构。数据结构选型不是堆砌而是匹配问题的形状。3. 总体设计贪心策略、DP 变体与复杂度取舍3.1 把问题压缩成区间覆盖可用余量 P-R整条链路能不能走通只取决于一个数初始功率 P 与阈值 R 的差值 P-R。这个差值代表“信号从被恢复之后可以容忍的最大总衰减量”。每经过一条边就从可用余量里扣掉一个衰减值一旦某个节点上的累计衰减超过 P-R该节点信号就会低于阈值。所以问题本质变成了一个区间覆盖问题链路上的每一段都必须被某一个放大器“覆盖”并且两个相邻放大器之间的衰减总量不能超过 P-R。判断条件里用的是“超过”而不是“大于等于”因为题目语义一般是“不低于阈值”等于阈值是允许的。如果导师要求“严格大于阈值”只需要把判断符号改一处。把问题翻译成这句话之后很多人会自然想到二分答案、动态规划或者暴力搜索但都没有必要。这些方法能解决更一般的变体却无法突出这道题贪心的简洁性。3.2 贪心算法从左到右只扫一遍贪心策略是线性扫描从节点 1 出发维护一个 loss 变量表示离最近一个放大器已经累计衰减了多少。每次准备经过边 i 时先检查 loss 加这条边的衰减量是否大于 P-R。如果大于说明再不放放大器下一个节点就撑不住了那么必须把放大器放在当前节点 i 上并把 loss 清零。信号到达节点 1loss 0 for i 1 到 n-1 如果 loss 衰减量[i] P - R 在节点 i 放置放大器 loss 0 loss loss 衰减量[i] 节点 i1 的信号 P - loss为什么放在当前节点而不是下一节点因为下一节点是接收端信号到达它时已经衰减过了再在它身上放放大器虽然也能恢复但这段衰减仍然浪费了一次“被放过”的机会。放在当前节点等于把恢复点前移一段能覆盖后续更多边。这也是贪心解的直观来源。这个算法的正确性可以用交换论证说清楚对于任意最优解把它的第一个放大器位置和贪心解的第一个放大器位置比较。贪心选择的放大器一定不会比最优解更靠前因为贪心在还能走通的情况下绝不放置因此贪心解第一个放大器覆盖的区间长度不短于最优解。接下来从该放大器出发对剩余的链路重复同样的论证贪心解每轮的覆盖范围都不短于最优解所以总放大器数不会多于最优解也就是最优。3.3 为什么不是回溯也不是拆成最短路径回溯枚举的复杂度是 2 的 n 次方n 到二十就明显吃力。最短路模型又要求我们把“衰减”映射成边权把“放大器”映射成路径上的恢复点反而要把链路拆成多层状态实现麻烦且没有体现出数据结构课程设计的重点。线性扫描不需要额外空间时间复杂度 O(n)空间 O(n) 用于记录节点信号这才是这道题作为课程设计的合理深度。3.4 带节点成本的 DP 扩展当贪心失效时如果题目改成每个节点放置放大器的成本不同或者放大器恢复后的功率不是固定值贪心就不成立了。此时需要动规。一种常见改法是节点 i 放置放大器的代价为 cost[i]求最小总代价。定义 dp[i] 表示前 i 个节点都合规且节点 i 放置了放大器的最小代价转移时枚举上一个放大器所在位置 j要求 j 到 i 之间的衰减总量不超过 P-R。dp[1] cost[1] for i 2 到 n dp[i] 无穷大 for j 1 到 i-1 如果 从 j 到 i-1 的衰减总和 P - R dp[i] min(dp[i], dp[j] cost[i]) 答案 min(dp[n], dp[n-1], ...)这个扩展不要求写在基础版代码里但很适合写进设计报告的“算法对比”一节。我在答辩时见到最稳妥的一类学生都是先讲清楚基本版贪心为什么最优再补一句“若引入节点成本问题升级为线性动态规划复杂度 O(n²)”。只讲贪心显得单薄只讲 DP 又显得没抓住实验题本意。三种算法的取舍可以归纳成一张表算法时间复杂度空间复杂度适用场景贪心扫描O(n)O(n)放大器恢复固定功率成本相同动态规划O(n²)O(n)节点成本不同恢复策略不同回溯枚举O(2^n)O(n)仅 n 20 的验证场景4. C 模块实现工程结构、核心代码与图表输出4.1 工程文件划分与输入解析工程不需要做成一个大 main 文件。为了课程设计报告好看也为了自己调试省事我一般按四层来分结构体定义、求解器、输入输出、测试数据。amplifier/ ├── solver.h # Node、Edge、AmplifierSolver 声明 ├── solver.cpp # 贪心与校验实现 ├── main.cpp # 读取输入调用求解器输出结果 ├── export_csv.cpp # 导出画图数据 ├── testcases/ │ ├── in1.txt # 基础样例 │ ├── in2.txt # 单段衰减恰好等于 P-R │ └── in3.txt # n 较大时压力样例输入读取用 C 标准流即可多组样例用 while 循环。这里最容易踩坑的是空行和无效输入。稳健做法是逐项读整数而不是逐行读字符串因为样例文件里可能有注释行或空行干扰 getline 解析。4.2 核心贪心求解器实现下面是求解器的核心代码注释已经按课程设计汇报的要求写清楚了关键判断逻辑集中在 solve 函数里。#include bits/stdc.h using namespace std; struct Edge { int from, to; // 边的两端节点编号1-based long long decay; // 该段链路的信号衰减量 }; struct Node { long long power; // 到达该节点时的信号强度 bool amplified; // 该节点是否需要放置放大器 }; class AmplifierSolver { private: int n; // 节点总数 long long power; // 初始信号功率 P long long threshold; // 阈值 R vectorEdge edges; // 链路段共 n-1 条 vectorNode nodes; // 每个节点的信号状态 vectorint placed; // 记录放大器位置 long long budget; // 可容忍总衰减量 P-R public: AmplifierSolver(int n_, long long p_, long long th_, const vectorlong long decays) : n(n_), power(p_), threshold(th_) { budget power - threshold; // 把一维衰减数组映射成边结构 for (int i 1; i n; i) { edges.push_back({i, i 1, decays[i - 1]}); } nodes.resize(n 1); placed.clear(); } int solve() { long long loss 0; // 距最近放大器已累计衰减 nodes[1].power power; // 信号源 for (int i 1; i n; i) { // 进入第 i 段之前判断当前节点 i 是否需要承担放大器 if (loss edges[i - 1].decay budget) { nodes[i].power power; nodes[i].amplified true; placed.push_back(i); loss 0; } // 正常经过这一段 loss edges[i - 1].decay; nodes[i 1].power power - loss; } return (int)placed.size(); } // 校验最终链路每个节点信号是否合规 bool verify() const { for (int i 1; i n; i) { if (nodes[i].power threshold) return false; } return true; } const vectorint getPlaced() const { return placed; } const vectorNode getNodes() const { return nodes; } };这段代码里有三个细节值得在报告里单独说明。第一个是判断时机必须在“经过第 i 段之前”判断而不是在算出下一个节点信号之后再去补救。第二个是 loss 清零后节点 i 的信号已经被覆盖成初始功率所以 CSV 导出时不能直接沿用循环之前的值。第三个是 edges 用 vector 按下标访问而不是用链表因为这里不需要增删边顺序表对随机访问更友好。4.3 结果校验与 CSV 导出写完贪心后不能只看输出数量还要强制跑一遍 verify。把最终信号打印到文件逐项对比阈值这一步能杜绝绝大多数半路翻车。void exportCSV(const string path) { ofstream fout(path); fout node,signal,amplifier\n; for (int i 1; i n; i) { fout i , nodes[i].power , (nodes[i].amplified ? 1 : 0) \n; } }CSV 文件格式是 node、signal、amplifier 三列amplifier 字段为 1 表示该节点放放大器。这个文件既可以直接交给导师看也能喂给 Python 脚本画图。4.4 用 Matplotlib 画信号衰减曲线图表部分是课程设计报告里比较出彩的模块。我一般用 Python 读 CSV画出信号随节点变化的折线同时把放大器节点用散点标记出来。import pandas as pd import matplotlib.pyplot as plt df pd.read_csv(signal_curve.csv) plt.figure(figsize(8, 4)) plt.plot(df[node], df[signal], markero, labelsignal) amp df[df[amplifier] 1] plt.scatter(amp[node], amp[signal], colorred, s80, labelamplifier) plt.axhline(ydf[signal].min(), colorgray, linestyle--, linewidth1) plt.xlabel(node) plt.ylabel(signal power) plt.legend() plt.grid(True) plt.savefig(signal_curve.png, dpi150)绘图脚本不参与课程要求的算法实现但它能直观看出放大器放在哪里、信号在哪几个节点被恢复。答辩时放一张图比念十行输出结果更有说服力。4.5 一份可读的输出样例以第 2 章的样例为例跑完程序后输出表格化的内容如下节点编号信号强度是否放置放大器说明110否信号源27否经过衰减 333否经过衰减 4410是放大器恢复信号57否经过衰减 3这个表格放进设计报告的实验结果节再配上一张信号曲线图输出的完整性就够了。5. 常见问题与避坑测试全过不代表能答辩5.1 放大器数量总是差一个边界条件写错位置现象样例都能跑通但自己随手改一个衰减量输出放大器数就比手算少一个或多一个。原因把判断放在了“下一个节点信号算出来之后”导致放大器的位置比真正需要的位置晚了半拍。例如走到节点 i1 发现信号已经低于阈值才在节点 i1 放放大器但真正应该在节点 i 放。解决严格按照“进入某段之前判断”的逻辑。放大器的恢复效果发生在当前节点覆盖的是接下来那一段不是已经走过的段。5.2 输入样例一直死循环多组样例的读入坑现象程序读取第二组样例时读到了第一组末尾残留的换行或空行导致解析错位甚至 while 循环读不到 EOF。原因用 getline 按行读取时行末回车没有处理好或者输入文件里混了注释和空行。解决直接用while (cin n)读整数让标准流自动跳过空白字符。这能避免 90% 的输入解析问题。5.3 int 溢出和负信号数据范围别省现象n 只有一千时程序正常换到 n 十万的测试数据信号值突然变成奇怪的大负数。原因衰减量累加超过了 int 范围或者在某处把 long long 强制转换成了 int。解决所有信号量和衰减量统一用 long long。写代码时从结构体字段到临时变量都用同一类型杜绝隐式转换。5.4 曲线图上的放大器位置不对忘了覆盖节点信号值现象CSV 里信号曲线是对的但放大器标记点却落在阈值线下方。原因放置放大器后没有把该节点的 power 字段重新赋值为 P导出的节点信号还是放大前的旧值。解决在 placed.push_back(i) 旁边同步执行 nodes[i].power power。每次插入放大器位置的代码块里都要带上这一行不要只维护 placed 数组。5.5 只验证样例不验证最优性对拍器才是后悔药现象几个手写样例全过答辩时被问“你怎么证明最少”只能支支吾吾。原因没有做正确性验证把样例通过当成了完整验收。解决写一个 n 不超过 20 的暴力枚举程序枚举所有放大器的放置子集找出合法解里数量最少的一个再随机生成几百组小数据让暴力程序和贪心程序对拍。两者输出不一致就说明贪心或暴力至少有一个错了。这套对拍流程不到一百行却能救回答辩现场最尴尬的问题。6. 测试、验收与答辩把方案从“能跑”变成“无懈可击”6.1 验收清单与测试用例设计课程设计验收不能只看最终结果。我一般把测试分成四类基础样例、边界样例、压力样例、错误样例。基础样例就是题目给的数据验证功能边界样例覆盖“衰减量恰好等于 P-R”“P 等于 R”“所有段衰减总量刚好在阈值之内”三种情况压力样例用十万级节点验证时间复杂度错误样例故意让单段衰减超过 P-R验证程序输出 -1 而不是崩溃。用例类型输入要点期望结果基础样例n5P10R2衰减 3 4 1 31 个放大器节点 4边界样例某段衰减恰为 P-R不放置放大器也能过压力样例n100000随机衰减线性扫描秒级出结果错误样例单段衰减大于 P-R输出 -16.2 随机数据对拍让程序自己和自己打架对拍脚本很短但价值很高。暴力程序枚举所有子集对每个合法方案统计放大器数量取最小值贪心程序跑同一组输入。用循环生成随机 n 和随机衰减量比较两份输出。一旦发现不一致就缩小到那组随机数据手动排查。这个流程能把“我觉得最优”变成“程序验证过最优”。6.3 答辩时最可能被追问的五个问题每次答辩都会围绕“为什么”展开而不是围绕“怎么写的”展开。我整理了五个高频追问为什么贪心得到的一定是最少的放大器数用交换论证贪心每次选择的恢复点不早于任何最优解的同序恢复点覆盖范围只长不短。如果每个节点放大器成本不同怎么办回答线性 DP 扩展复杂度 O(n²)说明你已经想清楚了贪心的适用边界。时间复杂度和空间复杂度分别是多少O(n) 时间、O(n) 空间。为什么用顺序表而不是链表因为这里只有按下标访问没有插入删除。如果某一段衰减超过 P-R 怎么办输出 -1并说明该链路单独一段就无法满足阈值。答辩前把所有输出都重新跑一遍 verify把 CSV 和曲线图再生成一次。从那以后我每次做课程设计都强制走一遍对拍和边界测试半路翻车的概率明显小了很多。这份方案的完整工程文件、测试样例和绘图脚本已打包在资源里下载后按 README 编译即可复现所有结果希望帮到你。本文还有配套的精品资源点击获取