KeyTo9_Fans 发表于 2024-5-11 14:12:28

简化的赛车游戏

经过简化的赛车游戏设定如下:一个有难度的最优解问题

1、赛道如下图所示:



假设每个格子是1平方米

2、起点、终点:

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

3、行车规则:

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

问:

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

mathe 发表于 2024-5-11 15:04:35

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

KeyTo9_Fans 发表于 2024-5-12 17:03:28

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



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



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

KeyTo9_Fans 发表于 2024-5-15 12:15:57

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



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



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

KeyTo9_Fans 发表于 2024-5-15 22:25:25

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



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

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 发表于 2024-6-2 10:18:53

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



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



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

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

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

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

KeyTo9_Fans 发表于 2024-6-2 16:00:30

楼上sxyjtd发贴问这道题和数学有什么关系(楼上sxyjtd的发贴可能被删除了),回复如下:

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

gxqcn 发表于 2024-6-2 21:18:32

顶!

一看到这个问题,就觉得不简单,是个难得的好问题,只是还没找到相应特别好的解决方案。
楼主已做了不少创造性的工作,并分享出来,希望感兴趣者有能力者也参与到这个问题的讨论中来。
页: [1]
查看完整版本: 简化的赛车游戏