shitsurei

失礼しました

0%

记一次算法的方案设计

发表于 更新于 分类于
实际情况，往往比理论复杂得多

随着无人机技术的快速发展，其用途也变得越来越广泛，工业农业和日常生活中处处都可以看到无人机的影子，国产无人机品牌大疆也因其国际领先的技术和工业水准广为人知。虽然用途广泛，但是总结起来也无非信息收集和物品传输两大类，因为无人机相较于传统的侦测设备或物流设备突破的点就在于不受地形的限制和视野的约束，受限于目前无人机技术的续航能力和载重能力，在物品传输方面的选择比较有限，所以大量的无人机还是运用在航拍，范围搜索，地形侦测，活动单位追踪等方面。对于收集信息的无人机，一般而言都是人为操纵无人机的飞行航线并有选择地在适当时机来记录信息的，那么我们是否有可能让无人机按照一定的路线自动导航并进行信息的收集呢，下面我们就来尝试一下。

问题抽象

假设我们现在想利用具备航拍功能的无人机了解某个区域的地形情况，那么我们需要考虑的情况会有哪些？如果在实际情况中，影响的因素会非常复杂，例如

我们是否了解这块地形的大致情况，例如是一个矩形区域还是圆形区域，或者是不规则形状？

如果是矩形区域，那么他的长宽大致是多少；如果是圆形区域，那么他的半径大致是多少？

我们如何选择无人机的起飞位置呢？

无人机的续航是否足够其遍历整个区域再返回起始位置？你不会希望飞到一半无人机没电了坠落吧……

无人机每次拍摄地形信息都要进行存储，那么无人机最大支持的存储空间是否满足覆盖整个地形范围呢？

如果因为天气因素导致无人机偏离原本航线时如何处理呢？

如果无人机的续航能力无法保证其一次完成整个地形的探测任务，那么我们应该如何对整个航线进行分段探测呢？

……

建模

如果我们不对整个问题的范围和变量做一定的约束，那么总会存在我们考虑不周到的点，使得整个问题在还没开始就变得无比复杂，与其这样，不如我们先对整个任务的资源和要求做一定的限制，在此基础上完成整个方案的核心要素，回过头来再在此基础上添加新的功能，增强算法的可扩展性和健壮性。

我们对整个任务做以下限制：

  • 我们将待探测的区域抽象为一个M×N大小的矩形区域，无人机的飞行轨迹可以看做在地图上的一个个坐标之间移动，移动距离使用两点间的曼哈顿距离
  • 地图上的每个坐标范围内的区域信息用某种数据格式表示，其表示形式和含义不重要，这里假定为字符格式
  • 无人机可以在地图上的任何位置进行航拍，每次拍摄可以记录当前位置及其前后左右四个方向的地图信息
  • 无人机需要从地图上的某个点起飞，最终收集完整个地图的信息后返回出发点
  • 无人机在飞行的过程中会消耗电量，且支持存储的航拍信息也有上限，这里不限定为具体数值，但需要尽可能的节省飞行距离和存储空间

为什么航拍的范围是“十字”

以上就是我们假定的一些限制条件，部分同学可能有疑惑，为什么每次拍摄只能记录一个“十字”范围的区域信息，这样对飞行过程中收集地图信息带来很多难度，但是如果大家对真实无人机的航拍方式有所了解，其实这是有实际意义的。大家可以回头看一眼本篇博客封面的图片，就是一个航拍的照片，为了使得一次拍摄包含更多的地图信息，我们一般会选择使用广角摄像头，这种摄像头的成像结果会以当前位置为圆心，三百六十度无死角的将四面八方的地图拍成一张圆形的图像，如下图所示：

广角航拍范围视图

我们为了方便计算，假设照片的范围正好与3×3的地图区域相切，那么此时图中左上，右上，左下，右下四个区域所能拍摄到的范围还不及当前单位面积的一半，因此不能算收集到了该区域的地图信息，单纯的观察图片可能无法得出靠谱的数据解释，我们可以通过Python的scipy库计算一下图中各个单位中所拍到的面积占单位面积的比例。

首先我们建立坐标系，因为圆形区域与正方形相交的部分除了中心位置的正方形面积被全部包括外，周围的八个部分可以分成两类，其中上下左右四个位置的面积是相等的，记为面积A；四个角落的位置同样是相等的，记为面积B。我们只需要求出面积A和B的大小即可，出于数值取整的考虑，我们将上图中一个小正方形区域的边长设置为2，同时为了方便求积分操作，我们把圆心放在[3,-1]位置，此时只需要计算圆的方程在[0,2]区间和[2,4]区间的积分结果，即为B和A的面积。

坐标系

以下是计算和验证面积A和面积B的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from scipy import integrate
def f(x):
    return (9-(x-3)**2)**0.5-1
