Đơn đăng ký tăng dài nhất

Question

Vấn đề LIS (Longest Increasing Subsequence) có hữu ích trong việc giải quyết các vấn đề CS khác không? Có một vài thuật toán, sử dụng phân loại kiên nhẫn, lập trình động hoặc với cây quyết định. Làm thế nào chúng được sử dụng trong cuộc sống thực - có thể cho các luồng dữ liệu hoặc một cái gì đó?

Để nhắc nhở bạn, tôi đặt in đậm chuỗi tăng dài nhất

{, 8, 4, 12, , 10, , 14, 1, , 5 , 13, 3, , 7, }.

Là phần thưởng, có cách nào để sử dụng kết quả a sequence of length mn + 1 will have an increasing subsequence of length m or a decreasing subsequence of length n không? Ví dụ. Danh sách của chúng tôi là chiều dài 16, do đó, sẽ có một chuỗi ngày càng tăng có chiều dài 5 hoặc giảm độ dài chuỗi 5. Trong trường hợp của chúng tôi 0,2,6,9,11,15.

Ngoài ra chuỗi ngày càng tăng chiều dài 8 hoặc chuỗi độ dài giảm 3: trong trường hợp của chúng tôi 12,10,1.

Answer 1

Ứng dụng thực tế thú vị của LIS là Diffience Diff, một thuật toán diffing bởi Bram Cohen (tác giả của BitTorrent) được sử dụng trong hệ thống điều khiển phiên bản Bazaar.

Thuật toán thông dụng khác bao gồm tính toán LCS (Longest Common Subsequence) giữa hai tài liệu. Trong khi hiệu quả, cách tiếp cận này có một vấn đề, đó là - kết quả thường xảy ra không phải là khá thân thiện với con người.

Một ví dụ đơn giản về cách một diff thường xuyên có thể thất bại:

void func1() { 
    x += 1 
+} 
+ 
+void functhreehalves() { 
+ x += 1.5 
} 

void func2() { 
    x += 2 
} 

Ưu điểm của Kiên nhẫn thuật toán Diff là nó cho phép để tính toán sự khác biệt một cách chính xác hơn, một cách tương ứng chặt chẽ hơn để làm thế nào một con người sẽ thực hiện.

Trong trường hợp kiên nhẫn trước Diff treo nó khác biệt tốt hơn:

void func1() { 
    x += 1 
} 

+void functhreehalves() { 
+ x += 1.5 
+} 
+ 
void func2() { 
    x += 2 
} 

Tóm lại, thuật toán là:

1. Tìm đường độc đáo đó là chung cho cả hai tài liệu.
2. Lấy tất cả các dòng đó từ tài liệu đầu tiên và sắp xếp chúng theo sự xuất hiện của chúng trong tài liệu thứ hai.
3. Tính LIS của chuỗi kết quả (bằng cách thực hiện một Patience Sort), nhận được chuỗi kết hợp dài nhất của các dòng, một sự tương ứng giữa các dòng của hai tài liệu.
4. Tuân thủ thuật toán trên mỗi phạm vi của các dòng giữa các dòng đã khớp.

Hãy xem the code.