CODEWITHSUNDEEP
algorithmshortest-pathpath-finding
Jose
Jose

Reputation: 123

Optimal ant colony location algorithm

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

Image of example 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?

Upvotes: 12

Views: 671

Answers (2)

tofi9
tofi9

Reputation: 5853

Some optimisations based on a brute-force approach:

  • Keep track of the shortest distance, and stop calculating any sum of shortest paths that exceeds

  • If the Manhattan distance (delta(x) + delta(y)) is longer than the shorted distance ever recorded, stop calculating

  • Combined with the Manhattan distance optimisation: start in the centre of the board or the centre the food packets and work yourself inside-out. The optimal location is more likely to be somewhere in the middle

  • Reduce your search domain to the area between the food packets (i.e. from [1,1] to [6,7], rather than [0,0] to [7,7])

  • Nikunj's optimisation

Further, if your board is really huge, an optimisation solver might be able to reduce the number of calculations. However, your problem seems to be a non-convex problem, and many solvers have issues solving those.

Upvotes: 0

Nikunj Banka
Nikunj Banka

Reputation: 11365

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.

Upvotes: 2

Related Questions