v1, err = integrate.quad(f, 0, 2)
# 2.125103815660392
print(v1)
v2, err = integrate.quad(f, 2, 4)
# 3.886959309833288
print(v2)
# 0.531275953915098
print(v1/4)
# 0.971739827458322
print(v2/4)
# 面积验证
import math
# 28.274333882308138（通过πR^2计算的圆面积）
print(9*math.pi)
# 28.04825250197472（通过累加和大正方形相切的各个部分面积计算圆的面积）
print((v1+v2)*4+4)

通过计算结果我们看到面积A的大小为2.13，面积B的大小为3.89，已知一个正方形的面积为4（边长为2），因此面积A的占比只有该区域的53%，而面积B可以达到97%，因此在一次无人机航拍时，四个边角位置是无法获取其完整信息的。

问题剖析

通过分析上文的几个限制条件，我们可以发现要完成一个无人机的航拍算法，需要考虑三个要点，评价算法的优劣有三大指标。先说三个要点：

  • 起飞位置
  • 飞行航线
  • 拍摄时机

题目要求无人机在某个位置起飞完成整个区域的探测任务后还要返回起飞位置，实现一个完全自动化的巡航和拍摄任务，因此无人机从地图中的哪个位置起飞，飞行过程中要依据什么来选择移动路径，又依据什么来选择合适的拍摄时机，如何判断已经完成了拍摄任务，如何从最终位置返航，这些都是我们要精心规划的。

再看三大指标：

  • 信息收集
  • 飞行距离
  • 拍摄次数

在最后两个条件中规定了这个算法的功能指标和性能指标，其中第四个条件要求无人机必须对整个地图的信息收集完整，这是一个功能性的指标，如果最终我们的算法使得收集的信息有遗漏，那么这个算法就是一个无法交付的版本；而第五个条件没有明确量化要求无人机的续航限制和内存限制，因为我们可以将其理解为两个性能相关的指标，其一是无人机的续航能力是有限的，每一次位置的移动都会耗费无人机的剩余电量，换句话说无人机一次续航后的航行里程是有上限的，我们要尽可能的减少无人机的移动次数；其二是无人机的存储容量是有限的，因此我们不能每次移动都进行拍摄，这样会造成存储的较大浪费（虽然实际情况中可能需要重复的位置信息来帮助我们勘误），因此我们要尽可能减少拍摄的次数。这两条指标是用于评价算法的性能，类似于我们用于评价算法的时间复杂度和空间复杂度。

“十字”拼图

对于一个算法方案，最优先考虑的当前是实现其功能，其次再来优化性能，题目要求规划的路线和拍摄方案要收集完整个区域的地图信息，换句话说在这个M×N的地图上每一个点都要被拍到至少一次，直观的反映到地图上相当于我们拿着一个“十字”形状的印章盖在地图上，直到地图上的所有位置被盖过。由于从这一次拍摄到下一次拍摄这样一个过程是需要无人机一步步移动过去的，如果拍摄的顺序过于跳跃或者说两次拍摄为了避免重复而中间存在遗漏的区域，就会消耗额外的移动次数折返回去查漏补缺，因此考虑选择拍摄的时机尽可能在移动的距离尽可能小的情况下（这里说尽可能小而不是最小因为最小就退化为每次移动都进行拍摄，这样会出现大量的存储浪费），那么移动距离为多少比较合适呢，毫无疑问3最合适，因为一次拍摄的长和宽范围都是3，因此在当前拍摄点向任意方向不折返的移动3的步长，下一次拍摄就不会出现重复的拍摄信息，但是这三步怎么走，其实我们有很多种选择，基本可以分为下图中的三种：

无重复飞行路径

  1. 如图所示第一种是每一次拍摄后按直线的方式向右（也可以向左，向上，向下）移动3步，作为下一次的拍摄坐标，这种方式很直观也很有效，但这种方式无法避免的一个问题是会出现信息重复，图一中两次拍摄不论方向如何选择，在这两次的拍摄范围内都会存在两个位置的信息空缺，这意味着这两个位置需要在之后的折返过程中重新拍摄填补，即使是尽可能的使拍摄信息之间不重复，也会存在一个无法弥补的区域（图中黑色阴影的坐标）需要我们不得不以重复信息的代价来填补这一空缺；
  2. 相比第一种，第二种“十字”拼图的排列方式就巧妙得多，因为他并不是选择一味地向一个方向移动3的步长，而是将3步拆分成水平方向走1步和垂直方向走2步，这样的移动方式和第一种一样都是每次移动拍摄位置花费3步的距离，但是却有效避免了信息的重复，其对存储空间的利用效率就提升了不少；
  3. 同样的，第三种移动方式也是对3的步长选择了拆分，但与第二种不同的是，第二种总是选择水平方向的1步和垂直方向的2步（也可以选择水平方向的2步和垂直方向的1步），即最终的巡航路线接近于优先对某个范围的垂直方向（或水平方向，取决于移动方式的选择）进行遍历；但是第三种的移动方式我们发现他会在水平方向和垂直方向交替的进行1步和2步的选择，这样也能满足信息不出现重复，而其巡航路线则会更接近一种圆周运动。

