简介：面向参加数学建模竞赛、需要研究最短路径与网络优化案例的学生和指导教师，这份论文以矩形公园道路设计为背景，要求在任意入口间最短路不超过两点直线距离一点四倍的约束下，使园内新建道路总长最短。压缩包仅含一个doc文档，约四百九十五KB，正文按问题重述、模型假设、符号说明、问题分析、数据分析与建模求解展开，便于读者梳理赛题拆解方式和论文写作结构。求解部分依次使用普里姆算法构建最小生成树、弗洛伊德算法计算最短路，并通过局部优化、费马点组合与斯坦纳树方法处理无预设交叉点和矩形湖障碍等情形，给出三问的道路布局、交叉点坐标以及三百九十四点五米、三百五十八点四米、三百五十九点六米等结果。已有三百三十人学习，适合对照算法选择、约束检验和结果表述，也可作为图论优化类建模练习的完整参考。

1. 开篇：公园道路设计题到底在考哪三件事

数学建模里的“公园道路设计”最容易让人误判：看起来是画几条线，实际考的是约束校验、局部返工和结果解释。题目给一个200米×100米矩形公园、8个入口和一个1.4倍最短路约束，还允许矩形四边已建道路不计入总长；真正拉分的地方不是会不会写Prim，而是能否先判断哪些入口对可以走边界、哪些必须新建内部路，再用Floyd逐对验算。问题一给定4个交叉点，考“已知骨架怎么接”；问题二放开交叉点，考Fermat点数量比较；问题三加矩形湖，考障碍下的模型修正。适合正在准备数学建模竞赛、课程设计答辩和算法面试的人，把三问当成同一条答题链来背，分数才稳。

2. 基础考点：Prim、Floyd 与 1.4 倍约束的建模落地

2.1 从矩形公园数据到图模型：节点、边权与边界免费路

公园道路设计题的第一动作不是写代码，而是把题目翻译成图：入口点和给定交叉点都是节点，节点之间的欧氏直线距离是边权，边界上已经建好的道路不计入新修总长。问题一有8个入口P1到P8，再给定A(50,75)、B(40,40)、C(120,40)、D(115,70)四个交叉点，所以图里是12个节点。问题二没有给定交叉点，初始图只放8个入口，后面再用Fermat点扩充节点。问题三多一个矩形湖，湖的四个角R1(140,70)、R2(140,45)、R3(165,45)、R4(165,70)不是入口，但会切断可建边的区域，必须在边集里做删除或绕行处理。

8个入口坐标必须背到能默写：P1(20,0)、P2(50,0)、P3(160,0)、P4(200,50)、P5(120,100)、P6(35,100)、P7(10,100)、P8(0,25)。这几个点不是随便给的，P1、P2、P3在底边，P4在右边，P5、P6、P7在顶边，P8在左边，边界形状决定了哪些入口对可以沿边直达。建模时先算两类距离：一类是两点直线距离，用于构造内部道路候选边；另一类是入口对沿矩形四边的最短距离，用于判断“这对入口能不能只靠边界满足1.4倍约束”。边界道路不计入总长，但在判定时不能忽略，否则会把本可走边界的入口对误判为必须新建道路。

提示：边界道路不计入总长，但在判定入口对能否直接利用边界时，必须把沿边距离算进去；这两件事不矛盾，一个是造价口径，一个是可行性口径。

以P1到P5为例，直线距离是141.4米，1.4倍是198.0米；沿边界从P1走到P5可以走底边、右边、顶边，距离远超198.0米，所以这对入口不能只靠边界满足，必须进入内部道路设计。反过来，有些入口对沿边距离不超过1.4倍直线距离，就可以直接标记为“边界可满足”，不强迫新建内部路。这个预处理能显著缩小后续Prim和Floyd要重点关注的入口对，也能避免在答题时把所有入口对混在一起算，导致约束表又长又乱。

这张表在答题里不是装饰，它决定了后面解释“为什么1→5会超限”“为什么3→7需要绕行”时有没有空间感。阅卷人看建模论文，先看有没有把入口、交叉点、边界路、内部路四种对象分清楚；再看边权是不是直线距离、边界距离是不是单独算。节点表和边权表写清楚，后面的Prim、Floyd、Fermat点才有落脚点。

2.2 Prim求最小生成树：为什么先搭骨架再验约束

