Thuật toán vị trí địa lý kiến ​​tối ưu

Question

Giả sử có một lưới có chứa cả hai bức tường (ô bị chặn) cũng như các mặt hàng thực phẩm được đặt ở bất kỳ vị trí nào trên lưới.

Bây giờ giả sử chúng ta đang cố gắng để quyết định vị trí tối ưu để đặt một đàn kiến ​​trên lưới này, như vậy mà kiến ​​phải đi khoảng cách tối thiểu (theo hướng nào đến/từ điểm khởi đầu của thuộc địa) để có được lượng thức ăn tối đa.

Cho đến nay, phương pháp tốt nhất mà tôi đã đưa ra như sau:

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 

có phương pháp này thậm chí làm việc? Có giải pháp hiệu quả hơn không?

Answer 1

Có, thuật toán của bạn hoạt động nhưng bạn có thể tối ưu hóa nó cho trường hợp khi [số gói thực phẩm] < < [số ô vuông trong lưới]. ví dụ. Trong biểu đồ trên.

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 

Cuối cùng mảng khoảng cách sẽ chứa lượng công việc mà một đàn kiến ​​phải làm để nắm bắt tất cả các gói thực phẩm trên lưới. Đặt đàn kiến ​​tại quảng trường có giá trị nhỏ nhất.

Nhưng lưu ý rằng độ phức tạp tiệm cận của phương pháp này vẫn giống như thuật toán bạn đã đưa ra trong câu hỏi.

Tái bút: Một tối ưu hóa hiển nhiên đối với thuật toán của bạn đã được đưa ra bởi Taoufiq trong các ý kiến. I E. ngừng tính toán tổng số đường đi ngắn nhất vượt quá khoảng cách ngắn nhất được tìm thấy cho đến bây giờ.

Hy vọng điều này hữu ích.

Answer 2

Một số optimisations dựa trên phương pháp brute-force:

• theo dõi khoảng cách ngắn nhất, và ngăn chặn việc tính toán bất kỳ sum of shortest paths vượt quá

• Nếu khoảng cách Manhattan (delta(x) + delta(y)) dài hơn khoảng cách ngắn đã từng được ghi lại, dừng tính toán

• Kết hợp với tối ưu hóa khoảng cách Manhattan: bắt đầu ở giữa bảng hoặc giữa trung tâm các gói thực phẩm điện tử và tự làm việc bên trong. Vị trí tối ưu là nhiều khả năng được ở đâu đó ở giữa

• Giảm miền tìm kiếm của bạn vào vùng giữa các gói thực phẩm (tức là từ [1,1] to [6,7], chứ không phải là [0,0] to [7,7])

• Nikunj của tối ưu hóa

Hơn nữa, nếu bảng của bạn rất lớn, optimisation solver có thể làm giảm số lần tính toán. Tuy nhiên, vấn đề của bạn dường như là một vấn đề không lồi, và nhiều người giải quyết có vấn đề giải quyết những vấn đề đó.