最优蚁群定位算法

假设有一个网格包含两个墙（被阻塞的单元格）以及放置在网格上任何位置的食物。最优蚁群定位算法

现在假设我们正试图决定最佳的位置来放置蚁群在这个电网，使得蚂蚁有旅游的最小距离（在任何方向往/返的起点殖民地）获得最大数量的食物。

到目前为止，我已经想出最好的办法是：

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

最优蚁群定位算法

回答

相关问题