最优蚁群定位算法

Question

假设有一个网格，其中包含两面墙（被阻挡的单元格）以及放置在网格上任何位置的食物。

现在假设我们正在尝试确定在这个网格上放置蚁群的最佳位置，这样蚂蚁必须行进的距离最短（在任何方向 to/from 蚁群的起点）以获得最大量的食物。

到目前为止，我想出的最佳方法如下：

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

这种方法行得通吗？有没有更高效的解决方案？

Answer 1

是的，您的算法有效，但您可以针对 [食物包数量] << [网格中的方块数量] 的情况对其进行优化。例如。在上图中。

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 在评论中对您的算法进行了另一个明显的优化。 IE。停止计算任何超过目前找到的最短距离的最短路径之和。

希望这有用。

Answer 2

一些基于蛮力方法的优化：

跟踪最短距离，并停止计算任何超过

sum of shortest paths

如果曼哈顿距离(delta(x) + delta(y))比有记录的最短距离长，停止计算
结合曼哈顿距离优化：从棋盘中央或食物包中央开始，由内而外锻炼自己。最佳位置更有可能在中间的某个地方
将您的搜索域缩小到食品包之间的区域（即来自 [1,1] to [6,7]，而不是 [0,0] to [7,7]）
的优化

此外，如果你的电路板真的很大，一个optimisation solver也许可以减少计算量。但是，您的问题似乎是一个非凸问题，许多求解器都无法解决这些问题。

最优蚁群定位算法

Optimal ant colony location algorithm

algorithm

path-finding

shortest-path