CHƯƠNG 12: HÀNG ƯU TIÊN VỚI PHÉP TOÁN HỢP NHẤT

Trong chương này chúng ta mở rộng KDLTT hàng ưu tiên bằngcách thêm vào hai phép toán: phép toán hợp nhất (Merg) và phép toán giảmkhoá (Decreasekey). Các phép toán này là rất cần thiết trong thiết kế thuậttoán cho các bài toán tối ưu, chẳng hạn các thuật toán đồ thị như tìmđường đi ngắn nhất (thuật toán Dijkstra), tìm cây bao trùm ngắn nhất(thuật toán Prim).
Nội dung trích xuất từ tài liệu:
CHƯƠNG 12: HÀNG ƯU TIÊN VỚI PHÉP TOÁN HỢP NHẤT CHƯƠNG 12 HÀNG ƯU TIÊN VỚI PHÉP TOÁN HỢP NHẤT Trong chương này chúng ta mở rộng KDLTT hàng ưu tiên bằngcách thêm vào hai phép toán: phép toán hợp nhất (Merg) và phép toán giảmkhoá (Decreasekey). Các phép toán này là rất cần thiết trong thiết kế thuậttoán cho các bài toán tối ưu, chẳng hạn các thuật toán đồ thị như tìmđường đi ngắn nhất (thuật toán Dijkstra), tìm cây bao trùm ngắn nhất(thuật toán Prim). Đầu tiên chúng ta sẽ cài đặt KDLTT hàng ưu tiên vớiphép toán hợp nhất bởi cây thứ tự bộ phận (binary heap), sau đó chúng tasẽ xây dựng một CTDL tự điều chỉnh, đó là cây nghiêng (skew heap), đểcài đặt hàng ưu tiên với phép toán hợp nhất và sử dụng kỹ thuật phân tíchtrả góp để đánh giá thời gian chạy của các phép toán hàng ưu tiên trênCTDL này.12.1 HÀNG ƯU TIÊN VỚI PHÉP TOÁN HỢP NHẤT Từ đây về sau chúng ta sẽ xem giá trị khoá của một phần tử là giátrị ưu tiên của phần tử đó. KDLTT hàng ưu tiên với phép toán hợp nhất làmột họ các hàng ưu tiên với các phép toán sau: • Các phép toán trên mỗi hàng ưu tiên (xem 10.1): xen một phần tử vào hàng ưu tiên (Insert), tìm phần tử có khoá nhỏ nhất (FindMin), loại khỏi hàng ưu tiên phần tử có khoá nhỏ nhất (DeleteMin). • Phép toán hợp nhất Merg (P1, P2). Hợp nhất hai hàng ưu tiên P1 và P2 thành một hàng ưu tiên và trả về hàng ưu tiên này, các hàng ưu tiên P1 và P2 bị huỷ bỏ. • Phép toán giảm khoá Decreasekey (P, x, k). Thay đổi giá trị khoá của phần tử x trong hàng ưu tiên P bởi k, ở đây k là giá trị khoá nhỏ hơn giá trị khoá hiện thời của x. Cần lưu ý rằng, trong phép toán giảm khoá, vị trí của phần tử xtrong hàng ưu tiên P được xem là đã biết, không cần phải thực hiện thaotác tìm. Trong các ứng dụng, phép toán giảm khoá thường được sử dụngtrong vòng lặp sau: loại phần tử có khoá nhỏ nhất khỏi hàng ưu tiên P, rồixem xét từng phần tử còn lại và tiến hành giảm khoá (nếu cần thiết); lặplại quá trình đó cho tới khi hàng ưu tiên P trở thành rỗng. Phép toán giảmkhoá là đặc biệt hữu ích trong việc thiết kế các thuật toán cho các vấn đề 85tối ưu. Chúng ta sẽ đưa ra các ví dụ ứng dụng hàng ưu tiên với phép toánhợp nhất trong chương nói về các thuật toán đồ thị. Người ta đã nghiên cứu và đề xuất nhiều CTDL khác nhau để càiđặt hàng ưu tiên với phép toán hợp nhất, chẳng hạn như binary heap,leftist heap, binomial heap, fibonacci heap, skew heap. Tất cả các CTDLnày đều có đặc điểm chung, đó là cấu trúc cây thoả mãn tính chất heap(khoá của mỗi đỉnh không lớn hơn khoá của các đỉnh con của nó).12.2 CÁC PHÉP TOÁN HỢP NHẤT VÀ GIẢM KHOÁ TRÊN CÂYTHỨ TỰ BỘ PHẬN Trong mục 10.3 chúng ta đã cài đặt hàng ưu tiên bởi cây thứ tự bộphận (binary heap). Nhớ lại rằng với cách cài đặt đó, phép toán FindMinchỉ cần thời gian O(1), vì phần tử có khoá nhỏ nhất nằm ở gốc cây; cácphép toán Insert và DeleteMin chỉ đòi hỏi thời gian O(logn), bởi vì để thựchiện các phép toán này chúng ta chỉ cần đi từ lá lên gốc (đối với Insert)hoặc đi từ gốc xuống lá (đối với DeleteMin) và tiến hành hoán vị các dữliệu chứa trong các đỉnh của cây, mà độ cao của cây thứ tự bộ phận n đỉnhlà O(logn). Bây giờ chúng ta xét xem các phép toán hợp nhất và giảm khoáđược thực hiện như thế nào trên cây thứ tự bộ phận. Phép toán hợp nhất Merg(P1, P2). Ở đây chúng ta cần phải kết hợphai cây thứ tự bộ phận P1 và P2 thành một cây thứ tự bộ phận. Cách tốtnhất chúng ta có thể làm là xen từng đỉnh của cây P2 vào cây P1. Giả sửcây P1 có n1 đỉnh, cây P2 có n2 đỉnh. Chúng ta cần sử dụng n2 phép toánInsert, mỗi phép toán này cần thời gian logarit theo số đỉnh trong cây P1.Do đó, phép toán Merg(P1, P2) đòi hỏi thời gian n2log(n1 + n2). Phép toán giảm khoá Decreasekey (P, x, k). Trên cây thứ tự bộ phận,phép toán giảm khoá được tiến hành rất thuận tiện. Đi từ đỉnh chứa x lêngốc (giống như khi ta thực hiện phép toán Insert) nếu khoá k nhỏ hơnkhoá của dữ liệu trong đỉnh cha thì ta hoán vị dữ liệu x và dữ liệu đó. Nhưvậy phép toán giảm khoá trên cây thứ tự bộ phận chỉ cần thời gianO(logn). Tóm lại trên cây thứ tự bộ phận (binary heap), phép toán FindMinchỉ cần thời gian hằng, các phép toán Insert, DeleteMin, Decreasekey chỉcần thời gian logarit. Riêng phép toán Merg, cây thứ tự bộ phận không chophép ta thực hiện hiệu quả phép toán này.12.3 CÂY NGHIÊNG 86 Trong mục này, chúng ta sẽ nghiên cứu sự cài đặt hàng ưu tiên vớiphép toán hợp nhất bởi CTDL tự điều chỉnh được gọi là cây nghiêng(skew heap). Cây nghiêng là cây nhị phân thoả mãn tính chất thứ tự bộphận (hay còn được gọi là tính chất heap), tức là khoá của dữ liệu trongmỗi đỉnh không lớn hơn khoá của dữ liệu trong các đỉnh con của nó. Chú ýrằng, trong cây nghiêng kh ...