第三章：路径规划核心概念——图论基础与TSP的映射关系
各位工程师朋友，今天我们来聊聊路径规划里最核心的几个概念。说实话，我刚入行那会儿，觉得路径规划不就是让激光头从A走到B吗？后来被现实狠狠教育了一顿——划片路径的优劣，直接决定了你的产能和良率。
3.1 图论基础：节点、边、路径
图论听起来高大上，其实说白了就是研究「点」和「线」的关系。在划片机里，每个划片起点、终点、转角点，都可以看作一个节点。节点之间的连线就是边，代表激光头移动的轨迹。而一条完整的划片路径，就是由若干节点和边组成的序列。
核心映射关系：
- 节点 → 划片起点、终点、换向点、Mark点
- 边 → 激光头在两个节点之间的移动轨迹（含空行程和加工行程）
- 路径 → 从起始节点到终止节点的完整移动序列
我个人习惯把划片路径拆解成「加工边」和「空移边」两类。加工边就是实际切割的线段，空移边则是激光头抬起后快速移动的线段。你想想看，优化路径的本质，就是尽量减少空移边的总长度。
避坑指南：我曾经在一个项目中，把所有节点都当作加工节点来处理，结果路径规划出来的空移距离比加工距离还长。后来才意识到，必须区分「必须经过的节点」和「可选经过的节点」。
3.2 旅行商问题（TSP）与划片路径的映射
旅行商问题，就是找一条最短路径，让旅行商访问所有城市各一次，最后回到起点。你发现没有？这和划片路径规划简直一模一样——激光头需要访问所有划片起点，完成切割后回到原点或下一个起点。
但这里有个关键区别：划片路径的「城市」不是任意点，而是有顺序约束的。比如，你必须在划完一条线之后才能去下一条线的起点。这就把TSP变成了有约束的TSP，也叫「顺序依赖旅行商问题」。
| TSP要素 | 划片路径映射 | 我的经验 |
|---|---|---|
| 城市 | 划片起点/终点 | 注意区分单起点和双起点场景 |
| 距离 | 激光头移动时间 | 空移速度通常比加工速度快3-5倍 |
| 访问顺序 | 划片顺序 | 必须满足工艺约束（如热影响区） |
| 回到起点 | 回到原点或下料点 | 有些场景不需要回原点 |
为什么会这样？因为激光划片不是简单的「点对点」移动。你想想看，如果两个划片区域靠得很近，但中间有障碍物（比如夹具），那空移路径就不能走直线。这时候，图论里的「最短路径算法」就派上用场了。
3.3 图论建模实战：从划片图形到图结构
我建议你按照以下步骤来建模：
- 提取所有划片线段端点：每个线段有两个端点，记作节点
- 建立邻接矩阵：计算所有节点之间的欧氏距离
- 标记加工边：将属于同一划片线段的两个节点之间的边标记为「必须加工」
- 添加虚拟节点：比如起始点、换向点、安全高度点
- 求解TSP：在满足加工顺序约束的前提下，找最短哈密顿路径
注意：千万不要直接用标准TSP求解器！我踩过这个坑——标准TSP假设所有节点都是「自由访问」的，但划片路径中，加工边的顺序是固定的。你需要用「有向图」或「约束图」来建模。
3.4 核心知识体系图
下面这张图是我自己总结的，把本章的知识点串起来了：
3.5 一个真实案例
我记得有一次做手机玻璃盖板的划片，图形上有200多个小矩形需要切割。如果用最简单的「逐行扫描」方式，空移路径总长超过15米。后来我用图论建模，把每个矩形的起点作为节点，用TSP求解器优化访问顺序，空移路径缩短到了4.2米。
你猜怎么着？单件加工时间从12秒降到了8.5秒，产能提升了29%。这就是路径规划的价值所在。
关键结论：
- 图论是路径规划的数学基础，节点和边的定义决定了优化空间
- TSP是划片路径优化的核心模型，但必须加入工艺约束
- 空移路径的优化比加工路径更重要，因为空移不产生价值
- 建模时一定要区分「必须加工边」和「可选空移边」
好了，这一章的内容就到这里。图论和TSP是路径规划的基石，理解透彻了，后面讲具体算法时你才能游刃有余。
公众号:蓝海资料掘金营，微信deep3321