记算法竞赛工程题题解思路

今年参加了 CACC (CCF算法能力大赛) 和算法精英赛, 发现最近的比赛开始喜欢出工程题. 工程题和算法题不同, 工程题由于数据量极大, 参数极多, 关系复杂, 所以很难找到最优解, 需要通过各种巧妙的方法找到一个尽可能优的解. 常见的计分方式是给出一个没有任何优化, 纯粹暴力解决或顺序遍历的解作为基线, 其他解的得分均基于此基线进行换算.

工程题并没有最佳答案, 本文方法仅为自己个人思路, 一定存在更好的方法.

外卖配送 (算法精英赛)

题目

本题为无人机轨迹优化题, 简要题目描述如下:

在 x 轴上有 m 个城市, 每个城市里有多个不同高度的建筑 $(y_1, y_2, \cdot)$. 现有一无人机从任意一点起飞, 要求停经所有城市的任意一个建筑, 再飞回去. 无人机的能耗由上升斜率和移动距离组成, 当无人机下降时, 仅考虑移动距离能耗. 规划一条最佳线路使能耗尽可能少.

能耗可以表示为:

$$E = \frac{(1 - k) \cdot d}{D} + \frac{k * s}{S}$$

其中 $d$ 为路径距离, $s$ 为线路斜率, 当无人机下降时, $s$ 取 $0$. $k, D, S$ 为固定参数. 所有数字均为整数.

分析

首先由于固定线路后总路程与总上升斜率不变, 因此任意点作为起点都不影响能耗, 默认第一个城市为起点即可.

分析题意, 可以将其视为二维平面上的线路优化问题. 有若干个不重合点 $(x_i, y_i)$, 这些点的横坐标可能重复. 设计一条尽可能平稳的轨迹, 同时使路径尽可能短.

我直接将其视为路径规划问题来看待, 如上图所示, 显然第一步是找出最为平稳的点集, 第二步再规划顺序.

在路径规划阶段, 尝试遍历第一个城市的每个点作为起点, 执行:

1. 把当前点加入点集 $P$.
2. 计算点集 $P$ 的平均高度.
3. 指针移动到下一个城市, 并把最接近平均高度的点加入点集 $P$.
4. 回到第 2 步重复执行, 直到每个城市都遍历了一次

这样就可以得到一系列点集, 它们的起点分别是第一个城市的每个点. 然后通过计算方差, 最大落差等因素, 找出一个高度最集中, 最平稳的点集. 并且能够立即得到一条简单路径: 只需要按顺序连接点集 $P$ 中的点即可.

第二步, 使用 2-opt 方法, 随机反转一段路径, 看是否优. 如果是, 则直接替换当前路径; 如果不是, 则换一段路径, 重复执行直到不存在更优方法, 此时算法结束.

以下是伪代码和示意图:

1
2
3
4
5
6
7
8
9
10

needSwap = True // 需要进行交换 
while needSwap: 
    needSwap = False // 先置为False, 如果没有发生交换说明无法优化 
        for i in [2, 3, …, pathList.len-2]: 
            for j [i+1, i+2, …, pathList.len-1] 
                oldDis = Distance([i-1, i, i+1, …, j-1, j, j+1]) // 交换之前的路径距离
                newDis = Distance([i-1, j, j-1, …, i+1, i, j+1]) // 交换之后的距离路径 
                if newDis < oldDis: // 如果交换后距离更短 
                    swap(pathList, i, j)
                    needSwap = True // 产生了交换, 说明存在优化可能, 继续循环尝试

数据采集