Prim在这道题里的角色是“选边搭骨架”，不是直接给最终答案。给定12个节点和两两距离后，Prim从任意一个节点出发，每次选一条连接“已选集合”和“未选集合”的最短边，直到所有节点连通。它得到的是最小生成树：在只考虑总边长最小、不要求任意两点路径满足1.4倍约束时，这是一张很自然的初始网络。问题一先用Prim把8个入口和4个交叉点连起来，问题二先用Prim把8个入口连起来，都是同一个思路。

但这里有一个高频误区：把最小生成树当成最终道路设计。最小生成树只保证整张网络连通且总权最小，不保证任意两个入口之间的树上路径不超过两点直线距离的1.4倍。树上的路径可能绕远，尤其是入口分布在矩形四边、中间节点又少的时候，某些入口对会明显超限。所以正确顺序是“先Prim选边，再Floyd算任意两点最短路，再拿1.4倍约束逐对验算，最后对超限对做局部优化”。这个顺序不能反，反了就会变成“先凭感觉连几条边，再用算法凑结果”，答辩时一问就露馅。

模拟答辩题：为什么不能直接用Floyd算法一次算出所有入口之间的最短路，然后按最短路建路？答题思路要分三层。第一层，Floyd的输入是一张已经确定的图，它只负责在现有边集上算最短路，不负责决定哪些边该建、哪些边不该建。第二层，如果先把所有入口两两相连再跑Floyd，边太多、总长太大，不符合“总道路长度最小”的目标。第三层，Prim负责选边集，Floyd负责在选出的边集上验约束，两者一个管“建什么”，一个管“查是否达标”。面试官最想听的是“选边和验算分离”，而不是背两个算法名字。

注意：Prim得到的是生成树，不是完整图；Floyd要在生成树的邻接矩阵上跑，不能拿原始完全图直接替代，否则约束验算的对象就变了。

从答题节奏看，Prim部分要写清楚三件事：节点集合怎么定、边权怎么算、每次选边的依据是什么。节点集合在问题一是12个点，问题二是8个入口加后续Fermat点；边权是欧氏距离，边界路只参与可行性判定；选边依据是当前可连接边中权值最小。把这三件事写成一段“模型建立”，再配一张最小生成树路径表，阅卷人就能顺着你的逻辑往下看。很多失分卷不是算错，而是把“原始完全图”“最小生成树”“最终优化图”三张图混着写，读者不知道当前表格对应哪一步。

2.3 Floyd补全任意两点最短路：1.4倍约束的判定表

Floyd的任务是把最小生成树上的任意两点最短路算出来。它的核心是三重循环：先允许经过第1个节点中转，再允许经过第2个节点中转，一直扩展到所有节点；每次比较“当前已知距离”和“经过中转点后的距离”，小者留下。对这道题来说，Floyd的输出不是一条路，而是一张最短距离矩阵，外加一张路径回溯表。路径回溯表很关键，因为后面局部优化时要知道某条超限路径到底经过了哪些边，才能判断改哪一条边最划算。

判定1.4倍约束时，不要只验相邻入口。题目要求任意两个入口之间的最短道路长不大于两点连线的1.4倍，8个入口一共有28对，必须逐对检查。实际操作可以分两步：第一步，用边界距离表筛掉“沿边就能满足”的入口对；第二步，对剩下的入口对用Floyd算出的树上最短距离和1.4倍直线距离做比较。比较结果建议做成三列表：入口对、当前最短路径长度、直线距离的1.4倍。超过的标红，进入局部优化；没超过的保留。这样写出来的论文有“验算痕迹”，比只写一句“经检验满足要求”可信得多。

问题一里，1→5、1→6、1→8、2→5、2→6、2→7、3→4、3→5、3→6、3→7这些入口对不能直接利用边缘道路，需要重点看。Floyd算完后，1→5的最短路径长度为203.2米，而1.4倍直线距离是198.0米；2→5的最短路径长度为173.2米，而1.4倍直线距离是170.9米。这两对超限，说明最小生成树骨架还不够，必须做局部调整。注意这里不是把整张图推翻重来，而是找共享边：1→5和2→5的最短路径都经过9-12，把9-12调整为9-5，就能同时缓解两对入口的超限问题，同时不破坏其他入口对的可行性。

