我做了这个练习，但无法弄清楚它背后的算法：
你有一辆汽车默认以速度n（即每秒n米）行驶。你把最短的路线带回家（你已经知道了），但过了一些红绿灯。每个交通灯T具有周期p，这意味着在每p秒之后交通灯开启。 （例如，周期为3，光线在第3,6,9,12等时为绿色，红色为1,2,4,5,7,8等。）所有之间也有距离交通信号灯，用d表示。
例如：汽车不断以每秒1米的速度行驶。第一个红绿灯的距离为5.其周期为3.意味着您在时间= 5到达那里并且必须等待1秒才能使灯变绿。您在时间= 6时返回旅程。
现在还有一件事：你也可以使用速度为m的涡轮增压器（总是大于或等于n），但只能使用x次。涡轮增压器将保持两个交通灯之间的整个距离。因此，在示例中，它将保持在5或20，并导致2.5或10秒的持续时间。
您必须返回从您所在位置到您家的最短时间。输入将是： 交通灯的数量|您可以使用涡轮增压器的次数（x）|正常速度（n）|涡轮转速（m） 距交通灯1（Td）|交通灯期1（Tp） 到红绿灯的距离2（Td）|交通灯期2（Tp） 等等
例如： 2 1 1 2 5 3 20 2
这将给出16的最短时间。（时间从汽车离开时开始，到完成时结束。）
这背后的算法是什么？你必须检查每一个可以运行的时间吗？
我希望你能帮助我。
编辑我有一种计算时间的方法，没有选择使用turbo： 对于每个红绿灯，我创建一个Pair（int length，int period）。默认情况下，时间设置为0。交通灯之间的计算方法是：
int i = 0;
int time = 0;
while(i<S.size()-1) {
Pair current = S.get(i);
time = time + Math.ceil(current.getLength() / n);
time = current.getPeriod * ceil(time / current.getPeriod());
i++;
}
return time;
但是必须有办法找到何时使用涡轮增压器？
一个纪元可以通过你可以使用你的turbo x_t，剩余距离d_t和t的次数来表征。 t modulo所有时期的ppcm也会这样做，但我不认为你会得到很大改善。
从那里你可以使用A *算法（wikipedia）和以下启发式：
h(d_t, x_t, t) =
if (m*x_t <= d_t)
ceil(d_t/m)
else
ceil((d_t-(x_t*m)) / n)
请注意，考虑到灯光的状态，您可以更聪明。重要的是永远不要高估最优成本。如果您的启发式算法有效，算法将基本上尝试各种可能性，同时修剪不如当前最佳解决方案的所有内容。
所以这里有一个“愚蠢的，递归的蛮力”（在评论中提到，只有一个优化切断次优分支）解决了JavaScript中的问题（虽然原始标记是Java，但是允许运行代码）。我只是将每个灯的绝对位置放在一起，以简化输入处理，而不是“与交通灯的距离”。此外，在时间0开始所有灯光循环并不像每个灯光在指定时刻开始并且具有不相等的活动/不活动间隔（诸如灯光＃1从第1秒开始，保持活动3秒，然后熄灭）持续5秒，然后重复3 + 5个循环）。
"use strict";
class Light {
constructor(at, interval) {
this.at = at;
this.period = interval;
}
isRed(time) {
return Math.floor(time / this.period) % 2 !== 0;
}
};
class Car {
constructor(boosts, position = 0, speed = 0, time = 0, prev = null) {
this.position = position;
this.speed = speed;
this.boosts = boosts;
this.time = time;
this.prev = prev;
}
visits(position) {
return position >= this.position && position <= this.position + this.speed;
}
stop() {
return new Car(this.boosts, this.position, 0, this.time + 1, this);
}
resume(resumeSpeed) {
const speed = (this.speed === 0) ? resumeSpeed : this.speed;
return new Car(this.boosts, this.position + speed, speed, this.time + 1, this);
}
tryBoost(boostSpeed) {
return (this.boosts > 0 && this.speed < boostSpeed) ?
new Car(this.boosts - 1, this.position + boostSpeed, boostSpeed, this.time + 1, this) :
null;
}
withTrace(enabled = false) {
if (enabled) {
const trace = [];
for (var c = this; c !== null; c = c.prev)
trace.push([c.time, c.position, c.speed]);
trace.reverse();
console.log(
"time :" + trace.map(x => x[0].toLocaleString('en-US', {minimumIntegerDigits: 2})) +
"\npos :" + trace.map(x => x[1].toLocaleString('en-US', {minimumIntegerDigits: 2})) +
"\nspeed:" + trace.map(x => x[2].toLocaleString('en-US', {minimumIntegerDigits: 2})));
}
return this;
}
};
const problem = {
turboSpeed: 2,
normalSpeed: 1,
boosts: 1,
lights: [
new Light(5,3),
new Light(25,2)
],
findRedLight : function (car) {
return this.lights
.filter(x => x.isRed(car.time) && car.visits(x.at))[0];
},
distance: 0,
bestTime: Number.MAX_SAFE_INTEGER,
findBestTime: function (car) {
if (car.time > this.bestTime)
return Number.MAX_SAFE_INTEGER;
const distanceLeft = this.distance - car.position;
if (distanceLeft <= 0)
return car.withTrace(true).time;
const scenarios = [];
const redLight = this.findRedLight(car);
if (redLight)
scenarios.push(car.stop());
else {
scenarios.push(car.resume(this.normalSpeed));
const boosted = car.tryBoost(this.turboSpeed);
if (boosted)
scenarios.push(boosted);
}
const shortestTime = scenarios.map(args => this.findBestTime(args))
.reduce((a, b) => Math.min(a, b));
this.bestTime = Math.min(this.bestTime, shortestTime);
return shortestTime;
}
};
problem.distance = problem.lights
.map(x => x.at)
.reduce((x, y) => Math.max(x, y));
const t = problem.findBestTime(new Car(problem.boosts));
console.log("Best time: " + t);