粒子群优化算法

Question

在使用PSO算法解决交通问题时，我有一个问题。假设我们有n辆车(仅限于四辆车)，这些车都有相同的目的地。它们有不同的起点城市。(假设我们知道它们的位置(x，y)) D:起点城市和目的地之间的距离。d:它在耗尽汽油之前可以行驶的最大距离。D >> d:每辆车必须加N次油，N=D/d，每辆车应该遵循的路线是不确定的。任务:我们正在寻找最少数量的加油站，这样每辆车都不会抛锚(当然是因为汽油)。有多少个加油站，它们的位置是什么？

Answer 1

我相信你可以用你的标准Dijkstra搜索算法解决这个问题，只需要稍微增强一下。

首先将您的起点设置为硬编码位置。像往常一样搜索Dijkstra，注意你遇到的加油站，但现在有点忽略它们。尝试在不停下来加油的情况下到达目的地，但取消对所有可能用完汽油的节点的搜索。现在，如果你到达目的地而没有耗尽汽油，那就是最短的路径，而且它不需要加油站。

但是，如果汽油用完了，那么将起点(和起点距离)设置为您在之前的搜索中找到的加油站，因此现在您有多个潜在的起点。然后它就会重复。如果您再次未能到达目的地，请从上次搜索中找到的所有加油站开始搜索。

一直这样做，直到您从上一个查询中的所有起点到达目的地。计算距离并选择最短的路径。