模拟面试题：1.4倍约束在模型里应该写成硬约束还是罚函数？答题思路是：最终模型必须满足硬约束，不能拿“总长度短但个别入口对超限”的方案交卷；罚函数可以作为求解过程中的引导，但最后一定要回到可行性检查。面试官追问“如果优化后仍有超限怎么办”，要答“回到边集调整，优先改共享边或增加交叉点，再重新跑Floyd验算”，而不是把约束放宽。这个题考的是建模底线，不是调参技巧。

3. 问题一：给定四个交叉点时如何把 394.5 米算出来

3.1 已知交叉点建模：12个点邻接矩阵与最小生成树

问题一的关键词是“给定交叉点”，所以不要自作主张增加新节点。把P1到P8和A、B、C、D一共12个点编号，P1到P8为1到8，A到D为9到12，然后构造12×12的直线距离矩阵。矩阵里对角线为0，其余为两点欧氏距离。边界道路不计入总长，但在判定入口对能否直接走边界时，仍然用沿边距离表。这个“两套距离”的处理是问题一的第一步，也是很多考生翻车的地方：把边界距离直接塞进12×12矩阵，后面Prim选边就会把免费边界路也算进总长，结果总长度对不上。

构造完邻接矩阵后，用Prim选最小生成树。Prim的输入是12×12距离矩阵，输出是若干条边和总权。代码不需要写得花哨，关键是把“已选集合”“待选边”“父节点”三件事写清楚。下面给一个可复现的Python骨架，矩阵用二维列表或NumPy数组都可以，不可达边用足够大的数表示。

import numpy as np def prim(dist): n = dist.shape[0] used = [False] * n # 节点是否已进入生成树 low = [float("inf")] * n # 当前树到各未选节点的最短边权 parent = [-1] * n # 记录每条树边的父节点 low[0] = 0 edges = [] for _ in range(n): # 选一个未使用且low最小的节点 u = min((i for i in range(n) if not used[i]), key=lambda i: low[i]) used[u] = True if parent[u] != -1: edges.append((parent[u], u, dist[parent[u], u])) # 用u更新其他未选节点的最短连接边 for v in range(n): if not used[v] and dist[u, v] < low[v]: low[v] = dist[u, v] parent[v] = u return edges # dist为12x12直线距离矩阵，不可达位置填inf # 返回edges中每个元素为(起点编号, 终点编号, 边长)

这段代码的逻辑是：从0号节点起步，每次把离当前树最近的未选节点拉进来，同时记录连接边。dist必须是12×12的直线距离矩阵，不能用边界免费距离替代；low保存当前树到每个未选节点的最短边权；parent用于回溯边。运行后得到的边集就是问题一的最小生成树骨架，总权是这些边权之和。注意边权只算内部新修道路，边界道路不进入这个求和。

拿到最小生成树后，不要直接写“总长最小”。还要把树边写成邻接矩阵，再用Floyd算任意两点最短路。因为Prim只保证树的总权最小，不保证树上任意入口对满足1.4倍约束。问题一的最小生成树路径表里会出现若干条连接关系，例如某些入口先连到交叉点，再连到另一个入口；这些路径在树上可能是唯一通路，Floyd算出来的距离就是实际要验算的距离。把Floyd的最短距离矩阵和1.4倍直线距离表并排放，超限对自然就暴露出来。

3.2 真题演练：1→5、2→5超限时怎么局部优化

模拟真题：在问题一的最小生成树中，1→5的最短路径为1-2-10-9-12-5，长度203.2米，超过1.4倍直线距离198.0米；2→5的最短路径为2-10-9-12-5，长度173.2米，超过1.4倍直线距离170.9米。问如何调整道路使两对入口都满足约束，并尽量少增加总长？

答题思路分四步。第一步，先找共享边。两条超限路径都经过9-12，说明9-12是“瓶颈边”，只改一条入口专属边可能顾此失彼。第二步，提出候选调整：把9-12调整为9-5，让1→5和2→5都改走更直接的连接。第三步，重新跑Floyd验算，不仅验1→5和2→5，还要验所有入口对，防止修好一对、弄坏另一对。第四步，算调整后的总道路长，问题一最终得到394.5米。这个结果不是拍脑袋来的，而是“初始MST→Floyd验算→超限表→共享边调整→再验算→总长”的链条产物。

