Kĩ thuật Heavy Light Decomposition  (Bấm vào liên kết phía dưới để tải xuống)

Kĩ thuật Heavy-Light Decomposition được đưa ra lần đầu năm 1983 bởi Sleator và Tarjan trong bài báo "A data structure for dynamic trees", Journal of Computer and System Sciences 26 (3): 362–391 trong phần phân tích tiệm cận về tính hiệu quả của cấu trúc link/cut tree của họ. Năm 1984, Harel và Tarjan lại sử dụng một lần nữa kĩ thuật này trong bài báo "Fast algorithms for finding nearest common ancestors", SIAM Journal on Computing 13 (2): 338–355 về tìm tổ tiên chung gần nhất của hai nút trong một cây. HLD sớm chứng tỏ sức mạnh của nó trong nghiên cứu độ phức tạp của các thuật toán, các cấu trúc dữ liệu trên cây.

Kĩ thuật Heavy Light Decomposition

Giới thiệu
Kĩ thuật Heavy-Light Decomposition (còn gọi là heavy path decomposition, từ đây xin viết tắt là HLD) được đưa ra lần đầu năm 1983 bởi Sleator và Tarjan trong bài báo "A data structure for dynamic trees", Journal of Computer and System Sciences 26 (3): 362–391 trong phần phân tích tiệm cận về tính hiệu quả của cấu trúc link/cut tree của họ. Năm 1984, Harel và Tarjan lại sử dụng một lần nữa kĩ thuật này trong bài báo "Fast algorithms for finding nearest common ancestors", SIAM Journal on Computing 13 (2): 338–355 về tìm tổ tiên chung gần nhất của hai nút trong một cây. HLD sớm chứng tỏ sức mạnh của nó trong nghiên cứu độ phức tạp của các thuật toán, các cấu trúc dữ liệu trên cây.
Tưởng chừng HLD chỉ có ý nghĩa chủ yếu trên phương diện lý thuyết độ phức tạp và chỉ là công cụ chứng minh toán học thuần túy cho các bài báo thì đến những năm 2013-2014, trong các bài toán của nhiều cuộc thi lập trình online, HLD đã bước ra thực tiễn và nhanh chóng thể hiện được tính ưu việt của mình trong việc mô tả và xử lí các mối quan hệ động giữa các đối tượng trong nhiều bài toán, đặc biệt trên cấu trúc cây với các truy vấn online.
Chúng tôi xin cung cấp một cái nhìn sơ lược về HLD và vài mở rộng của nó thông qua một số bài toán lập trình thuật toán, ngõ hầu cùng quý vị nắm bắt kịp với xu hướng thay đổi chóng mặt về giải thuật cũng như cấu trúc dữ liệu của các cuộc thi lập trình online, các cuộc thi lập trình khu vực và quốc tế.
HLD trên cây
Cây cân bằng
Ta đã biết cây cân bằng là một cấu trúc tốt trong lập trình. Một cây cân bằng nút có độ cao , điều này cho ta hai tính chất:
Ta cần duyệt qua không quá nút để đến được nút gốc từ một nút bất kì trong cây;
Ta cần duyệt qua không quá nút để di chuyển từ một nút bất kì đến một nút bất kì khác trong cây.
Hệ số luôn tốt cho mọi bài toán. Với một cây cân bằng nút, ta giải quyết được một loạt các truy vấn bằng độ phức tạp . Chẳng hạn: khoảng cách giữa hai nút, trọng số lớn/nhỏ nhất trên một đường đi, tổng liên tiếp lớn nhất của các đoạn liên tiếp, …
Chuỗi tuyến tính Một dãy các nút được nối tiếp tuyến tính cũng là một cấu trúc tốt. Ta có thể xây dựng các
segment tree hay binary indexed tree (là các cây cân bằng) cho chuỗi để giải quyết bằng độ phức tạp các truy vấn dạng max, min, tổng đoạn, … trên chuỗi.
Cây không cân bằng
Độ cao của một cây không cân bằng dao động trong một phạm vi quá lớn ( ). Với trường hợp suy biến, ta phải duyệt qua nút để từ một nút này di chuyển đến một nút khác. Ta xem xét dưới đây cách đối phó với một cây không cân bằng tương đối đặc biệt.
Bài toán: cho cây như hình vẽ, tính tổng trọng số các nút trên đường đi (đơn) giữa hai nút
bất kì, giả thiết trọng số các nút có thể thay đổi theo thời gian/truy vấn.

Có thể nhận thấy:
 Cây có nút  Ta cần thăm nút để di chuyển từ đến
 Ta thăm ít nhất nút để di chuyển từ đến
 Ta thăm ít nhất nút để di chuyển từ đến
Như vậy rõ ràng cần chi phí để di chuyển giữa hai nút tùy ý trong cây.
Để đối phó, ta thử bẻ cây thành ba chuỗi như hình vẽ:

Với mỗi chuỗi ta có thể xây dựng segment tree cho riêng nó và truy vấn trên mỗi chuỗi sẽ
xuất hiện yếu tố log. Ta nhận thấy:
Cây vẫn có nút, nhưng đã được phân rã thành ba chuỗi độ dài  thuộc cùng một chuỗi, truy vấn giữa chúng được giải quyết trong thuộc hai chuỗi khác nhau, đường đi giữa chúng có thể tách thành , truy vấn giữa được giải quyết trong , chính xác là mất hai lần
Tương tự: thuộc hai chuỗi khác nhau, đường đi giữa chúng có thể tách thành , truy vấn giữa chúng được giải quyết trong ,
chính xác là là mất ba lần
Như vậy, với cây đã cho, bằng phép phân rã thành ba chuỗi và xây dựng segment tree kèm theo mỗi chuỗi, truy vấn giữa hai nút bất kì tốn chi phí .
Vấn đề là: cây trên chỉ có đúng hai nút có bậc ba nên ta có được một phân rã tốt, đường đi giữa hai nút bất kì tách thành không quá ba đoạn chuỗi. Điều gì xảy ra nếu cây là cây tổng quát? Ta cần một kĩ thuật phân rã phức tạp hơn nhằm đạt được độ phức tạp chấp nhận được ngay cả trong trường hợp xấu nhất. Đó chính là HLD.

Tải xuống để xem tài liệu hoàn chỉnh - Chia sẻ cho bạn bè nếu trang web có ích với bạn!
Nguồn tài liệu:

Bạn cũng có thể quan tâm:

Bài tập môn Tin học lớp Lớp 12
Mời bạn tham gia hỏi - đáp
Thư viện bài tập © 2014 -2017 - Liên hệ - Giới thiệu - Bản quyền - Chính sách bảo mật - Sitemap