算法实例：平面寻路

2018/11/26

01 引言

问题描述：电路焊接过程中，自动化机械手需要将电路板上元器件的引脚连接到已打好的孔中，为了保证焊接过程机械手走的路径最短，即耗费时间最短，设计一个算法。
问题来源：《算法设计手册》p17.

电路板焊接实例

这是一个书籍讲解的范例，把电路版焊接作为一个引子。记录一下面对这种问题的时候，我的解决方案。

02 解决方案

数据建模

问题描述部分是按照现实生活中的描述，本质上是一个寻路问题，并不适用于解决问题的过程。

• 为了转化为数学问题，需要一个模型。首先建立坐标系，就普通的坐标系就可以。
• 为了突出问题，我们忽略机械手的初始位置，对上图中的点进行编号，并假设机械手从0号点出发。（这里这个假设本质上有些不够准确，忽略了很多信息，比如说那种一条直线的点，如果我随便找一个点作为起点，肯定就不是最短的了。但为了初步的分析，就先这样假设。）

（实际上的点有很多分布的形式，图中算是一个比较简单的实例，后续再来分析其他的各种情况）

将以上的信息整合，把问题转化如下：

P：存在一个集合S，集合中的元素为坐标系中的点（x,y），对集合中的元素进行排序，使得到的新的有序集合的元素，按顺序距离总和最小。

算法分析过程

随机从一个点出发，可以找到的路径很多，肯定不能用穷举那样的笨方法。要想思考出来好的算法， 就先看看我手里的信息嘛，逐步整合。

• 坐标系
• 各个点的位置

从明面上看，这已经是所有的信息了；其实还有一个隐藏的信息，就是各个点之间的直线距离。

首先就从这个距离上下功夫，脑海里想到的第一个算法。

第一个尝试：贪心算法，每次选择距离最短的点

1. 随机选择一个点作为出发点，并作为当前操作的点；
2. 求出剩余集合中与当前操作的点距离最短的那个点，如果有多个点距离相等，随机取一个；
3. 将取出的新的点，作为新的当前操作的点，并重复步骤2，直至剩余点为0。

采用贪心算法的结果，每次都是局部最优的，这样选择出来的结果，可能是最优的，也可能不是；相比穷举搜索的算法，已经提高了很多的效率，但仍有提升的空间。
注意看，每次步骤3的时候，从集合中取出一个新的点，都要去计算这个剩余集合中所有点和当前操作点的距离。（这个地方应该把时间复杂度给列上来）这是一个很耗时的操作，就像之前看过的字符串匹配的问题，如果以往的操作可以给你一些后面利用的信息，这种可以给你提供很大的价值。

第二个尝试：改进的贪心算法，利用最边上的点作为起始点

虽然前面提到了利用某数据结构来加速选点的过程，但是一下子来让我去想一个数据结构我可能也想不起来，我记得比较接近的就是kd-tree把，这个是当时做聚类的时候学到的一个。我先从简单的问题出发。
每次都选出一个最短的路径，如果分解了之后，就是新的点X轴和Y轴距离当前操作的点都最近。如果是按照排序的方式，因为这些点都是随机分布的，没有什么特殊的，你没有标准先找到第一个点。但是刚才也说过了，如果这些点分布在一条直线上（例如，与X轴平行），那么这个时候选取的初始点就存在意义了。所以要设计一个数据结构，对这些要求不敏感的，我直接就从最靠边上的点作为起始点就好了。

1. 对各个点按照X轴上的大小进行排序，
2. 将X轴上的最靠边（影响后续选择）的点做为起始点，并作为当前操作的点；
3. 按照已经排好序的点，从集合中取出最近的点；
4. 将取出的新的点作为新的当前操作的点，重复步骤3，直至集合为空集。

虽然上面的想法很好，但是这个算法失败了。

可以看看这样出来的效果：

第二个算法效果

上面这个算法可以借鉴的地方就是那个将最边上的点最为起始点。（这句话也不完全对，还是有一些不适用的地方。

03 结论

这是一个旅行商的问题，我这里思考的过程基本上没有问题，但没有抓到一些本质，所以结果并不是很理想。另外，我感觉，我对问题的抽象还是不够。

看来我得想第三个了，其实我前面的想法挺不错的，就是利用已经计算过的信息；或者说我是不是还有别的信息量没有挖掘出来。

这里仅仅是自己的一个思考，还是踏踏实实的看书上的说法把。