粒子羣優化

Question

我在使用PSO算法解決流量問題時有一個問題。 假設我們有n輛車（這裏僅限於四輛車），這些車輛具有相同的目的地。 （假設我們知道他們的位置（x，y）） D：起始城市和目的地之間的距離。 d：在氣體用盡之前它可以行駛的最大距離。 D >> d：每輛車必須加油N次，N = D/d 每輛車應該遵循的路徑是不確定的。 任務： 我們正在尋找最少的加油站數量，以便每輛車都不會發生故障（因爲氣體當然）。加油站的數量是多少？它們的位置是多少？

Answer 1

我相信你可以用你的標準Dijkstra搜索算法解決這個問題，只需稍微增加。

首先將您的起點設置爲硬編碼位置。像平常一樣進行Dijkstra搜索，記下您遇到的加油站，但現在有點忽略它們。儘量到達目的地，不要停止使用天然氣，但要取消搜索所有節點的燃氣。現在，如果你到達目的地而沒有用完天然氣，那麼這是最短的路徑，並且它沒有氣體停止。但是，如果您確實用盡了氣體，那麼將起始點（和起始距離）設置爲您在上一次搜索中找到的加油站，因此現在您有多個潛在起點。然後它只是重複。如果您再次未能到達目的地，則從您在上次搜索中找到的所有加油站開始搜索。

保持這樣做直到您從上一個查詢中的所有起點到達目的地。理清距離並選擇最短路徑。

現在，如果你到達一個停止加油站並未能到達最終目的地的階段，那麼在沒有用完天然氣的情況下，沒有可能的路線通往最終目的地。