为什么优先改共享边？因为局部优化的目标是“用最少的边改动换最多的约束满足”。如果1→5和2→5各改一条独立边，增加的总长可能更大，还容易引入新的绕行。把9-12改成9-5，相当于把两条超限路径的尾部同时截短，改动集中，解释也干净。答辩时如果被问“为什么不是直接连1-5”，要回答：直接连1-5只解决1→5，2→5仍然可能超限，而且新增一条长边可能让总长增加更多；共享边调整是同时看两对约束的折中。

提示：局部优化不是“哪对超限就连哪对”，而是先看超限路径的共享边，再比较候选调整对总长和其他入口对的影响。

这一题的步骤分很密。模型建立部分要写12个点、两套距离、Prim选边；求解部分要写最小生成树路径表、Floyd最短距离表、超限入口对表；优化部分要写为什么选9-12、改成什么、改完怎么验；结果部分要写394.5米和道路设计图。少任何一环，阅卷人都会觉得结果是“突然出现”的。尤其是超限表，不能只写“经计算不满足”，要列出具体入口对、当前长度、1.4倍阈值，才能支撑后面的局部优化。

3.3 答题模板：从394.5米结果反推步骤分

问题一的答题模板可以按“五段式”组织。第一段写节点与边权：8个入口加4个交叉点，共12个节点，边权为直线距离，边界道路只用于入口对可行性预判。第二段写初始网络：用Prim求最小生成树，给出树边表和总权。第三段写约束验算：用Floyd求任意两点最短路，列出不能直接利用边缘道路的入口对，并标出1→5、2→5超限。第四段写局部优化：指出两条超限路径共享9-12，调整为9-5，重新验算所有入口对。第五段写结果：新修道路总长394.5米，附道路设计图。

这个模板的优点是每一段都对应一个可检查的动作。面试官或阅卷人追问“Prim和Floyd各自起什么作用”，你能立刻指着第二段和第三段回答；追问“为什么改9-12而不是改别的边”，你能指着共享边分析回答；追问“394.5米怎么加出来的”，你能指着树边表逐项求和。很多卷子失分不是算法不会，而是结果和过程脱节：前面写了Prim，后面突然出现一个总长，中间没有Floyd验算和局部优化，阅卷人无法判断这个总长是不是满足约束后的结果。

如果时间紧，至少保留三张表：12点距离表或最小生成树边表、Floyd最短距离与1.4倍阈值对照表、局部优化前后总长对照表。三张表能把“建模—验算—优化”串起来。代码可以放附录，正文用文字说明输入输出。注意代码里的节点编号要和正文表格一致，P1到P8对应1到8，A到D对应9到12，不要正文写A、代码写9，读者对不上。血泪经验是：图、表、代码、结果四处的编号必须统一，否则答辩时自己都说不清哪条边被改了。

4. 问题二：Fermat 点数量比较与 358.4 米的答题链

4.1 先排除可直接走边缘的入口对：不要重复建路

问题二没有给定交叉点，第一步仍然是预处理边界。8个入口之间，有些入口对沿矩形四边的最短距离不超过两点直线距离的1.4倍，这些对可以直接利用边界道路，不需要为了它们新建内部路。原文筛出的不能直接利用边缘道路的入口对包括1→5、1→6、1→8、2→5、2→6、2→7、3→4、3→5、3→6、3→7。这个清单是后续优化的重点，但不是全部入口对；其他入口对也要在最终方案里验算，只是它们不构成“必须新建内部路”的硬需求。

“排除”这个词容易引起误解。它不是把节点从图里删掉，而是把这些入口对标记为“边界可满足”，在构造初始最小生成树时不必为了它们强行加边。比如8→7可以通过边缘道路满足，那么初始树里如果有一条8-7的直线路径，反而可能是多余的，后面可以删掉。问题二原文在局部优化时就出现过“删除8-7直线路径，最短路径经过8-7的符合要求”的处理。答题时要写清楚：边界可满足的对仍然参与最终Floyd验算，只是不进入“必须新建”的集合。

模拟面试题：为什么问题二不能直接沿用问题一的12点图？答题思路：问题一的4个交叉点是题目给定的，问题二没有给定交叉点，如果硬套问题一的A、B、C、D，就把“任意修建”误读成“在给定点上修建”，模型范围错了。正确做法是先只用8个入口建初始图，再用Fermat点或Steiner点增加交叉点，并对不同数量、不同组合做比较。面试官追问“那问题一的结果能不能作为问题二的初始解”，可以答“可以作为对照，但不能作为唯一候选，因为问题二允许新增节点，搜索空间更大”。

