Đóng các điểm đóng trên mặt phẳng?

Question

Giả sử rằng tôi có biểu đồ G hoàn chỉnh, không bị chiếu xạ với khoảng cách được liên kết với mỗi cạnh. Ý nghĩa của cạnh (u, v) có độ dài l là "điểm u và v không thể gần nhau hơn l." Mục tiêu của tôi là đặt các nút của đồ thị này ra trong mặt phẳng sao cho không có ràng buộc khoảng cách nào bị vi phạm và sao cho phần lồi của các điểm có tổng diện tích nhỏ nhất. Ví dụ, giả sử rằng tôi có một loạt các thành phần điện tôi muốn đưa vào một con chip, mỗi bộ tạo ra một số nhiễu điện. Nếu tôi đặt các thành phần quá gần nhau, chúng sẽ bắt đầu can thiệp vào nhau, làm cho toàn bộ hệ thống vô dụng. Với khoảng cách tối thiểu mà mỗi điểm phải là từ mỗi điểm khác, cách hiệu quả nhất về mặt không gian của việc đưa các thành phần vào một con chip là gì?

Tôi không biết làm cách nào để bắt đầu nghĩ về điều này. Tôi cũng không biết làm thế nào vấn đề có thể khái quát hóa với trường hợp chiều cao hơn (đóng gói điểm vào một hyperplane). Có ai biết một cách tốt để giải quyết vấn đề này?

Answer 1

Tôi có giải pháp tối ưu nhưng bạn sẽ không thích nó :).

Hãy nhãn nút của chúng tôi x , x , ..., x n . Hãy B = max _{i, j < n} (dist (x _i, x _j)), nơi dist (x _i, x _j) là khoảng cách tối thiểu giữa x _i và x _j.Đối với mỗi i, nút đặt x _i tại vị trí (0, i * B). Bây giờ mỗi nút có ít nhất B cách xa tất cả các nút khác và thân lồi có diện tích 0.

Điểm thực ở đây là giảm thiểu diện tích thân lồi một mình sẽ cung cấp cho bạn một giải pháp vô nghĩa. Một biện pháp tốt hơn có thể là đường kính của vỏ lồi.

Answer 2

Tôi đoán sẽ rất khó để tìm ra thuật toán tối ưu. Tôi sẽ không ngạc nhiên nếu nó hóa ra lại là một vấn đề NP-hard. Tuy nhiên, nếu bạn quan tâm đến một thuật toán thực tế mang lại các giải pháp tốt, tôi khuyên bạn nên xem force-based graph drawing algorithms.

Đây là ý tưởng chung (một số phép tính cao hơn sẽ xuất hiện). Nó tổng quát đến bất kỳ số thứ nguyên nào.

Xây dựng hàm f chỉ định giá trị cho mỗi bố cục nút - giá trị bạn muốn thu nhỏ. Trong trường hợp của bạn, hàm có thể tính toán diện tích của lồi lồi cho một bố trí đã cho + một hình phạt lớn cho mỗi ràng buộc mà không được đáp ứng. Hoặc nó có thể là một hàm đơn giản hơn g hợp lý gần đúng với cái cũ: trong ngắn hạn, chúng tôi muốn g để thu nhỏ hơn bất cứ khi nào f trở nên nhỏ hơn và ngược lại. Tốt nhất là chọn một hàm tương đối đơn giản, bởi vì bạn sẽ cần tính các dẫn xuất một phần của nó (đối với các tọa độ của các nút).

Bây giờ giả sử bạn có 100 nút và bạn muốn đặt chúng ra ở chế độ 3D. Điều đó có nghĩa là bạn có 300 số không xác định (100 nút lần 3 tọa độ cho mỗi nút). Chức năng f là một chức năng từ R đến R và lý tưởng nhất là chúng tôi muốn tìm mức tối thiểu toàn cầu. Thực tế hơn, mức tối thiểu địa phương đủ sâu sẽ đủ.

Có các thuật toán số nổi tiếng để tìm mức tối thiểu như vậy, ví dụ: Conjugate gradient, BFGS. Điều tốt là, bạn không thực sự phải hiểu chúng chi tiết, các thuật toán này được thực hiện bằng nhiều ngôn ngữ. Tất cả những gì bạn phải làm là cung cấp một phương pháp tính f(x) và f'(x) cho bất kỳ x theo yêu cầu của thuật toán và bố cục ban đầu x₀.

Answer 3

Đó là 2D bin packing problem (là NP cứng) với các ràng buộc bổ sung. Tôi đã nghe mô phỏng ủ thực hiện khá tốt cho thiết kế mạch/chip.

Tôi thực sự là looking for real-world test-data of a big bin packing problem cho Drools Planner.