Thuật toán nhanh để đóng gói thùng 2D với khoảng cách tối thiểu mỗi hình chữ nhật và một điểm

Question

Điều này tương tự như bin packing problem, nhưng với một số thay đổi.

Điều tôi có là bộ đếm thời gian của dữ liệu được chú thích và khi tôi vẽ biểu đồ, tôi muốn đặt chú thích ở vị trí tổng thể thu nhỏ khoảng cách từ điểm được chú thích.

Biểu đồ này, (bị đánh cắp vô cớ) cho thấy những gì tôi muốn làm: .

Tôi biết đây là vấn đề tối ưu hóa, nhưng tôi không biết bắt đầu từ đâu. Những gì tôi đã làm đầu tiên, đã được đặt nó tại x tương ứng, và di chuyển lên/xuống y để tìm một vị trí có sẵn và lưu các khu vực đã được rút ra. Trong khi đó làm việc, nó không thực sự tận dụng tốt nhất của không gian có sẵn, và tôi tự hỏi nếu có cái gì tốt hơn.

Tôi tự hỏi liệu có bất kỳ thuật toán nào đã biết có tấn công vấn đề này hay tương tự không?

Đã thêm ghi chú: Không cần phải tối ưu hóa, nhưng nó hoàn toàn cần phải nhanh. Điều này được thực hiện trong khi hiển thị, vì vậy giao diện người dùng bị chặn trong khi thực thi điều này.

Answer 1

Có rất nhiều cách tiếp cận cho vấn đề khó khăn này. Tôi khuyên bạn nên bắt đầu bài viết trên Wikipedia về số automatic label placement. Bạn cũng có thể nhận được một số ý tưởng từ lĩnh vực force-based algorithms for graph drawing.

Answer 2

Tôi sẽ làm như thế này- sử dụng thuật toán "phù hợp đầu tiên" đơn giản và bắt đầu với một thứ tự tùy ý để đặt nhãn. Điểm kết quả với một cái gì đó giống như tổng của khoảng cách bình phương từ mỗi điểm chú thích. Tôi sẽ làm khoảng cách bình phương để tránh có tất cả chúng thực sự gần gũi ngoại trừ một trong đó là một chặng đường dài đi.

Nếu giải pháp đầu tiên của bạn thấp hơn ngưỡng nào đó, hãy sử dụng nó và tiếp tục. Nếu không, hãy lấy những thứ phù hợp nhất (ví dụ: các nhãn nằm xa nhất từ ​​điểm chú thích) và di chuyển chúng lên theo thứ tự sắp xếp và bắt đầu lại. Lặp lại điều này cho đến khi bạn có được một giải pháp đủ tốt hoặc bạn hết thời gian, trong trường hợp đó bạn sẽ có giải pháp tốt nhất của lô đất và đi theo nó.