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吧
-
结果
果然拿铁了
文章评论