简介围绕公园内道路优化设计的这份数学建模论文面向参加数学建模竞赛、学习图论与几何优化的学生及指导教师聚焦在任意两个入口最短路径不超过直线距离1.4倍的约束下使新建道路总长度最短。论文按三问展开给定交叉点时用Prim算法求最小生成树以Floyd算法核验最短路并做局部优化交叉点可任意选取时引入Fermat点组合寻优园内有矩形湖时结合障碍约束用Fermat点与斯坦纳树重新配置交叉点并给出各问道路总长及交叉点坐标。资源包仅含1个doc文件约495KB集中呈现模型假设、符号说明、问题分析、数据表与求解过程便于按赛题脉络复盘算法选型与建模写作。已有330人学习可用于练习最短路径建模、掌握Prim、Floyd与Fermat点的组合使用并借鉴结果表达与图表组织。1. 这类题到底考什么一道公园道路设计题考的是你会不会把“1.4 倍”变成矩阵很多人拿到公园道路设计这道题第一反应是画图、连直线、目测哪条路短。真到赛场上这么干基本就翻车了——评分看的不是你画得像不像而是你有没有把“任意两个入口最短路径不大于两点直线距离 1.4 倍”这句人话翻译成一张能跑的邻接矩阵和一套校验流程。这道题属于数学建模里典型的图论加几何优化复合题先用最小生成树把点连起来再用 Floyd 校验任意两点最短路超标的做局部优化最后用 Fermat 点或斯坦纳树把总长压下去。它考三件事模型假设敢不敢下、算法链条闭不闭环、结果能不能自证满足约束。适合正在准备竞赛建模、图论优化方向面试或者要复现这类论文的人。2. 考点拆解从“1.4 倍约束”到最小生成树的建模骨架2.1 先把约束翻译成可计算的不等式这道题最容易让人误判的地方是把“任意两个入口之间的最短道路长不大于两点连线的 1.4 倍”理解成“每条新建道路不能超过直线距离的 1.4 倍”。前者是全局约束后者是局部约束一旦搞混后面所有优化都白做。正确的写法是设入口点集合为 P你设计的道路网络为图 Gd_G(i,j) 表示在这个网络里从入口 i 到入口 j 的最短路长度欧氏直线距离记作 L(i,j)那么约束就是对所有 i、j 都有 d_G(i,j) ≤ 1.4 × L(i,j)。目标函数则是所有内部新建道路的长度之和最小边界上已有的道路不计入总长。把这个不等式写出来只是第一步真正要落到代码里得先准备两张距离表。一张是 8 个入口加若干交叉点的两两欧氏距离另一张是入口点沿公园四条边绕行的距离。后者用来判断哪些入口对可以完全靠边界道路满足 1.4 倍要求从而不必在内部为它们修路。原文第一问里1→5、1→6、1→8、2→5、2→6、2→7、3→4、3→5、3→6、3→7 这十对点就是“不能直接利用边缘道路”的集合后面的最小生成树和校验都围绕它们展开。提示判断某对入口能否只走边界时比较的是“沿边界最短距离”和“1.4 倍直线距离”不是“直线距离”和“1.4 倍直线距离”。这一步用几行代码就能算清别在论文里靠文字描述糊过去。import math # 8 个入口坐标顺序按题目给的是 P1 到 P8 P [(20,0), (50,0), (160,0), (200,50), (120,100), (35,100), (10,100), (0,25)] def euclid(a, b): return math.hypot(a[0]-b[0], a[1]-b[1]) # 沿矩形边界的绕行距离矩形 200 x 100入口都在边上 # 简化处理按入口在边界上的顺序排成一圈算两种绕行取小 def boundary_dist(i, j): # 这里只给判定思路把 8 个点按边界顺序参数化后取环上较短弧 # 实际实现时按 P1-P2-P3-P4-P5-P6-P7-P8 的边界顺序累加 order [0,1,2,3,4,5,6,7] pos {p:k for k,p in enumerate(order)} a, b pos[i], pos[j] # 省略逐段边长累加核心是环上两条弧取 min return None # 判定沿边界距离 1.4 * 直线距离则这对点可不建内部路 for i in range(8): for j in range(i1, 8): L euclid(P[i], P[j]) # 用实际边界距离替换 None 后比较 print(i1, j1, round(L, 1), round(1.4*L, 1))上面这段代码的重点不是直接跑出结果而是把“直线距离”和“1.4 倍阈值”先摆到同一张表里。参数怎么改入口坐标换了就改 P矩形尺寸换了边界绕行距离的累加逻辑要跟着改1.4 这个系数是题目给的硬约束不要自己改成 1.3 或 1.5 去凑结果。跑完这张表你会得到一份“哪些点对必须靠内部道路解决”的清单这份清单就是后面 Prim 和 Floyd 的输入边界。2.2 边缘道路不计入总长这一步决定了模型自由度题目里有一句很关键的话可以利用公园四周的边即默认矩形四条边上存在已经建好的道路此道路不计入道路总长。这句话在模型里等价于边界道路是成本为 0 的边但它仍然存在于图中可以参与最短路计算。很多考生在这里踩坑要么把边界长度加进目标函数导致总长虚高、优化方向跑偏要么干脆把边界当成不存在可行域被自己砍掉一大块最后找不到满足 1.4 倍约束的解。正确的处理方式是把边分成三类。第一类是边界边成本为 0可以走但不能穿过公园内部第二类是内部新建边成本等于两点欧氏距离是你要求最小化的对象第三类是有湖情况下的湖边界题目说新修道路不能通过湖但可以到达湖四周的边所以湖的四条边也要作为可走边处理成本同样不计入内部新建总长。把这三类边分清楚目标函数才不会写错。边的类型是否计入总长能否参与最短路典型错误公园四周边界否是把边长加进目标函数内部新建道路是是漏掉某些交叉点之间的边湖的四条边否是直接把湖当成删除区域导致不连通这张表建议直接放进论文的模型假设后面评委会一眼看出你知道自己在算什么。参数上唯一需要小心的是湖的坐标R1(140,70)、R2(140,45)、R3(165,45)、R4(165,70)这四点围成的矩形内部禁止穿越但四条边可以走。如果你把湖处理成“删掉所有经过湖的边”而不补充沿湖边的绕行路径第三问很可能直接无解。2.3 Prim 只解决“连通且总长最小”不解决 1.4 倍这是整道题最容易被面试官追问的一句你用了 Prim那 Prim 到底保证了什么标准答法是Prim 在给定点集和边权下求出一棵连接所有点的最小生成树保证总边权最小但它不保证树上任意两点之间的路径满足 1.4 倍约束。换句话说Prim 给你的是一个“便宜但可能绕远”的初解真正的约束校验必须交给 Floyd 或 Dijkstra 做全点对最短路。所以答题链条应该是先建图跑 Prim 得到最小生成树边集再把树边作为图的新边集跑 Floyd 得到任意两点最短路最后拿这个最短路去和 1.4 倍直线距离逐对比较超标的点对记录下来进入局部优化。这个顺序不能反先 Floyd 后 Prim 在逻辑上说不通因为 Floyd 需要一张已经确定的图。import math, heapq def prim(points): n len(points) # 邻接矩阵欧氏距离点集包含入口和交叉点 g [[math.hypot(points[i][0]-points[j][0], points[i][1]-points[j][1]) for j in range(n)] for i in range(n)] used [False] * n low [float(inf)] * n parent [-1] * n low[0] 0 edges [] for _ in range(n): u min((i for i in range(n) if not used[i]), keylambda i: low[i]) used[u] True if parent[u] ! -1: edges.append((parent[u], u, g[parent[u]][u])) for v in range(n): if not used[v] and g[u][v] low[v]: low[v] g[u][v] parent[v] u return edges # 返回的是最小生成树的边集每条边带权 # 参数说明points 顺序决定输出下标别把入口和交叉点混排后忘记映射这段 Prim 的时间复杂度是 O(n²)对 12 个点、8 个点这种规模完全够用。关键注释在 parent 数组上它记录每个点是从哪个点连进来的最终 edges 里存的是树边。跑完之后不要急着画图先把 edges 转成邻接矩阵再喂给 Floyd。这里有个血泪经验如果你在 Prim 里直接把不存在的边设成 0Floyd 会把 0 当成真实距离最后校验全过论文看起来漂亮实际模型是错的。不存在的边必须设成无穷大。注意Prim 的输出是一棵树树里任意两点只有唯一路径。Floyd 在这棵树上跑出来的最短路就是这条唯一路径的长度。所以校验时不需要再考虑其他绕行方式除非你在局部优化里新增了边。面试里还常问一句为什么不用 Dijkstra 代替 Floyd答题思路是Dijkstra 单源跑 8 个入口需要 8 次代码量更大Floyd 三重循环一次出全点对矩阵适合这种点少、需要反复校验的场景。复杂度 O(n³) 在 n12 时完全可以接受工程上没必要为了省一点时间把代码写复杂。3. 高频考点Prim、Floyd 与 1.4 倍校验的三件套怎么答3.1 Prim 的答题模板从邻接矩阵到最小生成树边集考场上写 Prim别一上来就贴代码先把四句话说清楚点集是什么、边权怎么定义、起点怎么选、终止条件是什么。以第一问为例点集是 8 个入口加 A、B、C、D 共 12 个点边权是两点欧氏距离起点可以选 P1也可以选任意点最小生成树总长不变终止条件是所有点都被加入树。把这四句写在论文里评委就知道你不是背代码而是真懂算法。代码层面Prim 的核心是维护一个 low 数组表示未访问点到当前树的最短距离以及一个 parent 数组记录这个最短距离是从哪个树内点来的。每轮选 low 最小的未访问点加入树然后用它更新其他未访问点的 low。这个描述听起来简单但考场上最容易错的是初始化low 全部设成无穷大只有起点设成 0parent 全部设成 -1。如果你把 low 初始化成 0第一轮所有点都会被选进来树直接退化。第二问里点集变成 8 个入口没有给定交叉点Prim 跑出来的最小生成树总长会比第一问小但校验会发现更多点对超标。原文表 6 里 1→5、2→5、2→6、3→5、3→6、3→7 都需要改进原因就是没有交叉点帮忙分担路径。答题时要敢于下判断不是 Prim 算错了而是问题本身需要引入新的交叉点这正是 Fermat 点上场的理由。3.2 Floyd 求任意两点最短路校验矩阵怎么用Floyd 的三重循环几乎是图论题的标准动作但很多人只背了代码没想清楚初始化。dist 矩阵一开始要填成直接距离有边就填边权没边就填无穷大自己到自己填 0。然后三层循环最外层是中间点 k内两层是起点 i 和终点 j状态转移是 dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])。循环顺序不能乱k 必须放最外层否则会出现“用还没算好的中间点去更新”的逻辑错误。校验的时候拿 dist[i][j] 和 1.4 × L(i,j) 逐对比较。这里有个细节L(i,j) 是原始欧氏直线距离不是边界绕行距离也不是树上的距离。原文第一问表 4 里1→5 的最短路径长度是 203.2 米直线距离的 1.4 倍是 198.0 米超标 5.2 米2→5 是 173.2 米对 170.9 米超标 2.3 米。这两个数一摆出来局部优化的必要性就不用多解释了。def floyd(n, edges): INF float(inf) dist [[INF]*n for _ in range(n)] for i in range(n): dist[i][i] 0 for u, v, w in edges: dist[u][v] min(dist[u][v], w) dist[v][u] min(dist[v][u], w) for k in range(n): for i in range(n): for j in range(n): if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] return dist # edges 来自 Prim 的输出也可以手动加入局部优化新增的边 # 校验时用 dist[i][j] 与 1.4 * euclid(i, j) 比较这段代码的返回值是一个完整的最短路矩阵后面所有校验都查这张表。参数怎么改如果你在局部优化里把 9-12 改成 9-5就要把新边加进 edges 再跑一遍 Floyd不能只改一条边就宣布结果。很多论文在这里翻车改了边却不重新校验评委一查就发现其他点对超标了。3.3 真题演练4 个交叉点、12 个点的第一问怎么落到 394.5 米第一问的完整答题思路可以拆成五步。第一步算 12 个点的两两欧氏距离得到邻接矩阵同时算 8 个入口沿边界的绕行距离筛出不能直接走边界的十对点。第二步对 12 个点跑 Prim得到最小生成树原文表 3 给出的树边包括 2-8、10-9、6-7、12-5、11-3、4-11、12-10、9-6、9-12 等。第三步把树边喂给 Floyd算出任意两点最短路重点检查那十对不能走边界的点。第四步发现 1→5 和 2→5 超标分析这两条路径都经过 9-12于是把 9-12 调整为 9-5让 1→5 和 2→5 绕开原来的长路径。第五步重新跑 Floyd 校验所有点对确认全部满足后计算内部新建道路总长得到 394.5 米。这里最值得学的是第四步的“看共同边”。1→5 的路径是 1-2-10-9-12-52→5 的路径是 2-10-9-12-5两条超标路径共享 9-12 这一段所以改一条边就能同时解决两个问题。答题时要把这个分析写出来而不是直接说“我试了试把 9-12 改成 9-5 就好了”。面试官最想听的是你怎么定位到 9-12 的答案是看超标路径的交集交集边就是杠杆点。第五步的复核也不能省。改边之后原本达标的点对可能因为新边变短而更优但也可能因为路径结构变化出现新的超标。正确的做法是把新边加入图重新跑一次 Floyd输出完整的校验表。论文里最好放一张“点对、最短路长度、1.4 倍阈值、是否达标”的四列表评委扫一眼就能确认你的结果自洽。4. 高频考点Fermat 点与局部优化第二问的加分点4.1 Fermat 点的两种情形小于 120 度与不小于 120 度第二问没有给定交叉点原文的处理是先跑 Prim 加 Floyd 得到一版可行解再引入 Fermat 点压缩总长。Fermat 点的定义是三角形内到三个顶点距离之和最小的点。它有两种情形必须分开答。第一种三角形三个内角都小于 120 度Fermat 点在三角形内部且到三个顶点的连线两两夹角都是 120 度第二种三角形有一个内角大于等于 120 度这个钝角的顶点就是 Fermat 点不需要再往内部找。这个判定条件不是摆设。原文选的是 P2、P3、P5 构成的三角形三个角都没超过 120 度所以 Fermat 点在内部可以用非线性规划求。如果你不分情况对一个钝角三角形硬求内部点算出来的结果不会比钝角顶点更优论文里就会出现“优化后反而变长”的尴尬。答题时先把内角算出来再决定用哪种情形这一步花不了几分钟但能挡住很多质疑。提示Fermat 点优化的是“一个三角形内到三顶点距离和”它不直接保证全局 1.4 倍约束。每引入一个 Fermat 点都要把它当作新的交叉点加入图重新跑 Floyd 校验不能只算局部距离和。4.2 非线性规划模型怎么写目标函数与约束Fermat 点的求解可以写成一个无约束或有约束的非线性规划。目标函数是 f(x,y) √((x-x1)²(y-y1)²) √((x-x2)²(y-y2)²) √((x-x3)²(y-y3)²)约束是点 (x,y) 落在三角形内部。如果三角形三个角都小于 120 度也可以不加约束直接求无约束极小但加一个三角形内部的线性约束更稳妥能防止数值求解跑到三角形外面去。from scipy.optimize import minimize import numpy as np def fermat(p1, p2, p3): def obj(x): return (np.hypot(x[0]-p1[0], x[1]-p1[1]) np.hypot(x[0]-p2[0], x[1]-p2[1]) np.hypot(x[0]-p3[0], x[1]-p3[1])) # 初值取三个顶点的重心避免落到边界外 x0 [(p1[0]p2[0]p3[0])/3, (p1[1]p2[1]p3[1])/3] res minimize(obj, x0, methodNelder-Mead) return res.x, res.fun # 参数说明p1、p2、p3 是三个入口或交叉点的坐标 # 返回值和目标函数值都要记录目标函数值就是该三角形内的最小距离和这段代码用 Nelder-Mead 做无约束极小适合考场快速出结果。参数怎么改三角形顶点换位置就改 p1、p2、p3如果要用有约束版本可以把三角形三条边的半平面不等式写成 constraints 传给 minimize。结果出来后把 Fermat 点坐标记下来作为新的交叉点加入点集再跑 Prim 或直接连边最后一定要用 Floyd 复核全局最短路。4.3 真题演练1 个、2 个、3 个 Fermat 点的组合比较原文第二问做了一个很典型的对比实验只引入 1 个 Fermat 点时总长 392.9 米引入 2 个 Fermat 点时总长 358.4 米把 3 个 Fermat 点同时作为交叉点时总长反而变成 416.9 米。这个结果说明一个容易被忽视的考点Fermat 点不是越多越好。每加一个点图的边集和路径结构都会变原来达标的点对可能因为新路径绕远而超标局部最优的组合不一定等于全局最优。答题时要把这个对比写成“枚举加校验”的过程而不是“我选了 2 个点所以最好”。具体思路是先列出可能构成三角形的入口组合比如 P2、P3、P5 一组P2、P5、P6 和 P3、P4、P5 各一组对每种组合求 Fermat 点把点加入图跑 Floyd记录总长和是否全部满足 1.4 倍约束最后在所有可行方案里取总长最小的。原文最终选的两个交叉点总长 358.4 米就是在这个枚举过程中胜出的。第三问加了矩形湖之后第二问的最优路径会穿过湖不能直接照搬。原文的处理是分两种情况调整路径分别求 Fermat 点比较后得到 362.8 米和 397.95 米再对较优的情况继续用斯坦纳树优化最终交叉点落在 h1(68.825,64.7)、h2(112.216,75.34)、h3(161.8,30.7)总长 359.6 米。这里的答题关键是有障碍物时先把障碍物的边界纳入可走边再在剩余可行域里找 Fermat 点或斯坦纳点不能把湖当成简单的“删边”。5. 易错点四个最容易丢分的坑5.1 错在把 1.4 倍当成每条边的约束这是最常见的审题错误。题目说的是“任意两个入口之间的最短道路长不大于两点连线的 1.4 倍”约束对象是入口对之间的最短路不是每一条新建道路。错在只检查每条边是否小于 1.4 倍直线距离为什么错一条边可以很短但绕几段之后两点之间的最短路可能远超阈值怎么答对用 Floyd 做全点对最短路校验逐对比较不要逐边比较。5.2 错在把边界道路的长度算进总长题目明确说公园四周已经建好的道路不计入道路总长但很多考生在写目标函数时习惯性地把图中所有边都加起来。错在目标函数多加了边界边为什么错这会让优化器倾向于少用边界而边界恰恰是零成本资源应该大胆用怎么答对目标函数只累加内部新建边的欧氏长度边界边和湖边在成本里记 0但在最短路计算里正常参与。5.3 错在 Fermat 点无脑加忽略内角条件Fermat 点只对三角形有意义而且要先判断三个内角是否都小于 120 度。错在不看内角直接求内部点为什么错钝角三角形的 Fermat 点就是钝角顶点硬求内部点会得到一个更差的距离和怎么答对先算三个内角分两种情形处理求完点后加入图重新跑 Floyd确认全局约束仍然满足。5.4 错在有湖时直接删边不重建可行域第三问的湖是矩形障碍新修道路不能穿过但可以到达湖四周的边。错在把所有经过湖的边一删了之为什么错删边之后图可能不连通或者剩余路径的最短路超标问题直接无解怎么答对把湖的四条边作为可走边加入图禁止穿越湖内部然后在这个新图上重新找交叉点和最短路原文就是靠这个思路把总长压到 359.6 米。5.5 错在只报结果不报校验论文最后只写“最短道路总长为 394.5 米”却没有给校验表评委无法判断你的解是否满足 1.4 倍约束。错在把计算结果当成最终答案为什么错这道题的评分点有一半在约束满足性上怎么答对每个问题最后都附一张校验表列出超标点对、最短路长度、阈值和是否达标改边之后重新校验一遍再定稿。6. 答题技巧一套能复现的六步流程与时间分配真到考场上这道题最容易乱的是顺序有人先画图有人先写目标函数有人上来就调 Fermat 点。我后来固定成六步每次按顺序走基本不会漏。第一步读题抽约束把 1.4 倍、边界不计长度、湖不能穿越这三句话分别翻译成数学表达式第二步建图确定点集、边集和每类边的成本第三步跑 Prim 得到初解记录树边第四步跑 Floyd 做全点对校验输出超标清单第五步针对超标点对做局部优化或引入 Fermat 点每改一次就重新校验第六步整理结果画道路设计图附校验表。步骤产出检查项抽约束不等式组、边界条件1.4 倍是否作用在最短路建图点集、边集、成本表边界边成本是否为 0Prim最小生成树边集不存在的边是否设为无穷大Floyd全点对最短路矩阵k 是否在最外层局部优化新增边或 Fermat 点改边后是否重新校验出结果道路图、总长、校验表所有入口对是否达标时间分配上建模和写目标函数占四成编程和调参占三成画图和写校验表占三成。别把时间全砸在求 Fermat 点上第二问的 358.4 米是靠“枚举组合加校验”得到的不是靠一个点算出来的。第三问有湖时先处理可行域再谈优化顺序反了会多做很多无用功。从那以后我每次碰到带“任意两点最短路不超过某倍数”的题都强制先跑一遍全点对校验表再谈优化。这张表看起来笨但它能挡住绝大多数翻车。希望帮到你。本文还有配套的精品资源点击获取