最优蚁群定位算法

Question

假设有一个网格包含两个墙(被阻挡的单元格)以及放置在网格上任何位置的食物.

现在假设我们正在尝试确定将蚁群放置在该网格上的最佳位置,使得蚂蚁必须行进最小距离(在任何方向上往/来自群体的起始点)以获得最大量的食物.

到目前为止,我提出的最佳方法如下:

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

最后，距离数组将包含蚁群捕获网格上所有食物包所需要做的工作量。将蚁群放置在数值最小的方格上。

但请注意，这种方法的渐近复杂度与您在问题中给出的算法相同。

PS taoufiq 在评论中给出了对算法的另一个明显的优化。IE。停止计算超过迄今为止找到的最短距离的最短路径之和。

希望这有用。