如何在R中找到最短路徑

-1

問題：我有一組帶有Lat和Long信息的點的數據幀。我們需要從A開始，遍歷其他每個節點一次，並在任何時候結束。目標是儘量減少行駛的總半徑。如何在R中找到最短路徑

df <- data.frame("name" = c("A", "B", "C", "D", "E"), 
"lon" = c(-73.001, 23.231, 1.23, 115.40, -87.98), 
"lat" = c(40.21, 32.78, -34.30, 21.92, -12.2))

如果點數很大，則生成所有置換將不起作用。我試圖使用iGraph軟件包，但不知道如何解決這個問題。通過distm（gepsphere），我可以獲得所有距離矩陣，但我不知道如何繼續。

請幫我弄清楚如何做到這一點。我在R尋找解決方案。

來源

2015-12-27 sachinv

這不是旅行推銷員問題嗎？ –

正如@ 42已經提到的，這看起來像是一個旅行推銷員問題。所以你可以嘗試

library(TSP) 
library(geosphere) 
d <- distm(as.matrix(df[, -1])) 
tour <- solve_TSP(TSP(d, labels=df$name), 
        method="nearest_insertion", 
        control=list(start=1L)) 
labels(tour) 
# [1] "A" "D" "B" "C" "E"

來源

2015-12-27 21:20:51 lukeA

感謝您的回覆。我嘗試了各種方法，但我不能得到CDBAE這個命令，它似乎是總距離最短的路徑。通過將它們繪製在地圖上，這一路徑顯而易見。我們怎麼能得到這個？有任何想法嗎。 – sachinv

是這樣嗎？我必須承認，我不能通過眼睛來判斷大圓距離。檢查rownames（df）< - df $ name; tour_length2 < - function（x）{require（sp）; LinesLength（Lines（list（Line（df [x，c（「lon」，「lat」）]）），ID =「1」），longlat = TRUE）}; tour_length2（c（「E」，「A」，「B」，「C」，「D」））; tour_length2（c（「C」，「D」，「B」，「A」，「E」）） - 第一個似乎比你的「最佳」短。也就是說，如果措施是正確的。除此之外，你說你想從A開始？ – lukeA

感謝您的澄清。 – sachinv

如何在R中找到最短路徑

回答

相關問題