Optimal ant colony location algorithm

Question

Suppose there is a grid containing both walls (blocked cells) as well as food items placed in any location on the grid.

Now suppose we are trying to decide the optimal location to place an ant colony on this grid, such that the ants have to travel the least distance (in any direction to/from the starting point of the colony) to get the maximum amount of food.

So far, the best approach I've come up with is the following:

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

Would this approach even work? Is there a more efficient solution?

Answer 1

Yes, your algorithm works but you can optimize it for the case when [number of food packets] << [number of squares in the grid]. eg. In the above graph.

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

In the end the distances array would contain the amount of work that an ant colony has to do to capture all the food-packets on the grid. Place the ant colony at the square which has the smallest value.

But note that the asymptotic complexity of this approach remains the same as the algorithm you have given in the question.

P.S Another obvious optimization to your algorithm has been given by taoufiq in the comments. ie. stop calculating any sum of shortest paths that exceeds the shortest distance found till now.

Hope this was useful.