找回密码
 欢迎注册
查看: 140|回复: 4

[讨论] 简化的赛车游戏

[复制链接]
发表于 2024-5-11 14:12:28 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

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

1、赛道如下图所示:

1.png

假设每个格子是1平方米

2、起点、终点:

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

3、行车规则:

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

问:

(1)应如何操纵赛车,才能在遵守行车规则的前提下,到达终点所需的用时最短?这个最短的用时是多少秒?
(2)如果换成规模更大的赛道,应如何编写程序,读入赛道,输出最佳的操作序列和最短用时?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-5-11 15:04:35 | 显示全部楼层
这个离散化一下结果如何?时间作为目标函数感觉不好分析。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 7 天前 | 显示全部楼层
把时间离散化成0.25秒,让加速度每0.25秒变化一次,模拟退火算法的求解结果如下:

2.png

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

3.png

这个加速度的操作序列好像没啥规律。不知道把时间分得更细之后,结果会怎样呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 4 天前 | 显示全部楼层
把时间分的更细,每0.125秒为一个时间段,让加速度每0.125秒变化一次,模拟退火算法的求解结果如下:

2.png

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

3.png

这个加速度的序列好像还是没啥规律,可能还没有优化到最佳成绩
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 4 天前 | 显示全部楼层
由于模拟退火算法难以找到最优解,于是换成粒子群算法(把时间步长恢复到0.25秒),求解结果如下:

2.png

最快到达终点的那辆赛车,每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弧度的最优解

接下来逐渐调低旋转加速度方向的幅度,多次重新求解,就能找到加速度方向精度更高的最优解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-5-19 02:47 , Processed in 0.074892 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表