问最优蚁群定位算法

EN

是的，您的算法可以工作，但您可以优化它的情况下，当食品包的数量，<<的方块数在网格中。例如：在上面的图表中。

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

最后，距离数组将包含蚁群捕获网格上所有食物包所必须做的工作量。将蚁群放在最小值的广场上。

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

在评论中，taoufiq给出了对算法的另一个明显的优化。即。到目前为止，停止计算任何超过最短距离的最短路径之和。

希望这是有用的。

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

• 跟踪最短距离，停止计算超出的任何sum of shortest paths
• 如果曼哈顿距离(delta(x) + delta(y))比记录的短距离更长，停止计算
• 与曼哈顿的距离优化相结合:从董事会或中心的中心开始，把食物包放在里面，然后从内部开始工作。最佳的位置更可能在中间的某个地方。
• 将搜索域缩小到食物包之间的区域(即来自[1,1] to [6,7]，而不是[0,0] to [7,7])
• 尼库尼优化

此外，如果你的板真的很大，一个优化求解器可能会减少计算的数量。然而，你的问题似乎是一个非凸问题，许多求解者都有解决这些问题的问题。