2019年研究生数学建模国赛的一些想法。
比赛时间
-
-
结束：9月23日12：00 a.m.
-
比赛试题
-
-
B：懒得看题
-
C：CV题，测距
-
D：汽车工况，数据处理题
-
E：全球变暖题，直接DNN？
-
解法
第一问
- 先对点集构建KD-Tree，方便后期搜索
- 定义cost function使用$A^*$进行搜索，权衡跳数和欧式距离
- 从open set中取出cost值最小的节点并放入close set
- 遍历$k$邻近的节点，计算cost并更新垂直和水平误差，判断是否可达，可达节点放入open set
- 搜索宽度，直接用KD-Tree查询当前节点的KNN，时间复杂度可以达到$klog(n)$
- 可以先对数据进行一遍预处理，计算每个点对之间到达的可能性
- 可以根据当前的水平和垂直误差，来判断下一个选择的点是水平还是垂直校正点
- 最后一步到达$B$点的条件适当放宽
第二问
- 方法同一，但是更换了cost function
- 引入了最小转弯半径，两点之间的路径不能直接采用直线
- 根据文献，这里计算了两点之间的Dubins曲线的长度
- Dubins曲线计算参数
- 当前坐标$(x_i,y_i,z_i)$，方向角和攻角$(\varphi_i, \gamma_i)$
- 下一跳坐标$(x_i,y_i,z_i)$，方向角和攻角$(\varphi_j, \gamma_j)$
- 最小转弯半径$R_{min}$
- 二维Dubins曲线的计算比较简单，现成的库函数比较多，不多做赘述
- 三维Dubins曲线比较复杂，只在Github上找到零星几个勉强可用的代码
- 本来想看论文手写的，但是看到各种LSR、RSR等情况判断还有复杂的几何计算，觉得在有限时间内实现不太现实，果断放弃
- 老实说这里花费的代码时间比较多，花费了整整两天，近乎一半的比赛时间，事后回忆起来貌似有点得不偿失
- 最后使用的代码还存在角度问题，会使生成的曲线不一定是最短的，本想改变一下角度进行多次计算取最优，但是经过实践发现跑一次杜宾斯曲线+$A^*$都要花费仅半个小时，果断放弃
- 虽然收敛的解和第一问的差别并不大
- 题目规定的$R_{min}$和点集的数量级相差太大，导致最终画出的曲线看起来像是折线段
第三问
-
-
计算出路径后使用蒙特卡洛来计算成功率
-
第二题的数据，坏点大部分都集中在和之间的路径上，导致成功率和路径较难权衡
-
赛后反思
- draw.io上导出的png图片无法直接插入，浪费了很多时间导致早上在通宵的状态下急忙赶稿，还有subfigure的问题
-
别用Texpad！！！经过这次的比赛发现Texpad不适合快速写作，不能用Vim编辑是最大的痛点，以后直接上Visual Studio Code + Xelatex
-
三人分工安排略有不均，论文开始时间较晚
-
以后可以考虑用matlab
-
队友如果不会latex的话以后还是直接上word吧
-
结果
果然拿铁了
文章评论