问题二的初始最小生成树只连8个入口，总长会比问题一短，但Floyd验算后会发现更多入口对超限。原文表6显示，1→5、2→5、2→6、3→5、3→6、3→7等都需要改进。局部优化尝试过连1-6、2-6、2-5、删8-7、删4-5加3-5等操作，得到427.5米的可行图。这个427.5米很重要，它说明“只靠入口之间的直连和局部改边”还不够短，必须引入交叉点。答题时把427.5米作为引入Fermat点的动机，逻辑就顺了：先得到可行解，再追求更短。

4.2 Fermat点建模：一个、两个、三个交叉点怎么比

Fermat点的定义要答准：在一个三角形中，到三个顶点距离之和最小的点。若三角形三个内角都小于120度，Fermat点在三角形内部，三条连线三等分周角；若有一个内角不小于120度，则钝角顶点就是距离和最小的点。问题二用Fermat点，是因为入口之间直接连或局部改边已经不够短，需要在三角形区域内部放一个交叉点，让三条路以更小的总长连接三个入口。注意Fermat点不是随便取重心，也不是取三条中线的交点，必须按定义建模。

以P2、P3、P5构成的三角形为例，三个内角都小于120度，Fermat点在三角形内部。设Fermat点为Q(x,y)，目标函数是Q到P2、P3、P5的距离之和，约束是Q落在三角形内或边界上。用非线性规划求解，得到Q1后重新连边，总道路长从427.5米降到392.9米。这个下降说明交叉点有效。接着比较两个Fermat点：在P2、P5、P6和P3、P4、P5两个三角形内分别求Q2、Q3，重新组织边集，总长降到358.4米。再比较三个Fermat点同时作为交叉点，总长反而变成416.9米。最终选两个Fermat点的方案，总长358.4米。

这里的高频追问是：为什么三个Fermat点反而更长？答题思路不是“算法算错了”，而是“节点多了，边集组合变了”。每增加一个交叉点，虽然不是入口，但它会引入新的连接边；如果这些新边没有有效替代原来的长边，反而增加了总长。两个Fermat点时，Q2、Q3分别服务两个局部三角形，连接关系紧凑；三个Fermat点时，某些交叉点可能互相争夺连接对象，导致边集变长。数学建模里“增加决策变量”不等于“目标函数一定变优”，还要看组合是否合理。面试官最想听的是“枚举数量并比较总长”，而不是默认越多越好。

from scipy.optimize import minimize def fermat_point(points): # points为三个顶点坐标，例如[(50,0),(160,0),(120,100)] def obj(x): return sum(((x[0]-p[0])**2 + (x[1]-p[1])**2)**0.5 for p in points) # 初值取三个顶点的重心，避免从边界外开始 x0 = [sum(p[0] for p in points)/3, sum(p[1] for p in points)/3] res = minimize(obj, x0=x0, method="Nelder-Mead") return res.x, res.fun

这段代码的目标函数是点到三个顶点距离之和，points是三角形三个顶点，x0取重心作为初值，res.x是Fermat点坐标，res.fun是最小距离和。实际答题时还要加约束，确保点在三角形内部或边界上；如果三角形有内角不小于120度，要直接取钝角顶点，不能硬用内部点。代码只负责求一个三角形的Fermat点，完整方案还要把Q点放回图里重新构造边集、跑Floyd验算、比较总长。参数说明要写清楚：三角形顶点顺序不影响距离和，但初值太偏可能导致局部收敛，重心初值比较稳。

4.3 面试题演练：两个Fermat点最优而三个反而变长

模拟面试题：问题二已经算出两个Fermat点时总长358.4米，三个Fermat点时416.9米，为什么最终不选三个？请从模型和算法两个角度回答。答题思路分四步。第一步，先承认结论来自比较，不是先验判断；一个Fermat点392.9米，两个358.4米，三个416.9米，三个方案都可行，但总长不同。第二步，从模型角度解释：Fermat点优化的是局部三角形内到三个顶点的距离和，增加一个点会改变连接关系，可能让原本紧凑的边集变松。第三步，从算法角度解释：三个点同时放入图后，Prim选出的最小生成树可能不再经过某些有效边，Floyd验算后虽然可行，但总长被拉长。第四步，给出答题落点：最终选两个点，交叉点坐标为Q2、Q3，总长358.4米，并附优化图。