时间优先VS空间优先

从上面的尝试来看，显然不存在理想化的方案使得我们百分之百的充分利用每次拍摄收集的信息，我们无法避免存储空间的浪费，即使我们不考虑重复问题，位于地图的四个边角位置的坐标，我们不论以何种方式去拍摄这些位置的信息都会造成某个拍摄的范围位于整个地图之外，这个范围无疑就会被浪费掉。既然损失无法避免，也就是说不存在方案选择上的最优解，那么我们只能通过比较不同方案的性能来选择“较优解”或者更适应某种情况的解。

为了便于方案的性能评估，我们现在这里设定两个理想状态下的性能指标，第一个是存储空间的理想指标，由于整个地图的大小时M×N的，因此如果存在一种理想的拍摄方式，使得每次拍摄都不存在重复信息，且每次拍摄都可以得到5个有效的坐标信息，那么收集整个地图所需的拍摄次数为Math.ceiling(M×N÷5)，由于前面已经说明了实际巡航拍摄中一定存在信息的重复和损失，因此这只是一个理想值，实际方案不可能达到；第二个是航行时间的理想指标，正如之前的考虑，当我们的移动步长为3时，拍摄到的信息可以保证不重复，因此我们要拍摄完整个地图也至少要移动够3×Math.ceiling(M×N÷5)的距离，这只是从拍摄起点移动到拍摄终点的路程，如果要加上折返距离还要更大，但是航行的折返距离是取决于具体的航线规划的，不同规划方案最终拍摄完成后的坐标位置是不同的，我们也不排除存在航行拍摄完成后刚好回到起始位置的方案，因此关于时间上的理想指标（也可以叫航行距离理想指标）我们就按照3×Math.ceiling(M×N÷5)来计算。

方案设计

在测试无人机飞行拍摄方案时我们可以感性地认识到，当我们想要去节省无人机的飞行距离时，不得不付出重复拍摄信息的代价，而想要不重复的拍摄地图信息又需要无人机在飞行航线上做更加复杂的设计，从而使得飞行距离变长。也就是说作为衡量无人机飞行方案的两个性能指标存在潜在的负相关关系，具体的量化分析可能非常复杂，但是至少我们可以分别从两个方面去尝试逼近各自的最优解，再在此基础上看一下是否存在可以结合或优化的空间。因此基于这两种指标我们分别尝试给出最少移动距离方案，和最少拍摄次数方案。

方案一：最短移动路径方案

这个方案我们完全以移动距离为优先考虑的性能指标，即在满足拍摄信息覆盖整个地图的前提下，尽可能少的让无人机进行移动，不考虑节省拍摄次数，这一算法方案的实际意义主要有两个方面：

  1. 目前的无人机续航问题相比空间存储问题的优先级更高，因为随着存储技术的进步，存储空间的成本越来越低，相比而言电池技术一直没有大的突破，基本是靠“堆量”堆出来的，但是无人机航行主要的耗电成本就是克服自身重量的做功，所以续航的提升是主要问题，设计尽可能少的航行距离在实际需求中优先级较高；
  2. 前面的分析也指出，拍摄区域信息的重复在实际意义中也有着勘误和验证的作用，并非纯粹浪费存储空间。

设计这个路线最容易想到的就是以3行或3列为一个单位进行行遍历或列遍历，因为拍摄区域的长和宽都是3，所以我们在每一栋一层就拍摄3格的有效信息，同时出于无人机的移动尽可能少的考虑，采用“S”型遍历路线，即到达一侧边界后向下移动三格再以反方向遍历至另一侧，直到整个地图遍历完成。下面给出当地图大小为7×7时的路线图：

方案一路线图

图中我们假定的无人机起飞位置在(1,0)坐标处，从S1起飞后向右不断移动，每次移动都对当前位置的拍摄范围进行拍摄，直到S7位置拍摄完成后向下移动3步到S8位置后继续向左移动并拍摄，值得注意的是如果我们最后一次遍历只剩下一行时可以对拍摄进行优化，如图所示只需要S15，S16，S17这三个位置进行拍摄即可涵盖所有地图信息，减少一定的存储压力。从这一点优化方案中我们可以发现，当地图的长宽M和N中存在某个值是3的整数倍或整数倍加1时，我们在另一条边上遍历可以减少一定的存储压力。

下面我们来计算一下这种方案的移动次数和拍摄次数：

  • 拍摄次数：Math.ceiling(M/3)×N
  • 移动次数：Math.ceiling(M/3)×N+M（M为最终返航需要的移动距离）

这只是一个大概的估计值，因为实际路线会根据具体情况进行优化，类似前面提到的只剩一行时我们不需要再每次移动都拍摄，因此该算法的具体表现需要等实现后通过数据测试才能确定，在此按下不表。

方案二：“S”型路径优化方案

