Optymalny algorytm lokalizacji kolonii mrówek

Question

Załóżmy, że istnieje kratka zawierająca obie ściany (zablokowane komórki) oraz żywność umieszczona w dowolnym miejscu na siatce.

Załóżmy teraz staramy się zdecydować optymalną lokalizację na miejsce kolonii mrówek w tej sieci, tak że mrówki muszą podróżować najmniejszą odległość (w dowolnym kierunku do/od punktu startowego kolonia), aby uzyskać maksymalną ilość jedzenia.

Dotychczas najlepszym podejściem mam wymyślić jest następujący:

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 

Czy podejście to jeszcze działa? Czy istnieje bardziej wydajne rozwiązanie?

Answer 1

Tak, Twój algorytm działa, ale możesz zoptymalizować go dla przypadku, gdy [liczba pakietów żywności] < < [liczba kwadratów w siatce]. na przykład. Na powyższym wykresie.

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 

W końcu macierz odległości będzie zawierać ilość pracy, że mrówka kolonia ma zrobić, aby uchwycić wszystkie pakiety żywnościowego na starcie. Umieść kolonię mrówek na placu o najmniejszej wartości.

Należy jednak zauważyć, że asymptotyczna złożoność tego podejścia pozostaje taka sama jak algorytm podany w pytaniu.

P.S Innym oczywistym optymalizacja do algorytmu została podana przez taoufiq w komentarzach. to znaczy. przestań obliczać każdą sumę najkrótszych ścieżek, która przekracza najkrótszą odległość znalezioną do tej pory.

Mam nadzieję, że to było przydatne.

Answer 2

Niektóre optymalizacje w oparciu o podejście brute-force:

• śledzić najkrótszej odległości, a zatrzymać obliczenia każdy sum of shortest paths że przekracza

• Jeśli odległość Manhattan (delta(x) + delta(y)) jest dłuższy niż Zredukowana odległość kiedykolwiek zarejestrowana, przestań obliczać

• W połączeniu z optymalizacją odległości na Manhattanie: zacznij od środka planszy lub środka paczki z jedzeniem i pracujcie od środka. Optymalna lokalizacja jest bardziej prawdopodobne, aby być gdzieś w środku

• Zmniejsz swoją domenę wyszukiwarki do obszaru pomiędzy paczkami żywności (czyli od [1,1] to [6,7], zamiast [0,0] to [7,7])

• Nikunj „s optymalizacji

Co więcej, jeśli twoja deska jest naprawdę ogromna, optimisation solver może być w stanie zmniejszyć liczbę obliczeń. Jednak twój problem wydaje się być problemem nie wypukłym, a wielu solverów ma problemy z ich rozwiązaniem.