Оптимальный алгоритм определения местоположения колонии ant

Предположим, что есть сетка, содержащая обе стены (заблокированные ячейки), а также продукты питания, размещенные в любом месте на сетке.

Теперь предположим, что мы пытаемся определить оптимальное местоположение для размещения колонии ant на этой сетке, чтобы муравьи должны были проехать наименьшее расстояние (в любом направлении от/от начальной точки колонии), чтобы получить максимальное количество пищи.

До сих пор лучший подход, который я придумал, заключается в следующем:

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

Будет ли такой подход работать? Есть ли более эффективное решение?

Ответ 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

В конечном итоге массив расстояний будет содержать объем работы, который должна сделать колония ant, чтобы захватить все пакеты пищи в сетке. Поместите колонию ant на квадрат, который имеет наименьшее значение.

Но заметим, что асимптотическая сложность этого подхода остается такой же, как алгоритм, который вы задали в вопросе.

P.S Еще одна очевидная оптимизация вашего алгоритма была дана taoufiq в комментариях. то есть. остановите вычисление любой суммы кратчайших путей, которая превышает кратчайшее расстояние, найденное до сих пор.

Надеюсь, это было полезно.

Ответ 2

Некоторые оптимизации, основанные на подходе с грубой силой:

Следите за самым коротким расстоянием и прекратите вычислять любой sum of shortest paths, который превышает
Если расстояние Манхэттена (delta(x) + delta(y)) больше, чем когда-либо записанное короткое расстояние, остановите вычисление
В сочетании с оптимизацией расстояний на Манхэттене: начните в центре доски или в центре пакеты продуктов и сделайте себе наизнанку. Оптимальное местоположение, скорее всего, будет где-то посередине
Уменьшите область поиска в области между пакетами продуктов (т.е. от [1,1] to [6,7], а не [0,0] to [7,7])
Оптимизация Nikunj

Кроме того, если ваша плата действительно огромна, оптимизатор оптимизации может уменьшить количество вычислений. Однако ваша проблема, похоже, является непропускающей проблемой, и у многих решателей есть проблемы с их решением.