方案一中虽然我们尽可能的压低移动距离，但是造成了大量的拍摄信息浪费，相比理想的拍摄次数MN/5提高到了MN/3，拍摄次数同比增幅为66.7%，也就是说比理想情况下的拍摄次数多了一半左右，我们需要想办法优化飞行路线，降低拍摄次数。这里我们想到前面的“十字拼图”中的第二种方案，其大致也是遵循先遍历某个方向，因此我们可以尝试用这种拍摄方式对第一种方案做优化，减少重复的拍摄次数。我们发现第二种拼图的方式在行或列的遍历中实际上只能保证两行或两列的有效覆盖范围，因为我们只能取其与矩形形状相交的部分，而不规则的位置同样是存在重复拍摄或信息损失的。所以我们可以先尝试用这种方式来遍历上面的地图，通过遍历的结果再来总结有哪些可以优化的方面。

以下给出方案二的航行路线图：

方案二路线图

这里先解释一下无人机的移动规则，因为存在无人机移动至地图之外的情况，可能大家会存在疑惑，这里可以理解为为了遵循航行规则的统一性而做出的设定，毕竟无人机在空中航行时并没有飞行边界的限制，当无人机的拍摄范围内的五个位置包含M×N这个地图上的任意一个坐标时我们就认为这次拍摄是有意义的，这一点对于算法的设计尤为重要。

首先我们从地图的左上角起飞，以每两列为遍历单元，每次移动向着列的另一边移动行1步和列2步，而行的1步是方向交替的（口述起来比较复杂，相信大家看图可以一目了然），我们需要注意在两列遍历完成后下一次折返时逆向遍历下一个两列。由于我们不确定整个地图的长宽是多少，因此可能出现下一次的移动位置位于整个地图之外的情况，这里前面也有解释，这时只要无人机还能拍摄到地图内的区域我们就完成拍摄操作，例如图中的S8和S17位置。

从上图中来看似乎我们的优化没有起到减少拍摄次数的作用，方案一最终拍摄17次，方案二也是17次，其实不然，方案一我们是进行了优化的，最后一行只拍摄了3次，而方案二中最后一列并没有优化而是遵循了既有的路线规则。其实换个角度考虑如果我们将地图范围稍作修改增加一行或一列（其实没有什么差别，都是7×8的地图范围），那么我们再来看，对于方案一来说就无法再进行优化，最后一列需要从头拍摄到尾，累计拍摄总和21次；而对于方案二呢，我们会发现增加的这一列元素已经完全被当前已有的拍摄次数所覆盖了（观察S13至S17的拍摄范围即可）。因此我们的优化方案是起到了一定减少拍摄次数的效果的，但具体的评估还是需要最终用不同量级的数据测试后观察。

方案三：螺旋航行拍摄方案

现在我们先来分析一下方案二存在的问题，虽然相比方案一已经有效提升了拍摄的效率但是仍然存在信息的重复和损失，并且从初始的位置就损失了两个单位的信息，S8位置甚至一次拍摄丢失了四个单位的位置信息；而重复信息的情况例如S2和S6之间、S7和S9之间都存在两个单位的信息重复。虽然我们已经分析过拍摄过程中无法避免拍摄的信息重复和信息丢失情况，但是我们考虑能否将这种情况尽可能的延后至整个巡航过程的最后阶段，即我们优先收集最有效的信息，最后再将边界位置没有收集到的坐标信息查漏补缺的拍摄一遍。

这里我们就可以利用到“十字”拼图中的第三种方案，以这种螺旋的方式逐步收集到一定范围内的元素，这种飞行路线可以从某一个点开始向四周辐射，并且在拍摄的过程中保证不会出现信息的重复拍摄，那么我们在选择起飞位置的时候，越靠近整个地图的中间位置在向周围辐射的过程中就不会出现失衡的情况，即辐射的范围和原本的地图区域是中心对称的，不会出现一边还可以每次收集五个有效坐标信息，相对的另一边已经五个位置都扩展到了整个地图之外，那么这样的移动和拍摄就没有意义了。

下面我们给出方案三的航行路线图：

方案三路线图

相较于第二种飞行路线，这种航行的路线更加复杂，下面我们来分析一下。首先无人机选择从整个地图的中心位置起飞，以3步的步长为间隔进行拍摄，但是这3步的移动规则比较复杂，在尝试旋转移动时我们说在这种航行路线的移动是在水平方向和垂直方向上交替的进行1步和2步的移动，但是如果每走一步就更换移动的方向和步长顺序就会出现“十字”拼图示例中给出的第三种结构一样，只是在四个相邻的环中循环，无法扩大其拍摄范围。因此我们需要改变一定的规则，使得在旋转的过程中还能不断扩大拍摄的范围，从图中的路线来看可以这样描述移动的规则：

  • 存在四种固定顺序的移动模式，依次是向当前位置的右下（参考S1->S2），左下（参考S2->S3），左上（参考S3->S4），右上（参考S5->S6）方向移动3的步长
  • 初始改变移动模式的阈值为1，每一种移动方式移动达到阈值后更换下一种移动模式
  • 阈值会在每两次改变移动模式后加1

