1. 项目概述从钢板切割到数学建模的实战拆解看到“2024五一数学建模竞赛A题”这个标题很多同学第一反应可能是“哦又是一个优化问题”。但如果你真的这么想可能就错过了这道题背后隐藏的、连接工业实践与算法思维的绝佳桥梁。这道题的核心是“钢板最优切割路径问题”。简单说就是给你一块大钢板上面标记了若干个需要切割下来的小零件轮廓你的切割机比如激光或等离子需要沿着这些轮廓线走一遍把零件切下来。问题来了切割机从起点出发切完所有零件后回到起点怎么走总路程最短这听起来像是个“一笔画”或者“旅行商”问题对吧但实际上它要复杂和“脏”得多因为它涉及“空程”——切割头在不进行切割时的移动路径。这部分路径不产生价值却消耗时间和能耗是成本大头。所以最优路径的核心目标就是在保证切割出所有零件的前提下最小化空程总长度。这道题的价值远不止于拿奖。它本质上是一个经典的组合优化问题在工业场景下的具象化。你在解题过程中调用的贪心、动态规划、启发式搜索等算法思想是运筹学、物流调度、机器人路径规划乃至芯片布线领域的通用语言。通过它你能真正理解如何将一团乱麻的实际问题抽象成清晰的数学模型再用代码去求解和验证。无论你是数学、计算机、工业工程还是自动化专业的学生吃透这个问题对你建立系统性的优化思维都大有裨益。接下来我将以一个“老建模人”的视角带你层层剥开这道题不仅给出思路和代码框架更分享那些只有踩过坑才知道的实操细节和算法选型的底层逻辑。2. 问题核心与数学模型构建2.1 问题重述与关键约束解析首先我们必须把题目描述翻译成自己能精确操作的数学语言。通常题目会提供以下信息钢板信息一个矩形区域定义了长宽即切割的边界。零件信息N个需要切割的零件。每个零件由其轮廓上一系列有序的坐标点(x, y)定义首尾点相连形成封闭多边形。这是切割路径必须完整走完。切割规则切割必须从轮廓上的某一点开始完整遍历该轮廓所有边后才能离开去切下一个零件或返回。切割头在从一个零件的结束点移动到另一个零件的开始点期间或者从起点出发/返回起点时处于“空程”状态。空程移动通常假设为直线欧几里得距离且不能与已切割或未切割的零件内部区域发生干涉即不能穿过零件。但在初赛简化模型中有时会忽略干涉只考虑距离。优化目标寻找一个访问所有零件轮廓的序列并为每个零件选择一个合适的“起割点”使得总空程路径长度最小化。这里的关键难点有两个一是排序先切哪个后切哪个二是每个零件起割点的选择。两者耦合在一起使得搜索空间巨大。例如对于N个零件如果每个零件有M个可选起割点比如轮廓的每个顶点那么粗略的排列组合就有(N!) * (M^N)种可能完全枚举是不现实的。2.2 数学模型的建立我们需要建立两个模型一个是描述模型用来形式化地定义问题另一个是优化模型用来指导算法设计。描述模型设零件集合为P {P1, P2, ..., Pn}。对于零件Pi其轮廓点集为Vi {vi1, vi2, ..., vim_i}其中vi1和vim_i相连。我们可以定义其边集Ei。定义决策变量Xij ∈ {0, 1}表示切割路径中是否从零件Pi之后紧接着切割零件Pj。S_i表示零件Pi选择的起割点在其轮廓点集Vi中的索引。目标函数最小化总空程长度L_total Σ (从零件Pi的结束点到零件Pj的起割点的距离 * Xij) 从起点到第一个零件起割点的距离 从最后一个零件结束点到起点的距离。优化模型 这本质上是一个广义旅行商问题的变种。经典TSP要求访问每个“城市”一次而这里每个“城市”是一个零件轮廓且访问这个“城市”意味着要走完它的一整圈封闭路径哈密顿回路并且你可以从该轮廓的任意一点起割点开始和结束。这被称为“漫游推销员问题”或“线段TSP”。直接求解这个混合整数规划模型对于大规模问题非常困难因此我们必须转向启发式或元启发式算法。注意在竞赛中清晰地写出上述数学模型是拿分的基础。即使你后续用了启发式算法在论文中也需要展示这个形式化的模型体现你的建模思维。2.3 核心思路拆解分而治之的策略面对这个复杂问题一个行之有效的策略是“分而治之”将大问题分解为几个可管理的子问题子问题一单零件内部最优起割点选择。对于单个封闭轮廓从哪一点开始切割其结束点就在同一点。所以单零件内部的切割路径长度是固定的等于其轮廓周长。起割点的选择不影响本零件的切割长度但影响它连接前后零件空程的端点位置。因此我们需要为每个零件预计算一组“候选出口点”通常是轮廓的所有顶点或者再加上每条边的中点。子问题二零件间的空程优化排序与配对。给定每个零件的一组候选点我们需要决定①零件的切割顺序②每个零件具体使用哪个候选点作为“入口”也是上一个零件的“出口”。目标是最小化所有零件间空程距离之和。这很像一个“二次分配问题”。子问题三起点与终点的接入。将切割机的初始起点和最终返回点也纳入考虑相当于在零件序列的首尾增加了两个固定的“虚拟零件”。一个常见的简化思路是解耦先忽略单个零件内部起割点的选择假设每个零件用一个“代表点”如重心、几何中心或某个顶点来近似那么问题就退化为一个经典TSP访问所有代表点一次并回到起点。求得代表点的访问顺序后再在这个固定顺序下去优化每个零件具体从哪个点开始切割以最小化相邻零件间的空程。这种方法虽然可能不是全局最优但计算效率高且往往能得到不错的可行解。3. 算法选型与核心代码实现3.1 算法工具箱从精确到启发式没有一种算法能通吃所有规模和约束的切割问题。我们需要一个算法工具箱根据问题规模和精度要求进行选择。精确算法小规模N10动态规划DP对于非常小的问题可以用状态压缩DP来解决。状态定义为dp[S][i]其中S是一个二进制掩码表示已经切割的零件集合i表示当前位于零件i的某个结束点。dp[S][i]的值表示达到这个状态时的最小空程累积长度。通过枚举下一个要切的零件j及其起割点进行状态转移。这种方法能求得全局最优解但时间复杂度是O(2^N * N^2 * M^2)随着N增大呈指数爆炸。启发式算法中等规模10N50最近邻贪心算法从起点或当前点出发总是选择距离最近的、未切割零件的“最近入口点”作为下一个目标。实现简单速度快但容易陷入局部最优尤其是开局的选择会对最终结果产生很大影响。插入法先构建一个只包含少数零件如2-3个的初始路径然后不断将剩余的零件插入到当前路径中使总空程增加最小的位置。这比单纯贪心略好。2-opt / 3-opt 局部搜索在得到一个初始路径如通过贪心获得后尝试对路径进行局部调整来改进。例如2-opt就是尝试反转路径中一段子序列的顺序看是否能减少总距离。这是一种在固定顺序下优化路径的强力方法常作为其他算法的后处理步骤。元启发式算法大规模N50或追求高质量解模拟退火非常适合本题。它允许以一定的概率接受“更差”的解从而有机会跳出局部最优陷阱。我们可以将“一个解”定义为零件的排列顺序以及每个零件对应的起割点索引。邻域操作可以设计为交换两个零件的位置、逆转一段序列、或者随机改变某个零件的起割点。遗传算法将解编码为染色体例如一个序列表示零件顺序另一个序列表示对应的起割点索引。通过选择、交叉、变异操作迭代进化种群。其优势是并行搜索多个解但参数种群大小、交叉变异率调优需要经验。蚁群算法模仿蚂蚁觅食通过信息素引导搜索零件间的访问顺序。对于TSP类问题效果良好但同样需要参数调整。我的经验选择对于数学建模竞赛这种时间有限、需要快速出结果并撰写论文的场景我推荐“最近邻贪心 2-opt局部搜索”作为基线方案然后使用模拟退火进行全局优化。贪心算法能快速给出一个可行解2-opt能对其进行快速改进而模拟退火则提供了找到更优解的可能。代码实现上也相对直观。3.2 代码实现框架与核心模块以下是一个基于Python的代码框架使用了numpy进行数值计算matplotlib进行可视化非常有助于调试和展示结果。import numpy as np import matplotlib.pyplot as plt import random, math, itertools from typing import List, Tuple class CuttingPathOptimizer: def __init__(self, start_point: Tuple[float, float], parts: List[List[Tuple[float, float]]]): 初始化优化器。 :param start_point: 切割机起点坐标 (x, y) :param parts: 零件列表每个零件是其轮廓点的列表 [(x1,y1), (x2,y2), ...] self.start np.array(start_point) self.parts [np.array(part) for part in parts] # 转为numpy数组方便计算 self.num_parts len(parts) # 为每个零件预计算候选点这里简单取所有顶点 self.candidate_points [part for part in self.parts] # 每个零件的候选点就是其轮廓点集 # 计算零件间的距离矩阵简化版取零件重心间距离 self.centroids [part.mean(axis0) for part in self.parts] self.dist_matrix self._calc_distance_matrix(self.centroids) def _calc_distance_matrix(self, points: List[np.ndarray]) - np.ndarray: 计算点集之间的欧氏距离矩阵 n len(points) dist_mat np.zeros((n, n)) for i in range(n): for j in range(n): if i ! j: dist_mat[i, j] np.linalg.norm(points[i] - points[j]) return dist_mat def nearest_neighbor_path(self) - Tuple[List[int], float]: 最近邻贪心算法生成初始路径仅基于零件重心 unvisited set(range(self.num_parts)) path [] total_empty_distance 0.0 # 从起点到第一个最近零件 current_pos self.start while unvisited: # 找到距离当前点最近的未访问零件 nearest_part_idx min(unvisited, keylambda idx: np.linalg.norm(self.centroids[idx] - current_pos)) # 计算空程距离从当前点到该零件重心 dist_to_part np.linalg.norm(self.centroids[nearest_part_idx] - current_pos) total_empty_distance dist_to_part # 更新当前位置为该零件重心模拟在此零件切割 current_pos self.centroids[nearest_part_idx] path.append(nearest_part_idx) unvisited.remove(nearest_part_idx) # 从最后一个零件返回起点 dist_to_start np.linalg.norm(current_pos - self.start) total_empty_distance dist_to_start return path, total_empty_distance def two_opt_swap(self, path: List[int], total_dist: float) - Tuple[List[int], float]: 对给定路径执行2-opt局部搜索优化 improved True best_path path[:] best_dist total_dist n len(best_path) while improved: improved False for i in range(1, n-2): for j in range(i1, n): if j - i 1: continue # 相邻边反转无意义 # 尝试反转路径中 i 到 j 的部分 new_path best_path[:i] best_path[i:j1][::-1] best_path[j1:] # 计算新路径的空程距离简化计算仅基于重心 new_dist self._calc_path_distance(new_path) if new_dist best_dist - 1e-9: # 考虑浮点误差 best_path, best_dist new_path, new_dist improved True break # 找到改进就跳出内层循环重新开始扫描 if improved: break return best_path, best_dist def _calc_path_distance(self, path: List[int]) - float: 计算给定零件顺序路径的总空程基于重心简化模型 if not path: return 0.0 dist np.linalg.norm(self.centroids[path[0]] - self.start) for k in range(len(path)-1): dist np.linalg.norm(self.centroids[path[k1]] - self.centroids[path[k]]) dist np.linalg.norm(self.centroids[path[-1]] - self.start) return dist def simulated_annealing(self, init_path: List[int], init_cost: float, T_start1000.0, T_end1e-3, alpha0.99, max_iter5000) - Tuple[List[int], float]: 模拟退火算法优化路径。 :param init_path: 初始路径零件索引列表 :param init_cost: 初始路径成本 :param T_start: 初始温度 :param T_end: 终止温度 :param alpha: 降温系数 :param max_iter: 每个温度下的迭代次数 :return: 优化后的路径和成本 current_path init_path[:] current_cost init_cost best_path current_path[:] best_cost current_cost T T_start n len(current_path) while T T_end: for _ in range(max_iter): # 生成邻域解随机交换两个零件的位置 new_path current_path[:] i, j random.sample(range(n), 2) new_path[i], new_path[j] new_path[j], new_path[i] # 计算新成本 new_cost self._calc_path_distance(new_path) # 判断是否接受新解 delta new_cost - current_cost if delta 0 or random.random() math.exp(-delta / T): current_path, current_cost new_path, new_cost if current_cost best_cost: best_path, best_cost current_path[:], current_cost T * alpha # 降温 return best_path, best_cost def optimize(self) - dict: 主优化流程 # 1. 生成初始解贪心 print(生成初始贪心路径...) nn_path, nn_cost self.nearest_neighbor_path() print(f初始贪心路径成本: {nn_cost:.2f}) # 2. 局部搜索优化2-opt print(执行2-opt局部优化...) opt_path_2opt, opt_cost_2opt self.two_opt_swap(nn_path, nn_cost) print(f2-opt后路径成本: {opt_cost_2opt:.2f}) # 3. 全局优化模拟退火 print(执行模拟退火优化...) sa_path, sa_cost self.simulated_annealing(opt_path_2opt, opt_cost_2opt, T_start1000, T_end1e-3, alpha0.995, max_iter200) print(f模拟退火后路径成本: {sa_cost:.2f}) # 4. 最终路径精细调整可选的二次2-opt final_path, final_cost self.two_opt_swap(sa_path, sa_cost) print(f最终优化路径成本: {final_cost:.2f}) return { initial_path: nn_path, initial_cost: nn_cost, optimized_path: final_path, optimized_cost: final_cost, centroids: self.centroids } def visualize(self, result: dict, save_pathcutting_path.png): 可视化优化前后的路径对比 fig, (ax1, ax2) plt.subplots(1, 2, figsize(15, 6)) centroids result[centroids] start self.start # 绘制初始路径 ax1.set_title(fInitial Greedy Path (Cost: {result[initial_cost]:.2f})) for i, part in enumerate(self.parts): ax1.plot(part[:, 0], part[:, 1], k-, alpha0.5) # 零件轮廓 ax1.scatter(centroids[i][0], centroids[i][1], cblue, s50) # 重心 path result[initial_path] # 绘制空程路径 for k in range(len(path)-1): ax1.plot([centroids[path[k]][0], centroids[path[k1]][0]], [centroids[path[k]][1], centroids[path[k1]][1]], r--, lw1, alpha0.7) # 绘制起点和返回线 ax1.scatter(start[0], start[1], cgreen, s100, markers, labelStart/End) ax1.plot([start[0], centroids[path[0]][0]], [start[1], centroids[path[0]][1]], r--, lw1, alpha0.7) ax1.plot([centroids[path[-1]][0], start[0]], [centroids[path[-1]][1], start[1]], r--, lw1, alpha0.7) ax1.legend() ax1.set_aspect(equal, adjustablebox) ax1.grid(True, alpha0.3) # 绘制优化后路径 ax2.set_title(fOptimized Path (Cost: {result[optimized_cost]:.2f})) for i, part in enumerate(self.parts): ax2.plot(part[:, 0], part[:, 1], k-, alpha0.5) ax2.scatter(centroids[i][0], centroids[i][1], cblue, s50) path result[optimized_path] for k in range(len(path)-1): ax2.plot([centroids[path[k]][0], centroids[path[k1]][0]], [centroids[path[k]][1], centroids[path[k1]][1]], b-, lw2, alpha0.8) ax2.scatter(start[0], start[1], cgreen, s100, markers, labelStart/End) ax2.plot([start[0], centroids[path[0]][0]], [start[1], centroids[path[0]][1]], b-, lw2, alpha0.8) ax2.plot([centroids[path[-1]][0], start[0]], [centroids[path[-1]][1], start[1]], b-, lw2, alpha0.8) ax2.legend() ax2.set_aspect(equal, adjustablebox) ax2.grid(True, alpha0.3) plt.tight_layout() plt.savefig(save_path, dpi300) plt.show() print(f可视化结果已保存至: {save_path}) # 示例用法 if __name__ __main__: # 模拟生成一些随机零件三角形、四边形等 np.random.seed(42) parts_data [] for _ in range(8): # 生成8个零件 num_points np.random.randint(3, 6) # 每个零件3-5个顶点 # 随机生成一个中心点然后在其周围生成轮廓点 center np.random.rand(2) * 10 angles np.sort(np.random.rand(num_points) * 2 * np.pi) radii 0.5 np.random.rand(num_points) * 0.5 points center np.column_stack([radii * np.cos(angles), radii * np.sin(angles)]) # 确保轮廓闭合 points np.vstack([points, points[0]]) parts_data.append(points.tolist()) start_point (0, 0) # 创建优化器并求解 optimizer CuttingPathOptimizer(start_point, parts_data) result optimizer.optimize() # 可视化 optimizer.visualize(result)这个框架提供了从数据输入、算法实现到结果可视化的完整流程。它基于“零件重心”的简化距离模型这是竞赛中快速出结果的常用策略。在实际比赛中你需要根据题目提供的具体数据格式可能是文本文件或特定结构来调整数据加载部分。3.3 关键代码段解析与优化点距离计算_calc_distance_matrix函数计算了零件重心间的欧氏距离。这是整个优化模型的基石。如果题目要求考虑空程不能穿过零件这里的距离计算将变得极其复杂可能需要使用几何库如shapely来判断线段与多边形是否相交并计算绕过零件的最短距离或者采用A*等图搜索算法在网格化地图上寻路。这会大大增加计算量通常只在高阶优化中考虑。最近邻贪心nearest_neighbor_path函数是构建初始解的快速方法。它的缺点是路径依赖性强第一个选择会锁定后续方向。一个改进策略是运行多次每次从不同的“虚拟起点”或随机选择的第一个零件开始取最好的结果作为初始解。2-opt局部搜索two_opt_swap函数是路径优化的利器。它通过尝试“反转路径片段”来消除路径交叉这是改善TSP路径非常有效的方法。注意我们的实现中距离计算依赖于重心所以每次评估新路径成本时都调用了_calc_path_distance。在零件数很多时可以优化为增量计算只计算发生改变的那段路径的距离变化以提升效率。模拟退火simulated_annealing函数是跳出局部最优的关键。参数设置是核心初始温度T_start要足够高使得算法在初期有较大概率接受差解。可以设置为初始路径成本的若干倍如10-100倍。终止温度T_end足够低使得算法后期基本只接受好解。降温系数alpha通常在0.9到0.999之间。越大降温越慢搜索越充分但耗时越长。每个温度的迭代次数max_iter与问题规模相关通常设置为零件数量的若干倍。邻域操作我们这里只用了“交换两个零件位置”。更强大的邻域可以包括“逆转一段序列”、“将一段序列移动到另一个位置”等。好的邻域设计能显著提升算法性能。可视化visualize函数至关重要。在建模竞赛中一张清晰的路径对比图比大段文字更能说明你算法的有效性。务必在论文中展示优化前后的路径图。4. 高级优化与模型深化4.1 引入零件内部起割点优化前面的模型将每个零件简化为一个点重心。要获得更优解必须考虑零件轮廓上起割点的选择。这可以将问题建模为一个双层优化问题上层决定零件的访问顺序。下层在给定顺序下为每个零件选择最优的起割点使得相邻零件间的空程距离之和最小。对于下层问题当零件顺序固定后它就变成了一个动态规划问题。设顺序为P1, P2, ..., Pn。定义dp[i][k]为切割完前i个零件且第i个零件选择其第k个候选点作为结束点时所累积的最小空程从起点开始算。状态转移方程为dp[i][k] min_{j in candidates of P_{i-1}} { dp[i-1][j] distance( end_point(P_{i-1}, j), start_point(P_i, k) ) }其中distance是两点间的空程距离start_point(P_i, k)是零件Pi的第k个候选点也作为起割点end_point(P_{i-1}, j)是零件P_{i-1}的第j个候选点也作为结束点对于封闭轮廓起割点就是结束点。这样通过DP可以求出给定顺序下的最优起割点选择和最小空程。然后上层再用模拟退火等算法去搜索不同的零件顺序。这种方法比点模型精确得多但计算量也大很多因为每个状态转移都需要计算距离且DP的复杂度是O(N * M^2)其中M是候选点数量。4.2 处理复杂约束空程干涉与切割顺序约束实际工业切割中还有更多约束空程干涉切割头在空移时不能与已切割或待切割的零件发生碰撞。这需要引入几何碰撞检测。一个实用的近似方法是在路径规划时将每个零件的外接矩形或凸包作为“障碍物”空程线段如果与任何障碍物相交则为其距离加上一个很大的惩罚项或者使用绕行路径如沿着障碍物边界走。切割顺序约束某些零件嵌套在另一些零件内部像俄罗斯套娃。必须先切割内部的零件否则当外部零件被切下后内部的零件可能掉落或移位。这需要在建模时构建零件的拓扑关系图如通过判断一个零件的重心是否在另一个零件的多边形内部并在优化时加入约束确保内部零件先于其外部容器被切割。这可以通过在搜索算法中过滤掉违反约束的序列来实现。4.3 算法性能调优与并行化当零件数量达到数百甚至上千时算法效率成为瓶颈。以下是一些调优策略距离矩阵预计算与缓存对于点模型或固定候选点模型提前计算所有点对之间的距离并存储为矩阵避免在算法循环中重复计算距离。邻域评估的增量计算在模拟退火或局部搜索中当对当前解做一个小的改动如交换两个零件时只重新计算受影响的路径段距离而不是整个路径。使用更高效的数据结构例如在寻找最近邻时可以使用KD-Tree来加速空间搜索。并行化模拟退火和遗传算法天然适合并行。可以在多个线程或进程中同时评估多个邻域解或多个个体。分解与合并对于超大规模问题可以先将零件聚类成若干组先在组内优化再优化组间的顺序。5. 竞赛实战心得与避坑指南5.1 论文写作的核心要点数学建模竞赛“模型”和“算法”只占一半分数另一半在于“论文表述”。针对本题论文需要突出以下几点问题分析部分一定要画出清晰的示意图说明“切割路径”、“空程”、“起割点”等概念。将实际问题转化为图论或网络优化问题的过程要写清楚。模型建立部分分层次阐述。先建立“点近似模型”作为基础再逐步引入“起割点优化模型”、“干涉约束模型”等体现模型的逐步深化。公式要规范变量说明要清晰。算法设计部分不要只扔代码。要用流程图、伪代码或文字描述清楚算法的步骤。特别是模拟退火要解释清楚温度、邻域、接受准则等概念是如何应用到本问题中的。说明为什么选择这些算法它们的优缺点是什么。结果分析部分这是拿高分的关键。不能只说“我们的结果很好”。对比实验设计对比实验例如单独贪心算法 vs 贪心2-opt vs 模拟退火。用表格和图表如收敛曲线图、路径对比图展示不同算法的结果和运行时间。灵敏度分析分析算法参数如模拟退火的初始温度、降温系数对结果的影响。展示你的参数不是瞎选的。模型有效性分析如果你的模型考虑了更复杂的约束如干涉要设计案例证明考虑该约束的必要性。例如展示不考虑干涉时路径会穿过零件而你的算法能规避。可视化一定要有优化前后路径的对比图这是最直观的证据。可以用不同颜色区分切割路径和空程路径。模型评价与推广客观评价自己模型的优点如高效、解质量高和局限性如对大规模问题耗时、忽略了某些物理约束等。并提出可能的改进方向。5.2 常见问题与调试技巧算法陷入局部最优效果不佳检查初始解尝试多种方法生成初始解随机生成、多个不同起点的贪心、插入法等选择最好的一个作为模拟退火的起点。调整退火参数提高初始温度T_start降低降温速度增大alpha增加每个温度的迭代次数max_iter。给算法更多“探索”的空间和时间。丰富邻域操作除了交换尝试增加“逆转”、“插入”等操作扩大搜索范围。结合多种算法用遗传算法生成一个多样化的初始种群再用模拟退火对其中优秀个体进行精细优化。程序运行速度太慢性能剖析使用Python的cProfile模块找出代码中的耗时热点。通常是距离计算或邻域评估部分。向量化计算尽量使用numpy的向量化操作代替Python循环进行距离计算。缓存与增量更新如前所述预计算距离矩阵在局部搜索中增量更新路径成本。降低问题规模在调试和初步实验时使用小的数据集如10-20个零件。可视化结果路径交叉严重这是初始贪心算法常见问题。2-opt局部搜索正是为了解决路径交叉。确保你的2-opt实现正确并且迭代足够次数直到没有改进。如果2-opt后仍有交叉可能是因为你的“距离”定义是重心间的直线距离而实际最优空程可能需要绕行。考虑在可视化时将空程路径画成曼哈顿距离直角折线或进行简单的碰撞规避处理这样图形会更“整洁”虽然计算模型可能还是直线距离。结果不稳定每次运行都不一样这是启发式算法的固有特点尤其是涉及随机性的模拟退火、遗传算法。在论文中应报告多次运行如20次的最佳值、平均值和标准差以证明算法的鲁棒性。最终提交的结果当然是多次运行中最好的那个。如何处理题目中可能给出的特殊形状如包含内孔如果零件有内孔即轮廓不止一个环那么切割路径需要遍历所有环。这可以看作是将一个零件拆分成多个独立的“子轮廓”每个子轮廓都必须被访问一次。在建模时可以将一个零件的多个内孔视为必须被连续访问的“子任务”在访问该零件时需要规划好访问这些子轮廓的顺序和起割点。这进一步增加了问题的复杂性可能需要设计更复杂的“零件内”路径规划算法如将其视为一个微型的TSP。