최적의 개미 식민지 위치 알고리즘

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 

이 방법도 작동합니다 : 지금까지

, 내가 함께 왔어요 가장 좋은 방법은 다음과 같다? 보다 효율적인 솔루션이 있습니까?

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 

결국 거리 배열은 개미 식민지가 그리드의 모든 음식 패킷을 캡처하기 위해해야하는 작업량을 포함하게됩니다. 개미 식민지를 가장 작은 값을 갖는 사각형에 놓습니다.

그러나이 접근법의 점근 적 복잡성은 질문에서 제공 한 알고리즘과 동일하게 유지된다는 점에 유의하십시오.

P.S은 알고리즘의 또 다른 명백한 최적화는 코멘트에 taoufiq에 의해 주어졌다. 즉. 지금까지 발견 된 최단 거리를 초과하는 최단 경로의 합계 계산을 중단하십시오.

희망이 유용했습니다.

Answer 2

일부 무차별 접근 방식을 기반으로 최적화 : 최단 거리의

• 보관할 트랙, 그리고 맨하탄 거리 (delta(x) + delta(y)가) 이상이면

• 을 초과하는 sum of shortest paths 계산 중지 기록 된 단락 거리

• 맨해튼 거리 최적화와 결합 : 보드의 중심 또는 중심 th에서 시작 음식물 쓰레기를 처리하고 몸 밖에서 일을하십시오. 최적의 위치는 음식 패킷 사이의 영역으로 검색 도메인을 줄 중간

• 어딘가에 될 가능성이 높습니다 (즉 [1,1] to [6,7]보다는 [0,0] to [7,7]에서)

• Nikunj의 최적화

또한 보드가 실제로 큰 경우 optimisation solver은 계산 수를 줄일 수 있습니다. 그러나 문제는 비 볼록 (non-convex) 문제인 것처럼 보이며 많은 해결사에서 문제를 해결합니다.