这是不进行任何优化的初始版移动规则，当然我们需要根据地图的实际情况来优化，由于螺旋辐射的过程中不可避免的最终无人机的移动位置会跳出地图的范围，和方案二的优化规则相同，我们出于统一算法的目的，跳过无人机拍摄范围完全跳出地图的情况（例如方案图中S9至S10之间就跳过一个按照原本规则应该包括的位置）。

从方案设计图的情况来看，最终依然进行和17次的拍摄才收集全了整个地图的位置信息，和方案二似乎没有出入，但是仔细观察这17次拍摄的覆盖范围就可以发现，如果将地图的长和宽都扩大一个量级至8×8的范围，那么目前的拍摄范围距离全部的地图信息只有4个遗漏的坐标信息分布在各个边上，换句话说我们只需要21次拍摄就可以完成对一个8×8范围的地图的信息收集。除此之外这种算法相比前两种方案还有三点优势，分别是

  1. 前期拍摄信息不重复
  2. 优先记录中心区域信息
  3. 最终拍摄完成的位置距起始飞行位置近

先来说第一点，前期飞行过程不会出现拍摄信息的重复意味着什么，还记得我们前面讨论存储空间的理想指标是多少吗？答案是Math.ceiling(M×N÷5)，虽然由于收集信息结构和地图的结构无法完美匹配导致了拍摄信息的重复和损失，但是我们一旦能够将拍摄信息重复和损失的情况延后，就能够在越早的移动范围内获取大量的地图区域信息，此时如果因为续航能力的不足或其他不可控因素导致要提前结束巡航过程，这种方案在信息的收集度上就有更大的优势。就以方案三的示例情况来看，我们仅仅截取前期的拍摄覆盖范围来看，如图所示：

方案三前期路线图

当从起飞开始9次拍摄接受时对整个区域信息的掌握情况已经达到了83.7%，这样的信息收集效率如果我们对地图的信息收集要求没有百分之百这么高的话，我们只使用了方案一和方案二的一般存储空间就逼近了前两种方案的信息量，足以看出这种方案的优势。

再来看第二点，优先获取地图中心区域的信息在实际情况中往往有着更强的意义，显然当我们希望对一个区域的地形情况或其他信息进行巡查时一定是更关心该区域的中心位置而非边界，除非需要对整个区域进行地毯式的搜索，那么不论我们选择从一边到另一边的遍历还是从中心到四周的遍历都是一样的，其余大部分情况下这种遍历方式都更具优势。

最后一点显然也很好理解，如果我们把整个螺旋扩展的过程看做一个近似的圆，那么总终返回起飞位置的返航距离一定只是一个半径长度，反应在矩形区域中就坐落在某个边长的一半到两条边之和的一半这两者的区间内；反观方案一和方案二，基本返航距离都是该方案的两倍左右。

架构设计

在我们实现上述的三种航拍算法之前先来思考一下整个代码的体系结构，因为面向对象的编程思想告诉我们，适当的抽象和封装可以使我们的代码实现有效的复用，并且具备足够的可读性。尤其是在这个案例中，天然的就具有无人机这个实体，我们所要设计的一切操作都是围绕这个实体，即使上面设计了三种不同的飞行航线，其中依然用到了无人机的相同行为，例如飞行，拍摄和返航等。因此我们先对整个代码的结构做如下规划：

代码类图

其中，我们遵循面向对象的编程思想，将无人机抽象为IDrone接口，在接口中定义无人机的一系列行为，包含数据的初始化，移动，拍摄，返航等，而这些功能的具体实现方式实现在Drone类中。无人机的实体通过聚合的方式与航行算法抽象类PathStrategy类进行聚合，航行算法抽象类中包含两个航行算法相关的抽象算法：地图信息收集算法和地图信息还原算法，分别对应信息的输入和输出；同样的这两个方法的具体实现在具体航行算法的实现类中，正如上文我们设计了三种方案，分别对应三个实现类，其中MinMoveStrategy对应最短移动路径方案，STypePathStrategy对应“S”型路径优化方案，SpinPathStrategy对应螺旋航行拍摄方案。这样设计，即使后期我们有了新的航行算法，也可以简单的通过类的继承实现代码的复用，具有较强的可扩展性。最后客户端和算法抽象类之间具有关联关系，当客户端调用相应的航行算法进行地图信息的输入输出时，传入地图对象初始化好的无人机对象，选择所采用的航行算法即可得到结果。

下面我们来看一下整个算法最终版的代码体系结构：

代码类图

