Оптимальный алгоритм определения местоположения колонии 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

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