Tối đa hóa tổng số "không chồng chéo" số từ ma trận

Question

Chỉ cần tìm kiếm một chút hướng, tôi nhận ra rằng ví dụ được đưa ra có thể giải quyết bằng cách sử dụng lặp lại sức mạnh vũ phu, nhưng tôi đang tìm kiếm một thanh lịch hơn (ví dụ: toán học?) giải pháp có khả năng giải quyết các ví dụ lớn hơn đáng kể (nói 20x20 hoặc 30x30). Hoàn toàn có thể là điều này không thể được thực hiện, và tôi đã có rất ít thành công trong việc đưa ra cách tiếp cận không dựa vào sức mạnh vũ phu ...

Tôi có ma trận (gọi là A) là nxn. Tôi muốn chọn một tập hợp con (gọi nó là B) của các điểm từ ma trận A. Tập hợp con sẽ bao gồm các phần tử n, trong đó một và chỉ một phần tử được lấy từ mỗi hàng và từ mỗi cột A. Đầu ra sẽ cung cấp một giải pháp (B) sao cho tổng của các phần tử tạo thành B là giá trị tối đa có thể, với các ràng buộc này (ví dụ 25 trong ví dụ dưới đây). Nếu tìm thấy nhiều trường hợp của B (nghĩa là các giải pháp khác nhau cho cùng một số tiền tối đa) thì giải pháp cho B có phần tử tối thiểu lớn nhất sẽ được chọn.

B cũng có thể là ma trận lựa chọn là nxn, nhưng chỉ có n phần tử mong muốn khác không.

Ví dụ: nếu A =

|5 4 3 2 1| 
|4 3 2 1 5| 
|3 2 1 5 4| 
|2 1 5 4 3| 
|1 5 4 3 2| 

=> B sẽ

|5 5 5 5 5| 

Tuy nhiên, nếu A =

|5 4 3| 
|4 3 2| 
|3 2 1| 

B =

|3 3 3| 

Như các yếu tố tối thiểu của B là 3 mà lớn hơn cho

|5 3 1| 

hoặc

|4 4 1| 

mà cũng cả số tiền đến 9

Answer 1

Sự cố của bạn gần giống với Assignment problem, có thể, ví dụ: được giải quyết bởi Hungarian algorithm trong thời gian đa thức.

Lưu ý rằng vấn đề gán thường là một vấn đề giảm thiểu, nhưng nhân ma trận của bạn với -1 và thêm một số hằng số nên làm cho phương pháp áp dụng. Hơn nữa, không có điều kiện tie-phanh chính thức, cho trường hợp của nhiều giải pháp tối ưu. Tuy nhiên, phương thức này mang lại cho bạn một giải pháp có tổng tối ưu. Để m là summon tối thiểu. Sửa đổi ma trận của bạn bằng cách đặt tất cả các mục nhỏ hơn hoặc bằng m về 0 và giải quyết lại. Hoặc bạn nhận được một giải pháp với cùng một số tiền đó là tốt hơn so với một trong những cuối cùng. Nếu không, giải pháp trước đó đã tối ưu.

Answer 2

này có liên quan đến n Queens problem, ngoại trừ việc bạn không quan tâm đến đường chéo và bạn có các giải pháp có trọng số. Là vấn đề Queens, bạn có thể giải quyết nó bằng (nhiều) backtracking.

Tức là, khi bạn tìm thấy giải pháp mà bạn nhớ trọng lượng của nó, hãy đánh dấu biểu tượng là không hợp lệ và bắt đầu lại. Giải pháp (a) có tỷ lệ thắng cao nhất.

Answer 3

Ouch. This algorithm is wrong; there is no proof because it's wrong and therefore it's impossible to prove that it's correct.;) Tôi để nó ở đây vì tôi quá gắn bó để xóa nó hoàn toàn, và đó là một minh chứng tốt về lý do tại sao bạn nên chính thức chứng minh thuật toán thay vì nói "điều này có vẻ đúng! Không có cách nào có thể làm việc này không thành công! "

---

Tôi đang đưa ra giải pháp này mà không cần bằng chứng, hiện tại. Tôi có một bản phác thảo bằng chứng nhưng tôi gặp khó khăn trong việc chứng minh cấu trúc con tối ưu cho vấn đề này. Dù sao ...