可以看到主体的架构和我们上述分析的保持一致，同时为了功能的完整性，规范性和更进一步的可扩展性我们增加了部分代码，体现在以下几个方面：

  1. 增加IO工具类，将算法中需要输出信息的部分功能进行抽象，主要包括输出航行日志信息和输出最终的地图信息，这样做的好处是后期便于我们希望实现多渠道的信息输出时，只需要扩展该工具类的功能，就可以将信息输出至本地文件、网络等其他渠道中；
  2. 使用策略模式对无人机航行算法进行了抽象和封装，降低了客户端在调用算法接口时的耦合性，由于客户端在使用某种算法时并不关心算法的细节，因此我们应该尽可能的将算法相关的类和代码与客户端隔离，策略模式可以很好地帮助我们实现这一需求；
  3. 在代码中出现有限个情况选择时使用枚举类型代替字符串或数字，例如算法的选择，输出信息的种类等，增强代码的可读性和安全性。

算法实现

代码的具体实现囿于篇幅有限这里不全部列出，有兴趣的同学可以访问我的GitHub仓库进行浏览，这里给出链接。下面我就算法中几个重要的方法结合代码做一点讲解，首先是最短移动路径方案算法的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public int route(IDrone drone) {
        this.setDrone(drone);
        int m = drone.getMap().length, n = drone.getMap()[0].length;
//        deal just one line
        int index = 1, restAll = m * n;
        int[] xChange, yChange;
        if (m > n) {
            xChange = new int[]{3, 0, 3, 0};
            yChange = new int[]{0, m - 1, 0, 1 - m};
            drone.init(1, 0);
        } else {
            xChange = new int[]{0, n - 1, 0, 1 - n};
            yChange = new int[]{3, 0, 3, 0};
            drone.init(0, 1);
        }
        while (restAll > 0) {
            int tempX = drone.getCurX() + xChange[index];
            if (tempX >= n)
                tempX = n - 1;
            int tempY = drone.getCurY() + yChange[index];
            if (tempY >= m)
                tempY = m - 1;
            index++;
            index %= 4;
            if (tempX == drone.getCurX()) {
                if (tempY > drone.getCurY()) {
                    for (int i = drone.getCurY(); i <= tempY; i++) {
                        drone.move(tempX, i, false);
                        restAll -= drone.shoot(false);
                    }
                } else {
                    for (int i = drone.getCurY(); i >= tempY; i--) {
                        drone.move(tempX, i, false);
                        restAll -= drone.shoot(false);
                    }
                }
            } else if (tempY == drone.getCurY()) {
                if (tempX > drone.getCurX()) {
                    for (int i = drone.getCurX(); i <= tempX; i++) {
                        drone.move(i, tempY, true);
                        restAll -= drone.shoot(true);
                    }
                } else {
                    for (int i = drone.getCurX(); i >= tempX; i--) {
                        drone.move(i, tempY, true);
                        restAll -= drone.shoot(true);
                    }
                }
            }
        }
        drone.returnStart(true);
        return drone.getSumFeet();
    }

这里与最短移动路径相关的代码逻辑主要可以分为三个部分：

  1. 开始对地图矩形长宽的逻辑判断，目的是决定无人机的初始升空位置和遍历的方向顺序，这里选择的不同可能会影响最终无人机返航的路径距离。根据方案一中的推论，最终拍摄完成的位置如果和初始升空位置在同一侧，那么只需要移动大约一条边的距离即可返航，而如果不在同一侧则需要移动两条临边的距离才能返航，那么我们总是选择先遍历较长的边，即可在最终返航时只需要移动单边的情况下移动短边的距离返回初始位置；
  2. 中间循环部分，这里我们判断循环结束的条件是剩余未拍摄到的坐标个数不大于0，其他两个算法中的判断航拍任务是否完成也是采用该指标，这样的优点是保证了题目要求的收集完备整个地图中的地形信息，而实现方式也比较容易，即通过在无人机的初始化阶段通过判断地图的大小确定整个地图中需要收集的坐标个数，同时在拍摄过程中记录已经拍摄过的坐标位置，每次拍摄都返回当前新获得坐标信息个数即可。而该算法中我们基本上是每次移动都要进行拍摄的，因此我们先确定当前方向的遍历最终停下的位置，然后通过循环这些坐标来每次移动都进行拍摄，需要注意的点在于地图边界的判断和越界规避；
  3. 最后则是无人机的返航部分，通过调用已经封装好的返航方法完成。

下面给出“S”型路径优化方案算法的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int route(IDrone drone) {
        this.setDrone(drone);
        int m = drone.getMap().length, n = drone.getMap()[0].length;
        drone.init(0, 0);
        int nextX = 0, nextY = 0, restAll = m * n;
        int[] xChangeColumn = {2, 2}, xChangeRow = {-1, 1};
        int[] yChangeColumn = {1, -1}, yChangeRow = {2, 2};
        int columnIndex = 0, rowIndex = 0;
        while (restAll > 0) {
            restAll -= drone.shoot(true);
            if (restAll == 0)
                break;
            int tempX = nextX + xChangeColumn[columnIndex % 2];
            int tempY = nextY + yChangeColumn[columnIndex % 2];
            columnIndex++;
            if (valuable(tempX, tempY, m, n)) {
                nextX = tempX;
                nextY = tempY;
                drone.move(nextX, nextY, true);
            } else {
                nextX += xChangeRow[rowIndex % 2];
                nextY += yChangeRow[rowIndex % 2];
                rowIndex++;
                columnIndex++;
                xChangeColumn[0] = -xChangeColumn[0];
                xChangeColumn[1] = -xChangeColumn[1];
                drone.move(nextX, nextY, true);
            }
        }
    	drone.returnStart(true);
        return drone.getSumFeet();
    }

