最佳蚂蚁群定位算法

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

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

- Jose

---

优化的方法是跟踪最短距离，并停止计算任何超过“最短路径之和”的距离。 - tofi9

这里不清楚您想要优化的功能是什么。食物颗粒大小都一样吗？假设（0,0）处有一个颗粒，另一个颗粒在（4,0）。在（0,0）处（在颗粒上方，并距离另一个颗粒4个单位），还是在（2,0）处（两个颗粒之间的中心位置）建立殖民地更好？如果您将颗粒视为食品价值/距离，则第一个更好。如果您将颗粒视为食品价值-距离，则颗粒之间的所有位置都同样好。蚂蚁一次能搬回整个颗粒到殖民地吗？ - rob mayoff

@robmayoff 我认为“使蚂蚁行走的距离最短”是非常清晰的 - OP试图最小化一个特定点与所有包含食物的单元格之间距离的总和。 - The Paramagnetic Croissant

这真的不是很明显。如果你想要优化某些东西，你真的需要有一个数学表达式来进行比较。 - Novak

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

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

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

另外，taoufiq在评论中提供了另一个明显的优化方法。即停止计算任何超过当前找到的最短距离的最短路径之和。

希望这对你有用。

- Nikunj Banka

---

谢谢！我实现了这个算法（基于Lee算法寻找最短路径），它可以工作。 - Jose

Answer 2

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

• 跟踪最短距离，并停止计算任何超过最短路径之和的距离

• 如果曼哈顿距离（delta(x) + delta(y)）比记录的最短距离更长，则停止计算

• 结合曼哈顿距离优化：从棋盘中心或食物包中心开始，自内而外工作。最佳位置更可能在中间某处

• 将搜索域缩小到食物包之间的区域（即从[1,1]到[6,7]，而不是[0,0]到[7,7]）

• Nikunj的优化

此外，如果您的板子真的很大，优化求解器可能能够减少计算次数。然而，您的问题似乎是一个非凸问题，许多求解器在解决这些问题时会遇到困难。

- tofi9