Vấn đề

Cho một mảng vuông số, chọn càng nhiều số "không chồng chéo" càng tốt để tổng các số được chọn sẽ được tối đa hóa. "Không trùng lặp" có nghĩa là không có hai số có thể từ cùng một hàng hoặc cùng một cột.

Algorithm

• Hãy A là một mảng vuông n by n số.
• Hãy để Aij biểu thị phần tử A trong hàng thứvà cột j.
• Hãy S(i1:i2, j1:j2) biểu thị tổng tối ưu các số không chồng chéo cho một mảng con vuông A chứa giao điểm của hàng i1-i2 và cột j1-j2.

Sau đó, số tiền tối ưu của số không chồng chéo được ký hiệu S(1:n , 1:n) và được đưa ra như sau:

S(1:n , 1:n) = max { [ S( 2:n , 2:n ) + A11 ] 
         [ S( 2:n , 1:n-1) + A1n ] 
         [ S(1:n-1 , 2:n ) + An1 ] 
         [ S(1:n-1 , 1:n-1) + Ann ] } 
(recursively) 

Note that S(i:i, j:j) is simply Aij. 

Đó là, số tiền tối ưu cho một mảng vuông kích thước n thể được xác định bằng cách tính toán riêng số tiền tối ưu cho mỗi một trong bốn mảng phụ có kích thước n-1, và sau đó tối đa hóa tổng của mảng phụ và phần tử "bị loại bỏ".

S for |# # # #| 
     |# # # #| 
     |# # # #| 
     |# # # #| 

Is the best of the sums S for: 

|#  |  |  #|  |# # # |  | # # #| 
| # # #|  |# # # |  |# # # |  | # # #| 
| # # #|  |# # # |  |# # # |  | # # #| 
| # # #|  |# # # |  |  #|  |#  | 

Thực hiện

Thuật toán đệ quy trên cho thấy một giải pháp đệ quy:

def S(A,i1,i2,j1,j2): 
    if (i1 == i2) and (j1==j2): 
     return A[i1][j1] 
    else: 
     return max (S(A, i1+1, i2, j1+1, j2) + A[i1][j1] ], 
        S(A, i1+1, i2, j1, j2-1) + A[i1][j2] ], 
        S(A, i1, i2-1, j1+1, j2) + A[i2][j1] ], 
        S(A, i1, i2-1, j1, j2-1) + A[i2][j2] ],) 

Lưu ý rằng điều này sẽ làm cho các cuộc gọi đến O(4^n)S() !! Điều này là tốt hơn nhiều so với giai thừa O(n!) thời gian phức tạp của giải pháp "sức mạnh vũ phu", nhưng hiệu suất vẫn khủng khiếp.

Điều quan trọng cần lưu ý ở đây là nhiều cuộc gọi được lặp lại với cùng các tham số. Ví dụ, trong việc giải quyết một mảng 3 * 3, mỗi mảng 2 * 2 được giải quyết nhiều lần.

Điều này cho thấy hai giải pháp khả thi cho sự tăng tốc:

• Tận dụng đệ quy chức năng S() kết quả bộ nhớ cache để nó chỉ cần S(A,i1,i2,j1,j2) một lần cho mỗi i1,i2,j1,j2. Điều này có nghĩa là S() chỉ cần tính toán kết quả O(n^3) - tất cả các yêu cầu khác sẽ được lọc từ bộ nhớ cache. (Điều này được gọi là memoising.)
• Thay vì bắt đầu từ phía trên, với n*n mảng lớn, và làm việc xuống qua bài toán liên tiếp nhỏ hơn, hãy bắt đầu ở dưới cùng với các bài toán nhỏ nhất có thể và xây dựng lên với trường hợp n*n. Điều này được gọi là lập trình động. Đây cũng là O(n^3), nhưng nó nhanh hơn nhiều O(n^3) vì bạn không phải nhấn vào bộ nhớ cache mọi lúc.

Các giải pháp lập trình năng động tiến hành một chút như:

