最優蟻羣定位算法

假設有一個網格包含兩個牆（被阻塞的單元格）以及放置在網格上任何位置的食物。最優蟻羣定位算法

現在假設我們正試圖決定最佳的位置來放置蟻羣在這個電網，使得螞蟻有旅遊的最小距離（在任何方向往/返的起點殖民地）獲得最大數量的食物。

到目前爲止，我已經想出最好的辦法是：

for each square on the grid 
    use a shortest path algorithm to find the distance to/from each food source from this square 
    sum these distances to find a number and put the number in that square 
select the square with the smallest number

請問這種方法甚至工作？有沒有更有效的解決方案？

來源

2015-02-07 Jose

優化是跟蹤最短距離，並停止計算任何超過最短路徑的總和。 – tofi9 2015-02-07 06:33:33

目前還不清楚你想在這裏優化哪些功能。食物顆粒是否都是相同的大小？假設在（0,0）和（4,0）有一個粒子。（0,0）（在一個顆粒上面，另一個顆粒在4個單位上）或者在（2,0）上（兩個顆粒之間的中間位置）有個菌落？如果你認爲顆粒食物的價值/距離，第一個更好。如果您將顆粒作爲食物的價值 - 距離，顆粒之間的所有位置都同樣好。一隻螞蟻能在一次旅行中將整個小球帶回殖民地嗎？ – 2015-02-07 06:48:38

@robmayoff我認爲「讓螞蟻走得最遠」這一點非常清楚--OP正試圖將一個特定點與所有含有食物的細胞之間的距離總和最小化。 – 2015-02-07 10:45:18

是的，您的算法可以工作，但您可以針對[食物包數量] < < [網格中的平方數]的情況進行優化。例如。在上面的圖中。

distances = new int[ROWS][COLS]; 

for each food-packet on the grid 
    use a shortest path algorithm to find the distance to/from each square from this food-packet 
    accumulate the distances for each square in the 'distances' array

最後距離數組將包含蟻羣必須做的工作量，以捕獲網格上的所有食品包。將蟻羣置於具有最小值的正方形。

但請注意，此方法的漸近複雜度與您在問題中給出的算法保持不變。

P.S到你的算法另一個明顯的優化已經在評論taoufiq給出。即。停止計算超過迄今爲止發現的最短距離的任何最短路徑的總和。

希望這是有用的。

來源

2015-02-07 18:23:30

謝謝！我實現了這個算法（在Lee算法的基礎上尋找最短路徑），它可以工作。 – Jose 2015-02-08 04:34:59

基於蠻力方法的一些優化技術：最短距離的

跟蹤，並停止計算超過
如果曼哈頓距離（delta(x) + delta(y)）長於任何sum of shortest paths記錄的短距離，停止計算
結合曼哈頓距離優化：開始在棋盤中心或中心點e食品包裝，並從內到外工作。最佳位置是更可能是中間的某個位置
減少搜索域的食品包之間的區域（即從[1,1] to [6,7]，而不是[0,0] to [7,7]）
Nikunj的優化

此外，如果您的主板非常龐大，optimisation solver可能可以減少計算次數。但是，你的問題似乎是一個非凸問題，許多求解者都有解決這些問題的問題。

來源

2015-02-07 19:07:41 tofi9

最優蟻羣定位算法

回答

相關問題