该算法的实现与方案一的代码结构类似，但是由于这一算法的移动规则比较复杂，因此没有引入优先遍历方向的判断，所以可以看到该算法中无人机固定从左上角起飞，在当前位置拍摄后，如何确定下一次的拍摄位置是该算法的难点，我们可以看到循环中有一个valuable的方法，这是所有航拍算法的父类PathStrategy类中的一个非抽象的protected方法，因此仅供其子类使用，作用是判断某个位置是否可以拍摄到整个地图中的信息，方法实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
     * judge if current location could shoot message in valuable map
     *
     * @param x
     * @param y
     * @param m
     * @param n
     * @return
     */
    protected boolean valuable(int x, int y, int m, int n) {
        boolean value = false;
        int[] xChange = {0, -1, 0, 1, 0};
        int[] yChange = {0, 0, 1, 0, -1};
        for (int i = 0; i < 5; i++) {
            int tempX = x + xChange[i];
            int tempY = y + yChange[i];
            if (tempX >= 0 && tempX < m && tempY >= 0 && tempY < n) {
                value = true;
                break;
            }
        }
        return value;
    }

了解了该方法的作用再回头看原方法的代码逻辑，就能明白我们在列方向遍历和移动的过程中一旦出现越界“严重”（即拍摄不到有用信息）的情况，就需要进行行方向的移动，除此之外列方向下一次的移动顺序和之前要完全相反。这也是代码中变量命名tempX和tempY的用意，即我们在原规则的基础上试探性的进行一次列方向的移动，而无人机是否最终进行该移动，取决于是否可以拍摄到有价值的信息；而一旦无法拍摄到有价值的信息，我们就要在原位置的基础上进行行移动，所以这是一个以列移动为主、行移动为辅的移动顺序。其余的判断循环结束条件和无人机返航的逻辑与上一个方案相同。

最后我们来看螺旋航行拍摄方案算法的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int route(IDrone drone) {
        this.setDrone(drone);
        int m = drone.getMap().length, n = drone.getMap()[0].length;
        int startX = (m - 1) / 2 - 1, startY = (n - 1) / 2;
        startX = startX < 0 ? 0 : startX;
        startY = startY < 0 ? 0 : startY;
        drone.init(startX, startY);
        int[] xChange = {1, 2, -1, -2};
        int[] yChange = {2, -1, -2, 1};
        int index = 0, restAll = m * n;
        int nextX = startX, nextY = startY;
        while (restAll > 0) {
            restAll -= drone.shoot(true);
            if (restAll == 0)
                break;
            int tempIndex = nextIndex(index++);
            nextX += xChange[tempIndex];
            nextY += yChange[tempIndex];
            while (!valuable(nextX, nextY, m, n)) {
                tempIndex = nextIndex(index++);
                nextX += xChange[tempIndex];
                nextY += yChange[tempIndex];
            }
            drone.move(nextX, nextY, true);
        }
        drone.returnStart(true);
        return drone.getSumFeet();
    }

该算法的代码逻辑相比之前两个方案要清楚得多，一方面是因为这个算法的移动规则比较统一，不需要像之前的算法方案要进行各种逻辑判断，另一方面也是因为对该算法的封装程度较高。我们先来看算法的整体流程，首先不同于前面的算法，这里会根据整个地图的大小对无人机的初始位置进行计算，并将计算的结果做越界检查；其次我们依然要确定每次无人机的移动方向，正如方案三所分析的那样，虽然螺旋式的拍摄只有四种移动方式，但四种移动方式的交替顺序是按一定规则变化的，这就是代码中nextIndex方法对这一规则所做的抽象，因为移动方式的排列次序是确定的，只是无法按照每次交替的规则，所以我们将下一次的移动次数作为参数皆可以获得移动的方式，该方式的实习如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
     * find next move direction
     *
     * @param index
     * @return
     */
    private int nextIndex(int index) {
        int floor = (int) Math.floor(Math.sqrt(index));
        int base = floor % 2 == 0 ? 3 : 1;
        int odd = index - floor * floor;
        if (odd >= floor) {
            index = (base + 1) % 4;
            return index;
        }
        return base;
    }

该算法通过当前移动的次数确定下一次移动的方式在移动方式数组中索引下标，了解了这个方法的含义，其余代码或多或少在前面也有所提及，这里不再赘述。