• Tìm giải pháp tối ưu cho tất cả 1x1 tiểu mảng. (Không đáng kể.)
• Tìm các giải pháp tối ưu cho tất cả các mảng phụ 2x2.
• Tìm các giải pháp tối ưu cho tất cả các mảng phụ 3x3.
• ...
• Tìm giải pháp tối ưu cho tất cả các mảng phụ n-1 * n-1.
• Tìm các giải pháp tối ưu cho mảng phụ n * n hoàn chỉnh.

Ghi chú về giải pháp này:

chưa
• Không có bằng chứng. Tôi đang giải quyết nó.
• Bạn sẽ lưu ý thuật toán trên chỉ cung cấp cho bạn S(), tối ưu tổng số. Nó không cho bạn biết con số nào thực sự tạo nên số tiền đó. Bạn có thể thêm vào phương pháp của riêng bạn để backtracing đường dẫn của bạn đến giải pháp.
• Các thuật toán trên không đảm bảo tài sản đó gắn như 2,2 vs 1,3 sẽ bị phá vỡ trong lợi của việc có tất cả các số cá nhân được càng lớn càng tốt (để 2,2 thắng.) Tôi tin rằng bạn có thể định nghĩa max() để phá vỡ mối quan hệ có lợi cho số lượng lớn nhất có thể, và điều đó sẽ làm những gì bạn muốn, nhưng tôi không thể chứng minh điều đó.

ghi chú chung:

Dynamic programming là một kỹ thuật mạnh mẽ cho việc đưa ra các thuật toán nhanh cho bất kỳ vấn đề trưng bày hai thuộc tính:

1. Hạ tầng cơ sở tối ưu: Một vấn đề có thể được chia nhỏ thành hơi nhỏ các bộ phận, mỗi bộ phận có thể được sử dụng như một phần của giải pháp cho vấn đề ban đầu.
2. Các vấn đề phụ chồng chéo có nghĩa là có ít vấn đề con thực tế cần giải quyết và các giải pháp cho các vấn đề con được sử dụng lại nhiều lần.

Nếu vấn đề có nền móng tối ưu, và vấn đề phá vỡ vào hơi vấn đề nhỏ hơn - nói một vấn đề về kích thước n chia ra làm bài toán kích thước n-1 - thì vấn đề có thể được giải quyết bằng cách lập trình năng động .

Nếu bạn có thể chia nhỏ vấn đề thành nhiều những phần nhỏ hơn - nói chặt một vấn đề về kích thước n vào nửa, mỗi kích thước n/2 - đó là chia để trị, không lập trình năng động. Giải pháp chia và chinh phục thường là rất nhanh - ví dụ: tìm kiếm nhị phân sẽ tìm thấy phần tử trong một mảng được sắp xếp theo thời gian O(log n).

Answer 4

Vì Matthias cho biết bạn nên sử dụng tính năng quay lại.

1. Tìm giải pháp hợp lý. Chọn giá trị tối đa từ mỗi hàng và xem chúng có bị chồng chéo hay không. Nếu không, sau đó perturb một phần của giải pháp để kết quả trở nên không chồng chéo.
2. Xác định tập thể dục của giải pháp một phần.Giả sử bạn đang chọn giá trị cho mỗi hàng lặp đi lặp lại và bạn đã chọn các giá trị từ các hàng k đầu tiên. Thể dục của giải pháp này bằng tổng của các giá trị đã chọn + giá trị tối đa từ các hàng còn lại và các cột không được chọn
3. Bây giờ hãy bắt đầu tìm kiếm giải pháp đệ quy. Chọn các giá trị từ hàng đầu tiên, tính toán tập thể dục của chúng và chèn chúng vào hàng đợi ưu tiên. Loại bỏ tất cả các giải pháp có thể lực thấp hơn giải pháp tối ưu hiện tại (được khởi tạo ở bước 1). Chọn giải pháp ở đầu hàng đợi, tính toán cấp độ tiếp theo của các giải pháp và chèn chúng trở lại hàng đợi ưu tiên. Khi bạn đã chọn giá trị từ tất cả các cột và hàng, hãy tính tổng và nếu giá trị đó cao hơn giá trị tối ưu hiện tại, hãy thay thế nó.