这个题还容易引出另一个追问：Fermat点和Steiner树有什么区别？答题时不要混。Fermat点通常指三角形中到三个顶点距离和最小的点；Steiner树是更一般的网络优化，允许增加非终端节点来缩短连接所有终端的总长。Fermat点可以看作Steiner点在三个终端情形下的一个特例。问题二用Fermat点是因为入口可以组成三角形，问题三有湖障碍后继续用Steiner树方法做网络级优化。把这两个概念分清，答辩时就不会被“你到底用的是Fermat还是Steiner”问住。

注意：Fermat点数量比较时，每个候选方案都要重新构造边集、重新跑Floyd、重新验所有入口对，不能只比较Fermat点本身的距离和。

问题二的答题链可以压缩成一句话：先排除边界可满足的入口对，再用Prim和Floyd得到可行初始图，接着用Fermat点增加交叉点，分别比较一个、两个、三个交叉点的总长，最后选358.4米的两点方案。每个环节都要有表或图支撑。尤其是“一个、两个、三个”的比较表，列清楚交叉点数量、交叉点坐标、总道路长、是否满足1.4倍约束。阅卷人看到这张表，就知道你不是随便选了一个方案，而是做了枚举比较。

5. 失分点：有湖障碍、斯坦纳树与五类常见错误

5.1 湖的矩形约束：能到湖边不等于能穿湖

问题三在问题二基础上加了矩形湖，湖的四个角为R1(140,70)、R2(140,45)、R3(165,45)、R4(165,70)。题目说新修道路不能通过湖，但可以到达湖四周的边。这句话要拆成两层：第一层，湖内部是禁行区，任何穿湖的边都要删除或改道；第二层，湖边不是入口，道路可以接到湖边上，但不能把湖边当成新的“入口”随意连通。问题二的最优图经过湖，所以不能直接把358.4米的方案搬过来，必须做障碍处理。

处理湖的第一步是检查问题二最优图的每条边是否穿湖。穿湖边要删除，然后重新组织连接。原文分了两种情况做优化，分别计算总长，情况一362.8米，情况二397.95米；对情况一再求Fermat点优化，得到360.6米；最后用斯坦纳树方法继续优化，摘要给出的最终最短路径为359.6米，交叉点为h1(68.825,64.7)、h2(112.216,75.34)、h3(161.8,30.7)。这里有一个答辩口径问题：正文中间出现360.6米，摘要最终写359.6米，考生要明确“360.6米是情况一Fermat优化后的中间结果，359.6米是继续用斯坦纳树优化后的最终结果”，不能把两个数混着写。

模拟真题：有湖之后，为什么不能简单把穿湖的边改成沿着湖边绕？答题思路：沿湖边绕只是可行化处理，能保证不穿湖，但不一定总长最短；而且湖边绕行可能让某些入口对的最短路径变长，甚至超过1.4倍约束。正确做法是先删除穿湖边，得到可行候选，再用Fermat点或Steiner点重新优化连接，最后重新跑Floyd验所有入口对。答题时要把“可行”和“最优”分开说，先可行再优化，顺序不能乱。

5.2 斯坦纳树不是万能补丁：先判断原最优图为什么失效

斯坦纳树在这道题里的作用是：允许在图中增加非入口、非给定交叉点的辅助节点，使连接所有入口的总边长更短。问题三有湖障碍，问题二的最优图穿湖失效，于是先做情况分类和Fermat点优化，再上斯坦纳树方法继续压缩总长。注意斯坦纳树不是“随便加几个点就能变短”，它需要满足连接性、避障和1.4倍约束。加点的位置、数量、连接对象都要通过建模和比较确定，不能拍脑袋。

面试官可能追问：Fermat点和斯坦纳树在问题三怎么配合？答题思路：Fermat点负责局部三角形内的连接优化，适合在已经确定的三角形区域里找更优交叉点；斯坦纳树负责网络级优化，允许增加辅助节点并重新组织边集。问题三先处理湖障碍，把穿湖边改掉，得到可行图；再用Fermat点优化局部连接；最后用斯坦纳树做全局比较。三者是递进关系，不是互相替代。回答时要把“局部优化”和“全局优化”分开，避免把所有方法都说成“求最短路”。

提示：斯坦纳树的解不一定包含所有原始候选边，它可能删除旧边、增加新辅助点；每次改动后都要重新验算1.4倍约束和避障条件。

