简化的赛车游戏

KeyTo9_Fans

经过简化的赛车游戏设定如下：

1、赛道如下图所示：



假设每个格子是1平方米

2、起点、终点：

起点如上图红点所示，位于左上角正方格上边的中点；终点是一条线段，位于左下角，如上图的红线所示。

3、行车规则：

（1）赛车被简化成了一个点
（2）赛道没有墙，赛车在到达终点前，一旦驶出灰色区域（驶入白色区域），即为挑战失败，成绩（用时）记为无穷大
（3）赛车的初速为0，可以以任意速度到达终点，即使到达终点后驶出灰色区域，成绩依然有效
（4）任何时候，赛车的加速度大小都不能超过1米每平方秒，加速度的方向可以瞬间改变成任何方向，加速度的大小可以瞬间改变成1米每平方秒以内的任何大小

问：

（1）应如何操纵赛车，才能在遵守行车规则的前提下，到达终点所需的用时最短？这个最短的用时是多少秒？
（2）如果换成规模更大的赛道，应如何编写程序，读入赛道，输出最佳的操作序列和最短用时？

mathe

这个离散化一下结果如何？时间作为目标函数感觉不好分析。

KeyTo9_Fans

把时间离散化成0.25秒，让加速度每0.25秒变化一次，模拟退火算法的求解结果如下：



成绩大概是10.55秒，加速度大小始终是1，加速度的方向如下图所示：



这个加速度的操作序列好像没啥规律。不知道把时间分得更细之后，结果会怎样呢？

KeyTo9_Fans

把时间分的更细，每0.125秒为一个时间段，让加速度每0.125秒变化一次，模拟退火算法的求解结果如下：



成绩大约是10.50秒，加速度的大小始终是1，加速度的方向如下图所示：



这个加速度的序列好像还是没啥规律，可能还没有优化到最佳成绩

KeyTo9_Fans

由于模拟退火算法难以找到最优解，于是换成粒子群算法（把时间步长恢复到0.25秒），求解结果如下：



最快到达终点的那辆赛车，每0.25秒的加速度在模拟退火的解的基础上，应分别增加

0.1*[0 0 0 0 1 0 1 1 -1 0 -1 0 1 0 1 -1 0 1 0 0 -1 1 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1]

弧度，它的成绩比模拟退火的成绩快0.02秒左右

粒子群算法的求解步骤如下：

在模拟退火得到的解的基础上，每一步都尝试 {逆时针旋转加速度方向0.1弧度、保持加速度不变、顺时针旋转加速度方向0.1弧度} 这3种方案

于是理论上：

经过第1步的模拟，原来的1辆赛车就分身成3辆赛车
经过第2步的模拟，原来的3辆赛车就分身成9辆赛车
经过第3步的模拟，原来的9辆赛车就分身成27辆赛车
……
经过第n步的模拟，原来的3^(n-1)辆赛车就分身成3^n辆赛车

就像从起点发射了一群粒子一样，哪个粒子最先到达终点，以后赛车就按它的路走，因此称为粒子群算法

但实际上，大部分粒子都撞墙后消失不见了，不再产生后续的分身，只有很小比例的粒子顺利到达了终点

接下来从存活的那些粒子里找出最先到达终点的那个粒子，学习它的操作序列，即可完成一轮优化

接下来不断重复上述步骤，就能找到加速度方向精度为0.1弧度的最优解

接下来逐渐调低旋转加速度方向的幅度，多次重新求解，就能找到加速度方向精度更高的最优解

#####

将旋转加速度方向的幅度从0.1逐渐调低至0.0001，多次重新求解

结果成绩提高到10.46秒后就难以提高了

这个成绩对应的路线图如下：



这个成绩对应的加速度方向如下：



与模拟退火的操作序列相比，这个序列更光滑

KeyTo9_Fans

把时间分的更细，每0.125秒为一个时间段，让加速度每0.125秒变化一次，粒子群算法的求解结果如下：



最终成绩是10.41秒，比模拟退火的成绩好多了，加速度的方向如下：



这个加速度序列比模拟退火得到的序列光滑多了，唯一不能解释的现象是：

【当时间段长度是0.25秒时，加速度方向序列的尾部是平的，

但是当把时间段细分到0.125秒时，加速度方向序列的尾部是翘起来的】

我已经检查过了两组解，确实是最优解，已经没法继续调优了，所以我不知道该怎么解释上面这个奇怪的现象。

KeyTo9_Fans

楼上sxyjtd发贴问这道题和数学有什么关系（楼上sxyjtd的发贴可能被删除了），回复如下：

这是编程擂台板块：
----------------------------------------------
编程擂台 今日: 3 |主题: 283|排名: 22
版主: KeyTo9_Fans
■ 范畴：摆擂、攻擂，各显神通，源码or程序不限。
----------------------------------------------
这个板块是可以编程解决问题的

gxqcn

顶！

一看到这个问题，就觉得不简单，是个难得的好问题，只是还没找到相应特别好的解决方案。
楼主已做了不少创造性的工作，并分享出来，希望感兴趣者有能力者也参与到这个问题的讨论中来。