Thuật toán hình dạng với tối ưu hóa

Question

Tôi có hình dạng được xác định bởi các đoạn thẳng.

Tôi muốn đơn giản hóa hình dạng được xây dựng bằng các đường thẳng nhưng chỉ với một tập hợp sườn dốc.

Tôi muốn giảm thiểu số lượng phân khúc được sử dụng và giảm thiểu sự khác biệt về diện tích so với hình dạng trước và sau.

Tôi muốn tối thiểu hóa hai thứ này cùng một lúc với trọng lượng do người dùng xác định nhấn mạnh giảm thiểu nhiều cái khác.

minimize { J = w1(number of segments/length) + w2(difference area/length) } 

đâu w1 và w2 đều trọng lượng và chiều dài là chiều dài của phân khúc mới. Tôi muốn một thuật toán thực hiện điều này. Ý tưởng nào?

Dưới đây tôi hiển thị một vài hình ảnh về cách tôi có thể muốn nó hoạt động. Có điều gì trong văn học có thể giúp viết một thuật toán hay không. Cảm ơn!

Answer 1

Điều này có vẻ như là một vấn đề rất khó khăn! Tôi sẽ tiếp cận nó bằng cách đầu tiên xác định hai thói quen:

1. diffArea(fig, target) tính diện tích chênh lệch giữa fig và target
2. decomp(fig, p1, p2, s1, s2) tính hai nhân vật có thể được xây dựng bằng cách thay thế tất cả các phân khúc giữa p1 và p2 với một cặp các đoạn hình dạng s1 và s2. Ví dụ: nếu có bốn phân đoạn giữa các điểm p1 và p2 trong fig thì decomp(fig, p1, p2, s1, s2) trả về hai số liệu được tạo bằng cách thay thế bốn phân đoạn đó bằng các phiên bản được thu nhỏ thích hợp s1 và s2. Chỉ có một cách để chia tỷ lệ s1 và s2 để lấp đầy khoảng trống giữa p1 và p2 (vì chúng tôi đang ở trong không gian 2 chiều) và hai số liệu đến từ một trong hai thứ tự là s1 -> s2 hoặc s2 -> s1.

Với hai quy trình này, tôi nghĩ rằng quy trình tìm kiếm cục bộ được lặp lại có thể hoạt động tốt. Bạn sẽ có các bước sau:

1. Đặt fig đến một bounding hình lớn xung quanh target
2. Đối với mỗi cặp đỉnh (p1, p2) trong fig (bắt đầu với cặp với 1 phân khúc giữa, sau đó 2 phân khúc giữa, ...) Và đối với mỗi cặp (s1, s2) hình dạng:
   • Tính fig1 và fig2 sử dụng decomp(fig, p1, p2, s1, s2)
   • Hãy e_fig là số cạnh trong fig và e_new bởi số cạnh trong fig1 và fig2
   • Nếu w1 * e_new + w2 * diffArea(fig1, target) < w1 * e_fig + w2 * diffArea(fig, target), thay thế fig với fig1
   • Nếu w1 * e_new + w2 * diffArea(fig2, target) < w1 * e_fig + w2 * diffArea(fig, target), thay thế fig bằng fig2

Lặp lại quy trình này cho đến khi bạn thử nghiệm mọi cặp đỉnh và không tìm thấy thay thế cải tiến. Điều này rõ ràng là sẽ không cung cấp cho bạn một giải pháp tối ưu, nhưng tôi đặt cược nó sẽ thực hiện khá tốt.

Answer 2

Vâng, trong trường hợp này Pareto efficiency có vẻ là một trọng lượng tốt của một giải pháp. Thoạt nhìn, có vẻ như việc sử dụng một tối ưu hóa rời rạc sẽ thích hợp. Lựa chọn một thuật toán cụ thể phụ thuộc vào độ phức tạp của các hình được định hình. Đối với các số liệu lớn và phức tạp, tôi sẽ đề nghị sử dụng thuật toán di truyền.