Kết hợp hai bên trọng số tối đa, ràng buộc: thứ tự của từng biểu đồ được giữ nguyên

Question

Giả sử tôi có hai bộ: (n_1, n_2, ...) và (m_1, m_2, ...) và đối sánh hàm phù hợp (n, m) trả về một giá trị từ 0 đến 1. tôi muốn tìm ánh xạ giữa hai bộ như vậy mà khó khăn sau đây được đáp ứng:

• Mỗi phần tử phải có ít nhất 1 phần tử xuất hiện trong bộ ngược lại.
• yếu tố chưa từng có sẽ được ghép nối với một yếu tố giả với chi phí 1
• Tổng số các chức năng phù hợp khi áp dụng cho tất cả các yếu tố là tối đa
• tôi đang gặp khó khăn hiện nay chính thức, nhưng nếu bạn xếp hàng mỗi bộ song song với nhau với thứ tự ban đầu của họ và vẽ một đường thẳng giữa các phần tử được so khớp, không có dòng nào trong số các đường chéo sẽ bị gạch chéo. E.x. [n_1 < -> m_2, n_2 < -> m_3] là ánh xạ hợp lệ nhưng [n_1 < -> m_2, n_2 < -> m_1] thì không.

(Tôi tin rằng ba đầu tiên là tiêu chuẩn trọng hạn chế phù hợp song phương, nhưng tôi đã chỉ định chúng trong trường hợp tôi bị hiểu lầm trọng phù hợp song phương)

này là tương đối thẳng về phía trước để làm với một tìm kiếm đầy đủ trong thời gian mũ (đối với kích thước của các bộ), nhưng tôi hy vọng một thời gian đa thức (lý tưởng là giải pháp O ((| n | * | m |)^3) hoặc tốt hơn) tồn tại.

Tôi đã tìm kiếm số tiền hợp lý trên "vấn đề chuyển nhượng"/"kết hợp hai bên trọng số" và đã thấy các biến thể với các ràng buộc khác nhau, nhưng không tìm thấy biến thể nào khớp hoặc tôi có thể giảm xuống ràng buộc đặt hàng. Bạn có ý tưởng nào về cách tôi có thể giải quyết vấn đề này không? Hoặc có lẽ một bằng chứng thô rằng nó không thể giải được trong thời gian đa thức (cho mục đích của tôi, giảm NP-hoàn thành cũng sẽ làm việc)?

Answer 1

Sự cố này đã được nghiên cứu với tên "kết hợp không vượt qua trọng lượng tối đa". Có một chương trình động bậc hai đơn giản. Để M (a, b) là giá trị của một kết hợp tối ưu trên n ,…, n _a và m ,…, m _b. Chúng tôi có sự tái

M (0, b) = -b
M (a, 0) = -a
M (a, b) = max {M (a - 1, b - 1) + đối sánh (a, b), M (a - 1, b) - 1, M (a, b - 1) - 1}.

Bằng cách truy tìm lại argmaxes, bạn có thể khôi phục giải pháp tối ưu từ giá trị của nó.

Nếu kết quả có ít hơn đáng kể so với số bậc hai bậc mục lớn hơn -1, có một thuật toán chạy theo thời gian linearithmic trong số mục nhập hữu ích (Khoo and Cong, A Fast Multilayer General Area Router for MCM Designs).