tìm ma trận chéo đường chéo với số tiền tối đa về phía trước rồi lùi lại

Question

Nếu tôi có ma trận, mọi phần tử của ma trận là số không âm. Tôi muốn đi qua ma trận từ góc dưới bên trái đến góc trên cùng bên phải. Trong mỗi bước tôi chỉ có thể di chuyển lên trên hoặc sang phải, và mọi phần tử được truy cập sẽ được đặt thành 0; sau đó, tôi bước trở lại từ góc trên bên phải đến góc dưới cùng bên trái, mỗi bước tôi chỉ có thể di chuyển xuống hoặc xuống.

Câu hỏi của tôi là cách tìm hiệu quả đường dẫn có tổng số tiền tối đa.

Answer 1

Hãy có ma trận với N hàng và M cột và giả định rằng N>=2 và M>=2, nếu không giải pháp là không đáng kể. Tôi có một thuật toán chạy trong O(max(M,N) * min(N,M)^4) sử dụng lập trình động.

Trước tiên, hãy chứng minh rằng một giải pháp tối ưu nơi đường dẫn không vượt qua (ngoại trừ lúc bắt đầu và kết thúc) luôn luôn tồn tại. Chúng tôi sẽ thực hiện bất kỳ giải pháp nào và chuyển đổi thành một giải pháp không giao dịch mà không làm giảm chức năng tối ưu hóa.

Proof:

Bắt đầu bằng cách đảm bảo rằng con đường thứ hai (từ góc trên bên phải xuống dưới cùng bên trái) phải lúc nào cũng ở trên hoặc ở hàng tương tự như con đường đầu tiên. Làm điều đó bằng cách lấy một phần duy nhất của cả hai con đường mà điều này là không đúng sự thật, và trao đổi chúng. Hình minh họa:

Sau đó, loại bỏ một va chạm cùng một lúc. Bạn luôn có thể tìm thấy một va chạm sao cho ít nhất một tuyến đường đang chuyển đến đó và bạn có thể thay đổi đường đi đó để tránh va chạm. Lặp lại điều này cho đến khi tất cả các va chạm được loại bỏ. Minh họa một bước:

Chúng ta thấy rằng không chỉ có yếu tố chúng tôi xóa khỏi cả hai con đường kết hợp, nhưng nhiều yếu tố đã được thêm vào, và tất cả các yếu tố này là không âm, vì vậy số tiền chỉ có thể đi lên .

Thuật toán:

Chúng tôi sẽ chỉ xem xét những con đường mà không vượt qua, tôi cũng sẽ cho rằng N<=M (ma trận rộng ít nhất là chiều cao). Thông thường, chúng tôi sẽ thêm số từ một cột, có thể được thực hiện nhanh chóng bằng cách sử dụng Prefix sum.

Chúng tôi sẽ bắt đầu ở cột đầu tiên. Đối với mỗi cặp (i, j) sao cho 1<=i<j<=N, chúng tôi sẽ tính số điểm của cặp đó, là tổng bao nhiêu cả hai đường dẫn bắt đầu tại (1,1) và kết thúc tại (1, i) và (1, j) tương ứng. Ví dụ:

Matrix: 
1 2 3 
4 5 6 
7 8 9 

score(1,1) = 7 
score(1,3) = 12 
score(2,3) = -inf (paths cannot cross) 

Sau đó, chúng tôi sẽ tính toán điểm số của mỗi cặp trong cột tiếp theo từ số điểm của cặp trong cột hiện tại. Đối với mỗi cặp trong cột tiếp theo, chỉ cần nhìn vào tất cả các cặp trong cột trước đó có đường dẫn có thể được mở rộng để phù hợp với đường dẫn của cột hiện tại.

Cuối cùng, câu trả lời của bạn là điểm số của cặp (N-1, N) trong cột cuối cùng. Tôi xin lỗi vì tôi đang khủng khiếp giải thích các thuật toán trên phương tiện truyền thông bằng văn bản, tôi hy vọng nó không hoàn toàn không ổn định.