问题三的另一个失分点是湖的边界处理。湖的四个角坐标要准确写入模型，穿湖判定可以用线段与矩形相交判断，也可以把湖看成一个禁行矩形，边集里删除与矩形内部相交的线段。道路可以到达湖边，意味着可以把湖边上的点作为连接点，但不能穿过湖内部。答题时如果只写“避开湖”三个字，没有给出湖的坐标、穿湖判定和改道方案，步骤分会被扣掉。血泪经验是：障碍题一定要把“禁行区域”写成数学条件，不能只画示意图。

5.3 易错清单：五类错误逐条纠偏

第一类错误：把边界免费路算进总长。错在把矩形四边的已建道路也计入新修道路总长度；为什么错，因为题目明确边界道路不计入总长，算进去会让结果偏大，也会让Prim选边失真；怎么答对，分开两套距离，边界距离只用于入口对可行性预判，总长只累加内部新修边。

第二类错误：先用Floyd再用Prim。错在把Floyd当成选边算法；为什么错，Floyd需要一张已经确定的图，不能在“还没决定建哪些边”时给出道路设计；怎么答对，先Prim选最小生成树骨架，再Floyd算树上任意两点最短路，最后按1.4倍约束做局部优化。

第三类错误：只验相邻入口或只验超限清单。错在把“不能直接利用边缘道路的入口对”当成全部验算对象；为什么错，题目要求任意两个入口之间都满足1.4倍约束，未列入清单的入口对也可能因为局部改边而超限；怎么答对，最终方案必须对28对入口全部验算，超限清单只是重点排查对象。

第四类错误：默认Fermat点越多越好。错在不比较一个、两个、三个Fermat点的总长；为什么错，增加交叉点会改变边集组合，三个点时总长可能反而变长；怎么答对，枚举不同数量、不同组合，分别构造边集、跑Floyd、验约束，用总长和可行性共同决策。

第五类错误：湖障碍只删边不重算。错在把穿湖边删掉后就宣布完成；为什么错，删边会改变连通性和最短路，可能让其他入口对超限，也可能留下不连通的分量；怎么答对，删边后重新构造可行图，必要时用Fermat点或斯坦纳树优化，再重新验所有入口对和避障条件。问题三还要注意结果口径，360.6米是中间优化值，359.6米是最终摘要值，答辩时先说明口径再报数。

6. 答题技巧：从算法名到阅卷步骤的押题清单

6.1 把“算法名”翻译成阅卷人想看的动作

公园道路设计题的押题方向很集中：节点与边权建模、Prim选边、Floyd验约束、局部优化、Fermat点数量比较、湖障碍处理、斯坦纳树收尾。答题时不要只写“用了Prim算法”“用了Floyd算法”，要写成动作链：先构造12点或8点距离矩阵，再用Prim得到最小生成树边表，再用Floyd得到任意两点最短距离表，再拿1.4倍阈值逐对比较，再对超限对找共享边做局部优化，最后报总长和设计图。阅卷人看的是这条链是否闭合，不是算法名字是否响亮。

这张表可以直接当答辩前的自检清单。每一行都对应一个可能被追问的点，答不上来就回到正文补表。尤其是“结果口径”这一行，问题三的数字最容易翻车：摘要最终写359.6米，正文中间有360.6米，答辩时要主动说明“这是继续优化前后的两个阶段”，而不是等面试官质疑数据矛盾。

6.2 押题思路：三道题其实是一条链

问题一考“给定交叉点怎么接”，问题二考“交叉点数量怎么选”，问题三考“有障碍怎么改”。三问共用同一套底层动作：节点表、边权表、Prim、Floyd、1.4倍验算、局部优化。把这条链背熟，换一个公园形状或入口坐标也能迁移。押题时优先练三个动作：一是从坐标表构造距离矩阵，二是把Floyd超限表做出来，三是针对共享边提出局部优化方案。Fermat点和斯坦纳树是加分项，但前提是前面的约束验算不能错。

我后来带模拟答辩时，每次都在纸上强制走一遍“节点表—边权表—MST—Floyd—超限表—局部优化—结果口径”七步，哪怕时间紧也不跳步。这份资料把三问的模型、代码骨架、结果对照表和答辩追问整理成一册，需要对着练的读者可在文末按说明获取。希望帮到你。

本文还有配套的精品资源，点击获取