算法测试

最后我们结合之前给出的部分指标进行算法性能的评估，主要包括以下指标：

  • 累计路径
  • 累计拍摄次数
  • 理想路径
  • 无损拍摄次数
  • 路径比
  • 有效信息比

在用于测试的数据量级上，囿于机器性能有限，我们从个位数的地图尺寸大小开始，每次增加指数级别的大小，直到地图的边长到达三位数。

方案一

地图大小 初始位置 累计路径 理想路径 累计拍摄 无损拍摄 有效信息比
3×3 (0,1) 4 6 3 2 66.7%
5×5 (0,1) 14 15 12 5 41.7%
9×9 (0,1) 44 57 31 19 61.3%
17×17 (0,1) 126 174 112 58 51.8%
33×33 (0,1) 444 654 383 218 56.9%
65×65 (0,1) 1534 2535 1472 845 57.4%
129×129 (0,1) 5884 9987 5631 3329 59.1%

通过对方案一进行测试，我们可以看出最短移动路径算法“名副其实”，随着问题规模的扩大，累计路径和理想路径的相差越来越大，当数据规模达到三位数后该算法的实际所需累计路径将近节省了50%（以理想路径做参照），而相应的也付出了一定的存储空间代价，随着数据量级的增大，有效信息比最终稳定在60%左右这个区间，也就是说平均来看每次拍摄地图信息可以收集到3个新的坐标信息，表现基本及格，性能还需要和之后的两个算法进行对比再下定论。

方案二

地图大小 初始位置 累计路径 理想路径 累计拍摄 无损拍摄 有效信息比
3×3 (0,0) 12 6 4 2 50.0%
5×5 (0,0) 32 15 9 5 55.6%
9×9 (0,0) 88 57 25 19 76.0%
17×17 (0,0) 272 174 81 58 71.6%
33×33 (0,0) 928 654 289 218 75.4%
65×65 (0,0) 3392 2535 1089 845 77.6%
129×129 (0,1) 12928 9987 4225 3329 78.8%

通过对比方案二的测试结果就可以看出方案一在移动距离上的优势，但是方案二的有效信息比相比方案一就有了显著提高，随着数据量级的增大最终稳定在77%左右这个区间，相比方案一的有效信息比提高了15%。

方案三

地图大小 初始位置 累计路径 理想路径 累计拍摄 无损拍摄 有效信息比
3×3 (0,1) 12 6 4 2 50.0%
5×5 (1,2) 38 15 9 5 55.6%
9×9 (3,4) 94 57 24 19 79.2%
17×17 (7,8) 278 174 71 58 81.7%
33×33 (15,16) 996 654 244 218 89.3%
65×65 (31,32) 3870 2535 897 845 94.2%
129×129 (63,64) 14734 9987 3432 3329 97.0%

最后我们来看方案三的测试结果，我们欣喜地发现随着问题规模的扩大，有效信息比不断攀升，当上升至三位数时有效信息比已经达到95%以上，这说明该算法对存储空间的利用率已经接近了百分之百。但是相应的该算法也相比方案二付出了更多的路径长度，方案二中以理想路径为参考每次拍摄间隔需要多移动约0.3步，而方案三中需要多移动约0.45步，而方案一中不是以3步的步长为一次拍摄间隔故不做对比。

方案三相比方案二的另一个隐患在于我们都是使用临边相等的矩形地图来测试，对于方案一和方案二这种与地图临边平行的移动方式，地图的临边是否相等是不受影响的；但这种地图结构天生适用于螺旋式的遍历过程，如果临边长度不相等，该算法的性能又如何呢，下面我们以一定的増长速度扩大临边之间的差距，再来测试一下该算法的性能表现：

地图大小 初始位置 累计路径 理想路径 累计拍摄 无损拍摄 有效信息比
5×10 (3,2) 76 30 16 10 62.5%
5×15 (6,2) 126 45 23 15 65.2%
5×25 (11,2) 258 75 37 25 67.6%
5×40 (18,2) 532 120 58 40 69.0%
5×50 (23,2) 764 150 72 50 69.4%

果不其然，当临边不相等时该算法的性能有了明显的下降，有效信息比最终稳定在70%这个区间，相比方案二还低了10%左右，所以可以看出方案三的适用条件是有一定局限性的。

总结

综上所述，我们将三种算法测试下来，可以得出并没有任何一种算法在各个层面都可以做到性能最优，每一种算法都有其合适的使用场景，方案一适用于对移动路径距离敏感的场景，例如续航能力一般但内存空间容量大的无人机；方案三正好相反，适用于对存储空间敏感的场景，但是方案三又需要地图的临边差距较小，接近于正方形；方案二则是一个在各个性能指标上比较折中的算法，适用场景比较广泛，时间和空间的性能也比较优良，是大多数场景中推荐使用的无人机航拍算法。

坚持原创技术分享，您的支持将鼓励我继续创作！