type
status
date
slug
summary
tags
category
icon
password
2019年研究生数学建模国赛的一些想法。

比赛时间

  • 开始:9月19日8:00 a.m.
  • 结束:9月23日12:00 a.m.
  • 时长:100小时整

比赛试题

  • A:典型的机器学习的题目
  • B:懒得看题
  • C:CV题,测距
  • D:汽车工况,数据处理题
  • E:全球变暖题,直接DNN?
  • F:多约束条件下的优化算法,看似好做(最终选择)

解法

第一问

  • 先对点集构建KD-Tree,方便后期搜索
  • 定义cost function使用进行搜索,权衡跳数和欧式距离
  • 从open set中取出cost值最小的节点并放入close set
  • 遍历邻近的节点,计算cost并更新垂直和水平误差,判断是否可达,可达节点放入open set
  • 搜索宽度,直接用KD-Tree查询当前节点的KNN,时间复杂度可以达到
  • 可以先对数据进行一遍预处理,计算每个点对之间到达的可能性
  • 可以根据当前的水平和垂直误差,来判断下一个选择的点是水平还是垂直校正点
  • 最后一步到达点的条件适当放宽

第二问

  • 方法同一,但是更换了cost function
  • 引入了最小转弯半径,两点之间的路径不能直接采用直线
  • 根据文献,这里计算了两点之间的Dubins曲线的长度
  • Dubins曲线计算参数
    • 当前坐标,方向角和攻角
    • 下一跳坐标,方向角和攻角
    • 最小转弯半径
  • 二维Dubins曲线的计算比较简单,现成的库函数比较多,不多做赘述
  • 三维Dubins曲线比较复杂,只在Github上找到零星几个勉强可用的代码
    • 本来想看论文手写的,但是看到各种LSR、RSR等情况判断还有复杂的几何计算,觉得在有限时间内实现不太现实,果断放弃
    • 老实说这里花费的代码时间比较多,花费了整整两天,近乎一半的比赛时间,事后回忆起来貌似有点得不偿失
    • 最后使用的代码还存在角度问题,会使生成的曲线不一定是最短的,本想改变一下角度进行多次计算取最优,但是经过实践发现跑一次杜宾斯曲线+都要花费仅半个小时,果断放弃
    • 虽然收敛的解和第一问的差别并不大
    • 题目规定的和点集的数量级相差太大,导致最终画出的曲线看起来像是折线段
[1] Owen M, Beard R W, McLain T W. Implementing dubins airplane paths on fixed-wing uavs[J]. Handbook of Unmanned Aerial Vehicles, 2015: 1677-1701.[2] Pharpatara P, Hérissé B, Bestaoui Y. 3D-shortest paths for a hypersonic glider in a heterogeneous environment[J]. IFAC-PapersOnLine, 2015, 48(9): 186-191.

第三问

  • 在第一问的基础上,引入随机因素
  • 计算出路径后使用蒙特卡洛来计算成功率
  • 第二题的数据,坏点大部分都集中在和之间的路径上,导致成功率和路径较难权衡
  • 玄学调参

赛后反思

  • 工欲善其事必先利其器,赛前没有做好充分准备,未提前熟悉官方的latex模板,导致赛时各种基于google的latex写作,尤其是图片插入,不知为什么从draw.io上导出的png图片无法直接插入,浪费了很多时间导致早上在通宵的状态下急忙赶稿,还有subfigure的问题
  • 别用Texpad!!!经过这次的比赛发现Texpad不适合快速写作,不能用Vim编辑是最大的痛点,以后直接上Visual Studio Code + Xelatex
  • 三人分工安排略有不均,论文开始时间较晚
  • 以后可以考虑用matlab
  • 队友如果不会latex的话以后还是直接上word吧
  • 保持充足的睡眠很重要,尤其不要通宵赶稿(但是感觉不太现实)

结果

果然拿铁了
《决战中途岛》有感日常吐槽
Loading...