简介：《公园内道路设计问题》是一篇面向数学建模竞赛参赛者与图论应用学习者的论文，围绕矩形公园内道路最短化设计展开，要求在任意两入口间最短路径不超过直线距离1.4倍的前提下，使新建道路总长最小。资源包内仅含1个doc文档，约495KB，即论文全文，涵盖摘要、问题重述、模型假设、符号说明、问题分析与求解过程，并附Prim算法、Floyd算法程序与结果图表。目前已有330人学习下载。论文按三个问题层层递进：给定交叉点时，用Prim构建最小生成树、Floyd求最短路径并做局部优化，得总长394.5米；交叉点可任意选取时，借助Fermat点组合寻优，缩短至358.4米；引入矩形湖后，结合斯坦纳树处理障碍区域，给出交叉点坐标与359.6米的结果。读者可据此掌握从模型假设、邻接矩阵构造到算法实现与结果校验的完整流程，也可作为同类最短路径与网络优化赛题的参考模板。
1. 公园道路设计问题的方案边界：8 个入口、1.4 倍约束与不计入总长的四边
公园内道路设计问题在数学建模里看起来像一道最短路题，真正落到图纸上却要同时回答三件事：新修道路总长最短、任意两个入口之间的最短路径不超过两点直线距离的 1.4 倍、四边已建道路不计入总长且新修道路只能接 8 个入口。这三个条件互相牵制，只盯着最小生成树会把方案做“短”，却不一定做“通”。
这套方案适合正在做数学建模课设、毕设或竞赛题的人：题目给了 200 米 × 100 米的矩形公园和 8 个入口坐标，问题一固定 4 个交叉点，问题二允许自由选交叉点，问题三加入矩形湖障碍。下面按“需求边界—固定点建模—自由点优化—障碍绕行—避坑—验收”的顺序，把 Prim、Floyd、Fermat 点和 Steiner 树的落地细节拆开讲。
2. 问题一建模与实现：固定 4 个交叉点下的 Prim 最小生成树与 Floyd 校核
2.1 把 12 个点放进同一张距离表：邻接矩阵怎么建
问题一先不要急着写算法，先把点编号固定下来。8 个入口按题目顺序记为 P1 到 P8，4 个给定交叉点 A、B、C、D 顺延为 9、10、11、12。这个编号一旦定下，后面所有矩阵、边集、局部优化都按它走，否则很容易出现“代码里索引 9 是 A，论文里 9 是 B”的翻车。
| 编号 | 点名 | 坐标 | 类型 |
|---|---|---|---|
| 1 | P1 | (20,0) | 入口 |
| 2 | P2 | (50,0) | 入口 |
| 3 | P3 | (160,0) | 入口 |
| 4 | P4 | (200,50) | 入口 |
| 5 | P5 | (120,100) | 入口 |
| 6 | P6 | (35,100) | 入口 |
| 7 | P7 | (10,100) | 入口 |
| 8 | P8 | (0,25) | 入口 |
| 9 | A | (50,75) | 给定交叉点 |
| 10 | B | (40,40) | 给定交叉点 |
| 11 | C | (120,40) | 给定交叉点 |
| 12 | D | (115,70) | 给定交叉点 |
建矩阵时我一般会建两层：第一层是“可新修道路候选图”，12 个点两两相连，边权取欧氏距离，用来跑 Prim；第二层是“通行校核图”，在第一层基础上把四边已经建好的入口间道路补进去，边权取沿边缘的实际距离，用来跑 Floyd。两层不能混成一个矩阵，因为四边道路不计入总长，但在校核 1.4 倍时它是可走的。把不计权重的边直接塞进 Prim，目标函数就变了。
import math import numpy as np points = { 1: (20, 0), 2: (50, 0), 3: (160, 0), 4: (200, 50), 5: (120, 100), 6: (35, 100), 7: (10, 100), 8: (0, 25), 9: (50, 75), 10: (40, 40), 11: (120, 40), 12: (115, 70) } name = {1:"P1",2:"P2",3:"P3",4:"P4",5:"P5",6:"P6",7:"P7",8:"P8", 9:"A",10:"B",11:"C",12:"D"} n = len(points) D = np.zeros((n, n)) for i in range(1, n + 1): for j in range(1, n + 1): xi, yi = points[i] xj, yj = points[j] D[i-1, j-1] = math.hypot(xi - xj, yi - yj) # 四边已建道路不计总长，但在校核图中要补边 # 这里只补相邻入口沿边距离，实际脚本可按矩形四条边逐段累加 edge_pairs = [(1,2,30),(2,3,110),(3,4,64),(4,5,94.34), (5,6,85),(6,7,25),(7,8,75.74),(8,1,32)] print(D[0, 4]) # P1 到 P5 直线距离，用于对照表这段代码只做一件事：把坐标变成距离矩阵。参数points是全部节点坐标，D是 12 × 12 对称矩阵，edge_pairs是四边相邻入口的沿边距离。跑完先核对几个关键值，比如 P1 到 P5 的直线距离约 141.4 米，P1 到 P5 的 1.4 倍就是 198.0 米。这个数后面会反复出现，如果这里算错，后面违规清单全是假的。
2.2 Prim 求最小生成树：边集、编号与路径回溯
Prim 的作用是在 12 点完全图上找一棵总边权最小的树。它只保证“总长最小”，不保证任意两个入口之间的路径不超过 1.4 倍直线距离，所以它只是第一步。实现时用一个visited数组和一个min_edge数组，每次从已选集合向外挑最短边，记录父节点，最后回溯出边集。
def prim(dist, start=0): n = len(dist) visited = [False] * n min_w = [float("inf")] * n parent = [-1] * n min_w[start] = 0 edges = [] for _ in range(n): u = min((i for i in range(n) if not visited[i]), key=lambda i: min_w[i]) visited[u] = True if parent[u] != -1: edges.append((parent[u] + 1, u + 1, dist[parent[u]][u])) for v in range(n): if not visited[v] and dist[u][v] < min_w[v]: min_w[v] = dist[u][v] parent[v] = u return edges mst_edges = prim(D, start=0) for u, v, w in mst_edges: print(f"{name[u]}-{name[v]} {w:.2f}")dist必须是候选图距离矩阵，start可以任选，Prim 结果不随起点改变总权。跑完后不要只看总长，要把边集打印成人能读的P2-B、A-D这种形式，逐条对照论文里的表。问题一原解的最小生成树边集里出现了 9-12 这类交叉点之间的边，也出现了入口之间的边。这里有一个常见误用：有人把四边道路直接以 0 权重塞进 Prim，结果生成树大量走边缘，内部道路看起来很短，但 1.4 倍校核时又忘了边缘道路的实际长度，最后总长和路径对不上。正确做法是 Prim 只用内部候选边，四边道路留到 Floyd 校核图里。
2.3 Floyd 校核 1.4 倍阈值：从距离矩阵到违规清单
得到最小生成树后，把它转成邻接矩阵：有边的位置填欧氏距离，没有边填无穷大；再把四边已建道路按沿边距离补进去。Floyd 三重循环求所有点对最短路，重点看 8 个入口之间的 28 对距离。对每一对入口，拿最短路和1.4 × 直线距离比较，超过的进违规清单。
def floyd(dist): n = len(dist) f = dist.copy() for k in range(n): for i in range(n): for j in range(n): if f[i][j] > f[i][k] + f[k][j]: f[i][j] = f[i][k] + f[k][j] return f # 由 MST 边集构建校核图，再把四边道路补进去 F = np.full((n, n), np.inf) for i in range(n): F[i][i] = 0 for u, v, w in mst_edges: F[u-1, v-1] = F[v-1, u-1] = w for u, v, w in edge_pairs: F[u-1, v-1] = min(F[u-1, v-1], w) F[v-1, u-1] = min(F[v-1, u-1], w) short = floyd(F) for i in range(1, 9): for j in range(i + 1, 9): direct = D[i-1, j-1] if short[i-1, j-1] > 1.4 * direct + 1e-6: print(f"违规 {name[i]}->{name[j]}: {short[i-1,j-1]:.2f} > {1.4*direct:.2f}")问题一原解跑出来的违规对集中在 1→5 和 2→5：1→5 最短路径 203.2 米，而 1.4 倍直线距离是 198.0 米；2→5 最短路径 173.2 米，阈值 170.9 米。其他不能直接借边缘的入口对，比如 1→6、1→8、2→6、2→7、3→4、3→5、3→6、3→7，在最小生成树加边缘道路的图上已经合规。这里的关键不是“MST 一定违规”，而是“MST 之后必须校核”，校核图必须包含边缘道路，比较时必须用 1.4 倍直线距离而不是 1.4 倍路径距离。
提示：浮点比较不要写死
>，加一个1e-6容差。像 170.9 和 170.9000001 这种差异，在论文里看不出，在代码里会多报一条违规。
2.4 局部优化 9-12 改 9-5：一次改边如何消掉两条违规
两条违规路径都经过 9-12，也就是 A 到 D 这条边。原解的处理很干脆：把 9-12 改成 9-5，也就是让 A 直接连到 P5。这样 1→5 的路径变成 1-2-10-9-5，2→5 的路径变成 2-10-9-5，两条都压到阈值以下，同时其他入口对的路径没有被破坏。改完后内部道路总长为 394.5 米。
这个局部优化看起来是“拍脑袋”，其实有判断依据：违规对共享同一条边，说明这条边是瓶颈；把瓶颈边替换成通向违规终点的边，能同时缩短两条路径。落地时不要只改一条边就收工，改完要重新跑一遍 Floyd，把所有入口对重新校核，并重新计算总长。参数上，9-12对应A-D，9-5对应A-P5，如果编号表换了，这两个名字必须跟着换。常见误用是直接在距离矩阵里把D[8,11]改成无穷大，再补D[8,4]，却忘了同步边集和论文图，最后图、表、代码三套数据对不上。
问题一的结果 394.5 米不是“最小生成树总长”，而是“最小生成树 + 局部优化 + 边缘道路校核”之后的内部道路总长。写论文时要把这个区别写清楚，否则答辩时被问“为什么你的 MST 总长和最终总长不一样”会很难接。
3. 问题二自由交叉点优化：Fermat 点枚举与两交叉点组合的取舍
3.1 先排除可直接借边缘的入口对
问题二没有给定交叉点，先把“能直接借边缘道路”的入口对排掉。做法和问题一一样：用 Floyd 在只含边缘道路的图上算入口间最短距离，和 1.4 倍直线距离比较。能借边缘且合规的对，不进入内部道路优化；不能借边缘或借了也超阈值的对，才是候选约束。
问题二原解先对 8 个入口跑 Prim，得到最小生成树，再用 Floyd 校核。表里不能直接通过边缘的入口对中，1→6 的最短路径 132.7 米小于阈值 141.6 米，已经合规；真正需要改的是 1→5、2→5、2→6、3→5、3→6、3→7。原解先做局部优化：连 1-6 能让 1→5 合规，但 2→5 会变成 226.1 米，超过 170.9 米，所以不连 1-6；改连 2-6 后 2→5 仍然 186.1 米，超过阈值，所以还要连 2-5；删除 8-7 的直线路径，因为 8→7 可以走边缘；删除 4-5，加 3-5，让 3→6 和 3→7 通过 3-5-6 合规。这样局部优化后的内部道路总长是 427.5 米。
这一段最容易翻车的地方是“局部优化”没有统一规则，看到哪条违规就补哪条，最后补出一堆边。我的习惯是每改一次都记录三件事：改了哪条边、影响了哪些入口对、总长变化多少。427.5 米是一个中间结果，不是最终答案，它的价值是给 Fermat 点优化提供一个可行起点。
3.2 在三角形里找 Fermat 点：角度条件与非线性规划
Fermat 点的定义是：在一个三角形中，到三个顶点距离之和最小的点。若三角形三个内角都小于 120°，Fermat 点在三角形内部，且到三个顶点的连线两两夹角 120°；若有一个内角不小于 120°，那个钝角顶点就是 Fermat 点。问题二里，P2、P3、P5 构成的三角形三个角都小于 120°，所以可以用非线性规划求内部点。
目标函数是f(x,y)=sum(sqrt((x-xi)^2+(y-yi)^2))，约束是点落在三角形内部。实现时用scipy.optimize.minimize，初始点取三角形重心，约束写成三条边的半平面，或者用bounds加惩罚项。求出一个 Fermat 点 Q1 后，把它加入候选点集，重新跑 Prim 和 Floyd，总长从 427.5 米降到 392.9 米。
from scipy.optimize import minimize def fermat_point(tri): (x1,y1),(x2,y2),(x3,y3) = tri def obj(p): x, y = p return sum(math.hypot(x - xi, y - yi) for xi, yi in tri) # 初始点用重心，避免落在边界上 x0 = [(x1+x2+x3)/3, (y1+y2+y3)/3] # 用三条边所在直线的半平面做约束，实际脚本可用 SLSQP + 约束函数 cons = [] for (xa,ya),(xb,yb),(xc,yc) in [ ((x1,y1),(x2,y2),(x3,y3)), ((x2,y2),(x3,y3),(x1,y1)), ((x3,y3),(x1,y1),(x2,y2)) ]: # 叉积符号约束，保证点在三角形同一侧 def make_cons(xa,ya,xb,yb,xc,yc): return lambda p: (xb-xa)*(p[1]-ya) - (yb-ya)*(p[0]-xa) * \ ((xb-xa)*(yc-ya) - (yb-ya)*(xc-xa)) cons.append({"type":"ineq", "fun":make_cons(xa,ya,xb,yb,xc,yc)}) res = minimize(obj, x0, method="SLSQP", constraints=cons, options={"ftol":1e-10, "maxiter":1000}) return res.x, res.funtri是三个顶点坐标，obj是距离和，x0是重心，cons是半平面约束。跑完先检查res.success，再看三个角是否都小于 120°；如果某个角不小于 120°，不要硬跑非线性规划，直接把钝角顶点作为 Fermat 点。常见误用是只写目标函数不写约束，求出来的点跑到三角形外面，总长看着更短，但路径结构已经不成立。还有人把 Fermat 点当成“全局最优点”，实际上它只负责一个三角形内的三顶点连接，最终还要放回整张图里做 MST 和 Floyd 校核。
3.3 一个点、两个点、三个点的组合比较
求出 Q1 后，原解继续试两个 Fermat 点：三角形 P2P5P6 和 P3P4P5 分别求 Q2、Q3，把两个点同时加入候选集，重新跑 Prim 和 Floyd，总长降到 358.4 米。接着再试三个 Fermat 点同时作为交叉点，总长反而变成 416.9 米。这个结果看起来反直觉，但原因不复杂：Fermat 点只保证它所在三角形的三个顶点距离和最小，三个点同时接入时，MST 可能多出长边，或者原本可以由一个点服务的区域被拆成两个点，连接结构变复杂，总长就上去了。
组合比较的落地方式是枚举：候选点集 = 8 个入口 + 选中的 Fermat 点；对每个组合求 MST，计内部边总长，再用 Floyd 校核所有入口对；校核不通过就标记为不可行，通过才参与比较。参数上，组合数不要一上来就全枚举，先做“0 个点、1 个点、2 个点、3 个点”的粗筛，再在最优组合附近做局部搜索。问题二原解的比较结果如下：
| 方案 | 交叉点数量 | 内部道路总长 | 是否满足 1.4 倍 |
|---|---|---|---|
| 局部优化后 | 0 个 Fermat 点 | 427.5 米 | 满足 |
| 一个 Fermat 点 | Q1 | 392.9 米 | 满足 |
| 两个 Fermat 点 | Q2、Q3 | 358.4 米 | 满足 |
| 三个 Fermat 点 | Q1、Q2、Q3 | 416.9 米 | 满足 |
两个 Fermat 点的 358.4 米是问题二的最优结果。写论文时要把“为什么三个点反而更长”解释清楚，不要只贴一张图。答辩时老师很可能追问这一点，提前准备好“Fermat 点是局部三角形最优，不是全局组合最优”的说法，比临场解释稳得多。
3.4 为什么两个 Fermat 点得到 358.4 米
两个 Fermat 点分别服务两组三角形：P2P5P6 和 P3P4P5。它们把原来局部优化图里的长边拆成两段，让 P2、P3、P4、P5、P6 之间的连接更紧凑，同时没有引入三个点时那种多余连接。358.4 米是内部道路总长，不是入口间最短路总长；校核时仍然要把边缘道路加进去，逐对检查 28 个入口对。
落地复现时，两个 Fermat 点的坐标以脚本输出为准，不要手抄论文里缺失的坐标。原题解答中问题二的两个交叉点坐标没有在正文里完整给出，只给了总长 358.4 米；复现时应该把 Q2、Q3 的求解过程、初始点、约束、收敛状态都记录下来。如果换一组初始点得到不同坐标但总长接近，要检查是不是落到了三角形边界；如果总长明显变大，先查 Fermat 点是否在三角形内部，再查 MST 是否把该点连到了不合适的入口。
4. 问题三带障碍湖的道路规划：绕湖重构与 Steiner 树近似
4.1 湖的矩形边界与不可穿越约束
问题三在公园内加了一个矩形湖，四个角点为 R1(140,70)、R2(140,45)、R3(165,45)、R4(165,70)。新修道路不能穿过湖内部，但可以到达湖四周的边。问题二的最优图有一条路径经过湖，所以不能直接沿用 358.4 米的方案，必须把穿湖的边替换成绕湖的边。
这里的第一件事不是改算法，而是写相交检测。每条候选边都要判断是否穿过湖的内部；如果只是擦到湖角或沿湖边，可以保留，但要明确端点。实现时可以用几何库，也可以自己写线段与矩形内部相交判断。核心是：线段与矩形四条边求交，如果交点在矩形内部且不在端点，就判为穿湖；如果线段完全在矩形外，或者只接触边界，则不穿湖。
def seg_rect_cross(p, q, rect): # rect = (xmin, ymin, xmax, ymax) xmin, ymin, xmax, ymax = rect # 快速排除：两端都在矩形同一侧 if max(p[0], q[0]) < xmin or min(p[0], q[0]) > xmax: return False if max(p[1], q[1]) < ymin or min(p[1], q[1]) > ymax: return False # 用参数化线段与四条边求交，交点在内部则穿湖 # 实际脚本建议用 shapely 的 LineString.crosses(box) 做初筛 # 再用交点参数 t 判断是否落在 0<t<1 return True # 这里只示意接口，完整实现要补四条边求交p、q是线段端点，rect是湖的外接矩形(140,45,165,70)。这个函数只做初筛，完整实现要把四条边分别求交，并排除端点接触。常见误用是只判断端点是否在湖内，结果一条边从湖中间穿过去但两个端点都在湖外，检测不出来。另一种误用是把湖当成“删掉一条边”处理，删完图不连通，最后只能硬补长边，总长反而变大。
4.2 情况一与情况二：把最优图拆成可绕行子图
问题二的最优图穿湖后，原解拆成两种情况。情况一是把穿湖路径改从湖的一侧绕，计算总长 362.8 米；情况二是从另一侧绕，总长 397.95 米。两种情况都满足不穿湖，但情况一更短，所以选情况一继续优化。这个“先拆两种情况，再比较”的做法很实用：湖的绕行方向通常只有上方、下方、左侧、右侧几种，不需要一上来就做复杂的全局搜索。
情况一确定后，把 P3、P4、R4 组成三角形，求 Fermat 点 Q4，优化后路径长 360.6 米。这里 R4 是湖的角点 (165,70)，把湖角点作为可通行节点是合理的，因为题目允许道路到达湖四周的边。求 Q4 时仍然要先判断三角形三个角是否都小于 120°；如果某个角不小于 120°，直接取钝角顶点，不要硬套内部点公式。
4.3 从 Fermat 点到 Steiner 点：h1、h2、h3 的落地
情况一用 Fermat 点优化到 360.6 米后，原解继续用 Steiner 树方法优化，最终交叉点为 h1(68.825,64.7)、h2(112.216,75.34)、h3(161.8,30.7)，最短路径 359.6 米。Steiner 树和 Fermat 点的区别在于：Fermat 点只针对一个三角形的三个顶点，Steiner 树允许在全局增加若干辅助点，使连接所有终端的树总长更小。对三个终端，Steiner 点就是 Fermat 点；对更多终端，候选 Steiner 点通常由三三组合的 Fermat 点构成，再放回候选点集里做 MST 和校核。
落地时我一般会这样组织候选点：8 个入口、湖的四个角点、问题二得到的 Fermat 点、三三组合求出的 Fermat 点、少量沿湖边的候选点。候选点不是越多越好，点太多组合爆炸，而且容易把一些“看起来短但穿湖”的边带进来。每加入一个候选点，都要重新跑 MST、重新做穿湖检测、重新做 1.4 倍校核，三个检查都过了才计入总长比较。
h1、h2、h3 的位置也说明了绕湖策略：h1 在湖左侧，h2 在湖左上，h3 在湖下方，三个点把原本穿湖的连接拆成绕湖的分段连接。最终 359.6 米比问题二的 358.4 米多 1.2 米，这个增量就是绕湖的代价，数值上合理。写论文时不要把它写成“比问题二更优”，而应该写成“在湖障碍约束下重新优化后的结果”。
4.4 359.6 米结果怎么复核
复核分四步。第一步，用 h1、h2、h3 和 8 个入口重新构建内部边集，逐条检查是否穿湖；第二步，把四边已建道路补进校核图，跑 Floyd，检查 28 个入口对是否都不超过 1.4 倍直线距离；第三步，只对内部边求和，边缘道路权重记为 0，得到 359.6 米；第四步，把最终图、交叉点坐标、边集表、Floyd 违规清单放在一起对照，确认没有“图上有边、表里没数”的情况。
| 检查项 | 期望结果 | 检查方法 |
|---|---|---|
| 内部道路总长 | 359.6 米 | 只对入口-交叉点、交叉点-交叉点、入口-入口内部边求和 |
| 穿湖检测 | 无内部边穿过湖内部 | 每条边与矩形湖做线段相交判断 |
| 1.4 倍约束 | 28 个入口对全部合规 | Floyd 最短路径与 1.4 倍直线距离逐对比较 |
| 交叉点坐标 | h1、h2、h3 与图一致 | 脚本输出坐标与论文标注逐点核对 |
| 边缘道路 | 不计入总长但参与校核 | 目标矩阵与校核矩阵分开维护 |
注意：湖的四个角点坐标顺序要和矩形边界一致，R1(140,70)、R2(140,45)、R3(165,45)、R4(165,70) 围成的矩形是 x 从 140 到 165、y 从 45 到 70。顺序写错会让相交检测把湖判成另一个形状，后面所有绕行边都白算。
5. 道路方案避坑与排查：距离表、1.4 倍阈值和坐标精度最容易翻车的地方
5.1 只算内部边，忘了边缘道路要参与校核
现象：Floyd 校核时大量入口对违规，但图上看内部道路已经连得很密。原因：校核图只放了最小生成树的边，没有把四边已建道路补进去，导致本来可以走边缘的入口对被判成绕远。解决：目标矩阵和校核矩阵分开建，目标矩阵只含内部候选边，校核矩阵在目标矩阵基础上补边缘道路，边权用沿边实际距离。每次改边后两张图同步更新，不要用一张矩阵既算总长又做校核。
5.2 编号错位：A/B/C/D 和 9/10/11/12 对不上
现象：局部优化把 9-12 改成 9-5，总长变了，但违规清单没消掉。原因：代码里索引从 0 开始，论文里编号从 1 开始，D[8,11]和D[9,12]差一位；或者 A、B、C、D 的顺延顺序和坐标表不一致。解决：用字典按名字取坐标，所有边集打印时同时输出编号和点名，比如(9,12) A-D；局部优化前后各打印一次边集，确认改的是同一条边。
5.3 把最小生成树直接当最终路网
现象：MST 总长很短，但一校核就有入口对超过 1.4 倍。原因：MST 只最小化总边权，不约束任意两点路径；入口对之间的最短路可能绕很远。解决：MST 之后必须跑 Floyd，违规对进入局部优化或加入 Fermat 点；优化后再跑 Floyd，直到所有入口对合规。问题一的 394.5 米和问题二的 358.4 米都是“MST + 校核 + 优化”的结果，不是单次 MST 的结果。
5.4 Fermat 点角度条件被忽略
现象：非线性规划求出的点落在三角形外，或者总长比顶点直接连接还大。原因：三角形有内角不小于 120° 时，Fermat 点就是钝角顶点，不是内部等角点；硬跑内部点模型会得到错误解。解决：先算三个角，有角 ≥120° 直接取该顶点；三个角都小于 120° 再用 SLSQP 加半平面约束，初始点取重心，检查res.success和点是否在三角形内。
5.5 湖障碍用“删边”代替“绕行”
现象：删掉穿湖边后图不连通，或者补了一条更长的边，总长反而超过问题二。原因：湖不是简单删一条边，而是要把穿湖连接拆成沿湖的分段连接；湖角点可以作为可通行节点，但边不能穿过湖内部。解决：先做线段与矩形湖的相交检测，把穿湖边替换成经过湖角点或候选 Steiner 点的边；每改一次都检查连通性、穿湖和 1.4 倍约束。问题三最终 359.6 米只比问题二多 1.2 米，说明绕行方案是可控的；如果复现结果远大于 359.6，优先查相交检测和候选点集。
6. 从图纸到答辩：怎么验收 394.5/358.4/359.6 米这套方案
验收这套方案，我一般不看图漂不漂亮，只看三张表能不能对上。第一张是入口对校核表，28 个入口对逐对列出最短路径、1.4 倍阈值、是否合规；第二张是边集表，列出每条内部边的两个端点、长度、是否穿湖；第三张是结果对照表，问题一 394.5 米、问题二 358.4 米、问题三 359.6 米，分别对应哪组交叉点、哪张图。三张表能互相追溯，答辩时就不怕追问。
| 验收项 | 问题一 | 问题二 | 问题三 |
|---|---|---|---|
| 内部道路总长 | 394.5 米 | 358.4 米 | 359.6 米 |
| 交叉点 | A、B、C、D 固定 | 两个 Fermat 点 | h1、h2、h3 |
| 1.4 倍校核 | 28 对全部合规 | 28 对全部合规 | 28 对全部合规 |
| 障碍约束 | 无湖 | 无湖 | 无内部边穿湖 |
| 边缘道路 | 不计总长，参与校核 | 同左 | 同左 |
答辩时最容易被追问的四个点：为什么边缘道路不计总长还要参与校核；为什么问题二两个 Fermat 点比三个点更短；问题三 359.6 米比 358.4 米大是否合理；Steiner 树怎么保证不穿湖。前两个用“目标函数和约束分离”“Fermat 点是局部三角形最优”解释；第三个用“绕湖代价 1.2 米”解释；第四个直接打开相交检测代码和最终边集表，逐条指给老师看。
我早期做这类题时，总喜欢先画图再补表，结果图上的边和表里的距离对不上，答辩前一夜还在改坐标。从那以后我每次收尾都强制走一遍“边集表—Floyd 校核表—总长汇总表”的对账，哪怕图已经很好看了也不跳过。这套论文的完整图表、距离表和可运行脚本我整理在资源包里，需要按原题复现时直接对照取用。希望帮到你。
本文还有配套的精品资源，点击获取
