1. 问题拆解从“切割路径”到“图论与优化”的转化每年五一数学建模竞赛的A题往往是一个经典的运筹优化问题今年这个“钢板最优切割路径问题”也不例外。乍一看题目很多同学可能会被“切割路径”这个词带偏联想到数控机床的G代码或者图像处理里的轮廓追踪。但如果你有建模经验或者仔细分析过历年赛题就会立刻意识到这本质上是一个图论上的最短路径问题或者更具体地说是中国邮递员问题或旅行商问题在特定约束下的变种。我们面对的是一块钢板上面有若干个需要切割的图形可能是圆形、矩形或者不规则多边形。切割机从起点出发需要切割完所有图形的轮廓最后回到终点可能与起点相同。切割机在钢板上空走不切割的速度和切割时的速度是不同的空走快切割慢。我们的目标是找到一条总耗时最短的路径。这里的关键在于“切割”这个动作是强制的、不可跳过的你必须完整地走完每个图形的轮廓而“空走”则是连接各个图形轮廓的、可以自由优化的部分。所以整个问题就变成了如何以最优的顺序访问切割所有这些“强制边集”图形轮廓并在它们之间用“非强制边”空走路径连接起来。这立刻让我们联想到两个经典模型如果要求每条边轮廓必须走且只走一次那就是一笔画问题对应图论中的欧拉路径或欧拉回路。但现实中大多数图形轮廓自己就能构成一个封闭的欧拉回路因为是一个封闭图形所以核心矛盾在于连接各个图形的空走路径。这更接近于中国邮递员问题邮递员需要走过每条街切割每条边但可以重复走某些路空走重复目标是总路程最短。不过本题中“切割边”和“空走边”的成本不同这增加了问题的维度。另一种视角是将每个图形的整个轮廓视为一个必须访问的“点”问题就转化为在这些“点”之间寻找最优访问顺序这又有点像旅行商问题。实际上这是一个广义旅行商问题其中每个“城市”不是一个点而是一组边图形的轮廓访问一个“城市”意味着遍历该组的所有边。因此解题的第一步也是最关键的一步是完成问题的抽象转化顶点定义将每个需要切割的独立图形视为一个“超级顶点”或“簇”。每个簇内部包含一系列连续的边轮廓。边与权重定义簇内边即图形轮廓本身。遍历这些边的成本是“切割速度”乘以轮廓长度。簇间边连接两个不同图形轮廓上任意两点的线段。行走这些边的成本是“空走速度”乘以该线段长度。这里就产生了第一个优化点两个图形之间的最优空走连接是它们轮廓之间的最短距离点对点距离。目标寻找一条从起点S出发经过所有“簇”即切割所有图形最终到达终点T的路径使得总成本总时间最小。这条路径由两部分成本组成所有簇内轮廓的固定切割成本之和加上连接这些簇的所有簇间空走成本之和。这样一来一个看似复杂的工程问题就被清晰地映射为了一个组合优化问题。后续的所有建模、算法设计和编程都将围绕这个核心定义展开。2. 模型构建混合整数规划与图论模型的双视角基于上一节的转化我们可以从两个主流方向来构建数学模型精确的混合整数规划和基于图论的启发式算法框架。对于数学建模竞赛而言两者结合阐述会显得思路更加完整。2.1 混合整数规划模型MIP模型适合问题规模不大、追求最优解的情况。我们可以这样定义集合与参数V: 所有“簇”的集合索引为i, j。特别地S和T分别代表起点和终点所在的簇可能是虚拟簇。c_i: 访问簇i的固定成本即切割其整个轮廓所需的时间轮廓总长度 / 切割速度。d_ij: 从簇i到簇j的最短空走距离。这需要预先计算即两个多边形轮廓之间的最短欧几里得距离。这是一个子问题可以通过计算两个多边形上所有顶点对之间的距离并检查线段是否与多边形内部相交若相交则非空走可行路径来求解。t_ij: 从簇i空走到簇j所需的时间t_ij d_ij / 空走速度。K: 一个足够大的正数Big-M。决策变量x_ij: 0-1变量若路径中从簇i直接前往簇j进行空走则为1否则为0。u_i: 辅助连续变量用于消除子回路MTZ约束。目标函数 最小化总时间 所有簇的固定切割成本之和 所有被选中的簇间空走时间之和。Minimize Z Σ_i c_i Σ_i Σ_j (t_ij * x_ij)注意这里假设每个簇必须被访问一次且仅一次所以固定成本c_i是常数项。优化变量主要体现在x_ij上。约束条件每个簇离开一次起点S除外Σ_j x_ij 1, 对于所有i ∈ V \ {T}。每个簇到达一次终点T除外Σ_i x_ij 1, 对于所有j ∈ V \ {S}。起点流出和终点流入Σ_j x_Sj 1,Σ_i x_iT 1。消除子回路约束u_i - u_j K * x_ij K - 1, 对于所有i, j ∈ V \ {S}, i ≠ j。这是保证路径连通的经典约束。变量域x_ij ∈ {0, 1},u_i 0。这个模型直接描述了问题但它的规模会随着图形数量簇的数量呈平方增长且预计算d_ij和t_ij矩阵本身就是一个几何计算问题。对于图形较多、形状复杂的情况直接求解MIP可能非常耗时甚至不可行。这就引出了第二种思路。2.2 基于图论的启发式算法框架对于规模较大的问题我们通常采用启发式算法。核心思想是分两步走第一步距离矩阵与图构建计算所有簇两两之间的最短空走距离d_ij形成距离矩阵D。这是本问题的几何计算核心。构建一个完全图G其中节点就是各个簇边的权重为t_ij空走时间。第二步路径搜索此时问题转化为在一个完全图上寻找一条从起点S出发访问所有节点簇一次最后到达终点T的哈密顿路径使得路径权重和最小。这就是经典的定向旅行商问题。精确方法对于小规模n 20可以用动态规划状态压缩DP即 Held-Karp 算法。启发式方法对于中大规模必须采用启发式算法。构造型算法最近邻算法、插入算法最远插入、最小插入、Christofides算法针对对称TSP的近似算法。改进型算法2-opt、3-opt、Lin-Kernighan等局部搜索算法用于对初始解进行优化。元启发式算法遗传算法、模拟退火、蚁群算法。这些是数学建模竞赛中的“常客”因为它们框架通用易于结合问题特性进行改进。在实际编程求解时我们通常采用“启发式构造 局部搜索优化”的策略。例如先用最近邻法生成一个初始路径然后用2-opt算法反复迭代优化交换路径中的边直到目标函数无法改进为止。3. 核心子问题图形间最短空走距离的计算无论采用上述哪种模型一个无法回避的、且计算量巨大的子问题就是计算两个多边形切割图形之间的最短距离d_ij。这不仅仅是两个点集之间的最近点对距离因为空走路径不能穿过任何图形的内部否则会误切割。因此d_ij定义为从多边形A的边界上任一点到多边形B的边界上任一点的线段长度的最小值且该线段不与任何其他多边形的内部相交。这是一个计算几何问题。精确求解非常复杂。在竞赛有限时间内我们通常采用合理简化简化1顶点近似。假设空走路径的端点只可能位于多边形的顶点上。这样d_ij就近似为两个多边形顶点集合之间的最短距离。计算量从无穷点对降到有限点对m*n其中m和n分别是两个多边形的顶点数。简化2可见性判断。即使找到了两个顶点之间的最短线段仍需判断这条线段是否“干净”——即是否穿过了其他图形的内部。这需要做线段与多边形相交检测。如果线段与任何非自身的多边形内部相交则这条路径不可行。简化3进一步降维。当图形数量很多时对每一对图形都做全顶点对检查和全局相交检测计算量是O(k^2 * m^2 * n)k为图形数m为平均顶点数n为图形数用于相交检测难以承受。此时可以引入空间索引进行加速如包围盒过滤先计算每个多边形的最小外接矩形。如果两个多边形的外接矩形不相交且距离很远可以快速估算一个距离下限甚至直接跳过精细计算。最近点对算法对于两个点集用分治法等算法快速找到几何最近点对作为候选然后再进行可见性判断。在编程实现时一个稳健的策略是首先为每个多边形计算其顶点列表和外接矩形。当计算d_ij时先计算两个多边形外接矩形之间的最短距离作为一个快速估计值。然后遍历多边形A的每个顶点和多边形B的每个顶点计算顶点距离。对于当前最短的顶点对进行线段相交检测。如果该线段是“干净”的则将其距离作为d_ij。如果被阻挡则将此顶点对标记为不可行继续检查次短的顶点对直到找到一条“干净”的线段或遍历完所有候选。如果所有顶点对之间的线段都被阻挡在图形非常密集时可能发生那么最短空走路径可能不是直线而是需要绕过其他图形。这时问题就升级为平面上的避障最短路径问题复杂度激增。在竞赛中如果出现这种情况通常题目数据会避免或者你需要说明这一复杂性并采用更高级的路径规划算法如A*算法在顶点图上搜索但这会大大增加实现难度。4. 算法实现与代码框架这里我们以一个中等规模的问题为例给出一个结合了启发式TSP求解和简化距离计算的Python代码框架。我们假设图形是多边形数据以顶点列表形式给出。import numpy as np import math from itertools import permutations, combinations import matplotlib.pyplot as plt # 第一部分几何计算工具函数 def distance_point_to_segment(p, a, b): 计算点p到线段ab的最短距离。 ap p - a ab b - a t np.dot(ap, ab) / np.dot(ab, ab) t max(0, min(1, t)) projection a t * ab return np.linalg.norm(p - projection) def segments_intersect(p1, p2, p3, p4): 判断线段p1p2和p3p4是否相交不包括端点触碰。 def cross(v1, v2): return v1[0]*v2[1] - v1[1]*v2[0] v1 p2 - p1 v2 p3 - p1 v3 p4 - p1 c1 cross(v1, v2) c2 cross(v1, v3) if c1 * c2 0: return False v4 p4 - p3 v5 p1 - p3 v6 p2 - p3 c3 cross(v4, v5) c4 cross(v4, v6) if c3 * c4 0: return False # 排除共线且重叠的情况本题简单处理为不相交 if c1 0 and c2 0 and c3 0 and c4 0: return False return True def polygon_centroid(vertices): 计算多边形质心用于图形简化表示。 x [v[0] for v in vertices] y [v[1] for v in vertices] area 0.0 cx 0.0 cy 0.0 n len(vertices) for i in range(n): j (i 1) % n cross_product x[i]*y[j] - x[j]*y[i] area cross_product cx (x[i] x[j]) * cross_product cy (y[i] y[j]) * cross_product area * 0.5 if area 0: return np.array([np.mean(x), np.mean(y)]) cx / (6*area) cy / (6*area) return np.array([cx, cy]) def polygon_bbox(vertices): 返回多边形的外接矩形 (x_min, y_min, x_max, y_max)。 x [v[0] for v in vertices] y [v[1] for v in vertices] return (min(x), min(y), max(x), max(y)) def bbox_distance(bbox1, bbox2): 计算两个外接矩形之间的最短曼哈顿距离用于快速过滤。 x1_min, y1_min, x1_max, y1_max bbox1 x2_min, y2_min, x2_max, y2_max bbox2 dx max(0, x1_min - x2_max, x2_min - x1_max) dy max(0, y1_min - y2_max, y2_min - y1_max) return math.sqrt(dx*dx dy*dy) # 欧氏距离近似 # 第二部分问题数据与预处理 class CuttingShape: def __init__(self, id, vertices): self.id id self.vertices np.array(vertices) # N x 2 self.centroid polygon_centroid(vertices) self.bbox polygon_bbox(vertices) # 计算轮廓周长固定切割成本 self.perimeter 0.0 n len(vertices) for i in range(n): j (i 1) % n self.perimeter np.linalg.norm(self.vertices[j] - self.vertices[i]) self.cutting_time self.perimeter / cutting_speed # 参数设定示例 cutting_speed 1.0 # 切割速度 (单位/分钟) travel_speed 3.0 # 空走速度 (单位/分钟) start_point np.array([0, 0]) end_point np.array([10, 10]) # 假设这是输入的图形数据每个图形是一个顶点列表 shapes_data [ [(1, 1), (1, 3), (3, 3), (3, 1)], # 矩形 [(5, 5), (6, 7), (7, 5)], # 三角形 [(8, 2), (9, 4), (7, 4)], # 另一个三角形 ] shapes [CuttingShape(i, verts) for i, verts in enumerate(shapes_data)] num_shapes len(shapes) # 第三部分计算图形间最短可行空走距离 def compute_shortest_travel_distance(shape_a, shape_b, all_shapes): 计算从shape_a到shape_b的最短可行空走距离。 简化只考虑顶点到顶点的连线并进行相交检测。 min_dist float(inf) best_pair (None, None) # 快速过滤如果外接矩形距离很远直接返回质心距离近似 bbox_dist bbox_distance(shape_a.bbox, shape_b.bbox) if bbox_dist 50: # 阈值可根据问题尺度调整 return np.linalg.norm(shape_a.centroid - shape_b.centroid) # 遍历所有顶点对 for va in shape_a.vertices: for vb in shape_b.vertices: dist np.linalg.norm(vb - va) if dist min_dist: continue # 剪枝 # 检查线段va-vb是否与任何其他图形内部相交 feasible True for s in all_shapes: if s.id shape_a.id or s.id shape_b.id: continue # 检查线段与多边形s的每条边是否相交 verts_s s.vertices n_s len(verts_s) for k in range(n_s): p1 verts_s[k] p2 verts_s[(k 1) % n_s] if segments_intersect(va, vb, p1, p2): feasible False break if not feasible: break if feasible and dist min_dist: min_dist dist best_pair (va, vb) # 如果没找到任何可行顶点对退回使用质心距离这是一种妥协实际可能需路径规划 if min_dist float(inf): min_dist np.linalg.norm(shape_a.centroid - shape_b.centroid) # print(fWarning: No direct feasible path between {shape_a.id} and {shape_b.id}. Using centroid distance.) return min_dist # 预计算距离矩阵 print(Precomputing travel distance matrix...) travel_dist_matrix np.zeros((num_shapes, num_shapes)) for i in range(num_shapes): for j in range(i1, num_shapes): d compute_shortest_travel_distance(shapes[i], shapes[j], shapes) travel_dist_matrix[i, j] d travel_dist_matrix[j, i] d travel_time_matrix travel_dist_matrix / travel_speed # 第四部分TSP路径求解启发式最近邻 2-opt def total_path_time(path, travel_time_mat, shapes): 计算给定路径的总时间固定切割时间 空走时间。 total_travel 0.0 for k in range(len(path)-1): i path[k] j path[k1] total_travel travel_time_mat[i, j] total_cut sum(s.cutting_time for s in shapes) # 固定成本 return total_cut total_travel def nearest_neighbor_path(start_idx, travel_time_mat): 最近邻算法构造初始路径。 n travel_time_mat.shape[0] unvisited set(range(n)) unvisited.remove(start_idx) path [start_idx] current start_idx while unvisited: # 找到未访问节点中距离当前节点最近的 nearest min(unvisited, keylambda city: travel_time_mat[current, city]) path.append(nearest) unvisited.remove(nearest) current nearest return path def two_opt_swap(path, i, k): 执行2-opt交换反转路径中i到k的部分。 new_path path[:i] path[i:k1][::-1] path[k1:] return new_path def two_opt(path, travel_time_mat, shapes, max_iterations1000): 2-opt局部搜索优化。 n len(path) best_path path[:] best_time total_path_time(best_path, travel_time_mat, shapes) improved True iteration 0 while improved and iteration max_iterations: improved False for i in range(1, n-2): for k in range(i1, n-1): new_path two_opt_swap(best_path, i, k) new_time total_path_time(new_path, travel_time_mat, shapes) if new_time best_time: best_path new_path best_time new_time improved True break # 找到改进就跳出内层循环重新扫描 if improved: break iteration 1 return best_path, best_time # 假设起点和终点都是第一个图形根据题目要求调整 start_shape_idx 0 end_shape_idx 0 # 假设回到起点 # 构造初始路径最近邻 initial_path nearest_neighbor_path(start_shape_idx, travel_time_matrix) # 确保终点是要求的终点这里简单处理复杂情况需调整 if initial_path[-1] ! end_shape_idx: # 如果终点不对可以将其移到末尾但这可能破坏优化。更严谨的做法是将终点约束融入算法。 pass print(fInitial path (NN): {initial_path}) initial_time total_path_time(initial_path, travel_time_matrix, shapes) print(fInitial total time: {initial_time:.2f}) # 2-opt优化 optimized_path, optimized_time two_opt(initial_path, travel_time_matrix, shapes) print(fOptimized path (2-opt): {optimized_path}) print(fOptimized total time: {optimized_time:.2f}) print(fImprovement: {initial_time - optimized_time:.2f}) # 第五部分结果可视化可选 def plot_solution(shapes, path): plt.figure(figsize(10, 8)) # 绘制所有图形 colors [r, g, b, c, m, y] for idx, shape in enumerate(shapes): verts shape.vertices verts_closed np.vstack([verts, verts[0]]) # 闭合多边形 plt.plot(verts_closed[:, 0], verts_closed[:, 1], colorcolors[idx % len(colors)], linewidth2, labelfShape {shape.id}) plt.fill(verts_closed[:, 0], verts_closed[:, 1], colorcolors[idx % len(colors)], alpha0.1) # 绘制空走路径 for k in range(len(path)-1): i path[k] j path[k1] # 这里简单用质心连线表示空走路径实际应根据compute_shortest_travel_distance找到的最佳点对绘制 plt.plot([shapes[i].centroid[0], shapes[j].centroid[0]], [shapes[i].centroid[1], shapes[j].centroid[1]], k--, linewidth1, alpha0.7) # 标记起点终点 plt.scatter(shapes[path[0]].centroid[0], shapes[path[0]].centroid[1], s200, cgold, edgecolorsblack, marker*, labelStart/End) plt.xlabel(X) plt.ylabel(Y) plt.title(Optimal Cutting Path (Travel Routes Shown)) plt.legend() plt.grid(True, alpha0.3) plt.axis(equal) plt.show() plot_solution(shapes, optimized_path)这段代码提供了一个完整的求解框架但请注意它包含了许多简化距离计算简化compute_shortest_travel_distance函数只检查了顶点到顶点的连线且相交检测只针对其他图形的边。如果最短路径需要经过图形内部的点对于凹多边形或者需要绕过图形顶点连线全部被挡此函数会失效退回使用质心距离。在正式比赛中你需要评估题目数据是否可能导致这种情况并决定是否实现更复杂的可见性图或A*搜索。TSP求解简化使用了最简单的最近邻构造和2-opt优化。对于图形数量较多50的情况可能需要更强大的启发式算法如模拟退火、遗传算法来获得更好的解。起点终点处理代码中假设起点和终点是同一个图形索引0。实际问题中起点和终点可能是钢板上的特定点你需要将其视为虚拟的“簇”其固定切割成本为0但需要计算它到其他所有图形的距离。5. 模型评估、优化与论文写作要点得到一个解和代码只是第一步。在数学建模论文中你需要系统地展示你的工作。模型评估准确性你的距离计算模型在什么假设下成立顶点近似、直线空走。如果数据违反假设误差有多大可以进行敏感性分析例如在多边形边上采样更多点来计算距离与顶点近似法对比。算法性能你的启发式算法得到的解距离最优解可能有多远对于小规模问题n10可以用暴力枚举所有排列来获取精确最优解以此评估启发式算法的精度。对于大规模问题可以计算解的目标函数值与理论下界如最小生成树权值的两倍的差距。复杂度分析你的算法时间复杂度是多少距离计算是O(k^2 * m^2 * n)TSP启发式是O(k^2 * I)I是2-opt迭代次数。这决定了你的方法能处理多大规模的问题。模型优化方向距离计算优化实现基于扫描线或空间划分如四叉树、R树的加速算法快速过滤不可能相交的图形对。TSP求解优化初始解改进使用最小生成树MST生成TSP路径或者使用Christofides算法获得有理论保证的近似解。局部搜索增强实现3-opt、Lin-Kernighan等更强大的局部搜索算子。元启发式应用实现模拟退火算法。其核心在于以当前路径为初始解随机进行2-opt或3-opt交换产生新解以概率exp(-ΔT / temp)接受劣解并逐渐降低温度temp。代码框架比遗传算法更简单且效果通常不错。集成起点终点将起点和终点作为特殊节点加入TSP问题并妥善处理例如起点必须为路径第一项终点必须为最后一项。论文写作要点问题重述与分析清晰地将切割路径问题转化为图论问题这是体现建模思维的关键。模型假设明确列出你的假设如“空走路径为直线”、“空走路径端点仅考虑图形顶点”、“空走路径不允许穿过任何图形内部”。这显示了你的思考严谨性。模型建立分别阐述MIP模型和启发式模型。即使你主要用启发式求解MIP模型能体现你对问题本质的理解。算法设计详细说明你的距离计算算法和TSP求解算法最好配以流程图。实验结果设计不同规模和分布的测试数据如随机生成分散图形、聚集图形。用表格展示结果包括图形数量、算法运行时间、得到的总路径时间、与基准算法如最近邻的对比改进百分比。灵敏度分析改变切割速度与空走速度的比值观察最优路径是否发生变化。这能体现模型对不同生产环境的适应性。模型评价与推广客观评价模型的优缺点讨论在哪些实际情况下模型会失效如图形极度密集、存在凹多边形导致最短路径非直线并提出可能的改进方向。最后记住数学建模竞赛看重的是“模型”和“思考过程”而不仅仅是最终代码和答案。你的论文需要清晰地讲述一个故事如何从一个实际问题通过合理的抽象和简化转化为数学问题并设计有效的方案去求解它。代码是工具是验证你模型可行性的手段。将上述思路和代码框架有机结合深入挖掘每个环节的细节和原理你就能写出一篇有深度、有亮点的优秀论文。