Bài giảng 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ằng cá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ảm khoá (Decreasekey). Các phép toán này là rất cần thiết trong thiết kế thuật toá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ới phép toán hợp nhất bởi cây thứ tự bộ phận (binary heap), sau đó chúng ta sẽ 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ích trả góp để đánh giá thời gian chạy của các phép toán hàng ưu tiên trên CTDL 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ử x trong hàng ưu tiên P được xem là đã biết, không cần phải thực hiện thao tác tìm. Trong các ứng dụng, phép toán giảm khoá thường được sử dụng trong vòng lặp sau: loại phần tử có khoá nhỏ nhất khỏi hàng ưu tiên P, rồi xem 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ặp lại quá trình đó cho tới khi hàng ưu tiên P trở thành rỗng. Phép toán giảm khoá là đặc biệt hữu ích trong việc thiết kế các thuật toán cho các vấn đề tố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án hợ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 CTDL nà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ÂY THỨ 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 FindMin chỉ cần thời gian O(1), vì phần tử có khoá nhỏ nhất nằm ở gốc cây; các phép toán Insert và DeleteMin chỉ đòi hỏi thời gian O(logn), bởi vì để thực hiệ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 đỉnh là 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ợp hai cây thứ tự bộ phận P1 và P2 thành một cây thứ tự bộ phận. Cách tốt nhấ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án Insert, 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ên gốc (giống như khi ta thực hiện phép toán Insert) nếu khoá k nhỏ hơn khoá 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 gian O(logn). Tóm lại trên cây thứ tự bộ phận (binary heap), phép toán FindMin chỉ 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 cho phép ta thực hiện hiệu quả phép toán này. 12.3 CÂY NGHIÊNG Trong mục này, chúng ta sẽ nghiên cứu sự cài đặt hàng ưu tiên với phé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 trong mỗ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ông có điều kiện áp đặt nào nhằm hạn chế độ cao của cây. Tuy nhiên mỗi khi tiến hành một phép toán hàng ưu tiên trên cây nghiêng, ta thực hiện một phép điều chỉnh cây với mục đích để các phép toán thực hiện sau đó sẽ hiệu quả hơn. Kết quả là thời gian thực hiện một phép toán riêng biệt trên cây nghiêng có thể là O(n), nhưng thời gian chạy trả góp của mỗi phép toán hàng ưu tiên trên cây nghiêng chỉ là O(logn). 12.3.1 Các phép toán hàng ưu tiên trên cây nghiêng Khi hàng ưu tiên được biểu diễn dưới dạng cây nhị phân thoả mãn tính chất thứ tự bộ phận, chúng ta có thể cài đặt các phép toán khác thông qua phép toán hợp nhất. Trong mô tả các phép toán sau đây, ta ký hiệu S, S1, S2 là các cây nghiêng biểu diễn các hàng ưu tiên, x là một phần tử dữ liệu, k là một giá trị khoá, và p là con trỏ liên kết trong cây trỏ tới đỉnh chứa phần tử cần giảm khoá. Các phép toán được thực hiện như sau: FindMin(S): Trả về phần tử chứa trong gốc cây S. Insert(S, x): Tạo ra cây chỉ có một đỉnh chứa x và hợp nhất cây này với cây S. DeleteMin(S): Loại bỏ gốc cây, rồi hợp nhất cây con trái và cây con phải của S. Decreasekey(S, p, k): Phép toán này có nghĩa là chúng ta cần giảm khoá của phần tử chứa trong đỉnh p của cây nghiêng S với giá trị khoá mới là k. Giả sử S1 là cây con của S có gốc là p, phần tử chứa trong gốc cây S1 bây giờ có khoá là k, S2 là cây nhận được từ cây S bằng cách cắt bỏ nhánh p. Phép toán giảm khoá được thực hiện bằng cách hợp nhất cây S1 và S2. Như vậy vấn đề còn lại là cài đặt phép toán hợp nhất: hợp nhất hai cây nhị phân thoả mãn tính chất thứ tự bộ phận thành một cây nhị phân cũng thoả mãn tính chất đó. Điều này là không có gì khó khăn. Trong cây nhị phân, chúng ta gọi đường bên phải là đường đi xuất phát từ gốc cây và luôn luôn đi theo nhánh bên phải. Chẳng hạn, đường bên phải trong cây hình 12.1c là đường 2 – 3 – 5 - 8 . Chú ý rằng, trong cây nghiêng, các dữ liệu chứa trong các đỉnh trên đường đi bất kỳ từ gốc tới lá được sắp xếp theo thứ tự tăng dần theo khoá. Từ đó, ta có thể đưa ra thuật toán đơn giản sau để hợp nhất hai cây nghiêng S1 và S2: Xét các đường bên phải của cây nghiêng S1 và S2 như các DSLK được sắp theo thứ tự khoá tăng dần. Hợp nhất hai cây nghiêng S1 và S2 được thực hiện bằng cách hợp nhất hai DSLK này thành một DSLK được sắp theo thứ tự khoá tăng dần, trong khi vẫn giữ nguyên các nhánh trái của các đỉnh nằm trên hai DSLK đó. Ví dụ, hợp nhất hai cây nghiêng trong hình 12.1a và 12.1b, chúng ta nhận được cây nghiêng trong hình 12.1c. 3 2 7 6 5 4 8 9 + (a) (b) 2 9 8 7 5 6 4 3 (c) Hình 12.1. Phương pháp hợp nhất đơn giản. Chúng ta cũng có thể thực hiện phương pháp hợp nhất trên bằng thuật toán đệ quy sau. Giả sử khoá của dữ liệu trong gốc của cây S1 nhỏ hơn khoá của dữ liệu trong gốc cây S2. (Nếu ngược lại, ta chỉ cần hoán đổi hai cây S1 và S2). Khi đó hợp nhất của cây S1 với cây S2 là cây S có nhánh trái là nhánh trái của cây S1, còn nhánh phải của S là hợp nhất của cây là nhánh phải của cây S1 với cây S2 (lời gọi đệ quy). Chúng ta có các nhận xét sau về phương pháp hợp nhất trên. Thời gian thực hiện phép hợp nhất phụ thuộc vào độ dài của các đường bên phải của các cây S1 và S2. Nhớ lại rằng, không có điều kiện áp đặt nào nhằm hạn chế độ cao của các cây nghiêng, trong trường hợp xấu nhất các cây nghiêng S1 và S2 có thể chỉ gồm đường bên phải. Do đó trong trường hợp xấu nhất, phương pháp hợp nhất trên đòi hỏi thời gian O(n1 + n2), trong đó n1, n2 là số đỉnh trong cây S1, S2 tương ứng. Cây nghiêng kết quả S có đường bên phải dài hơn các đường bên phải của S1 và S2, tức là khi thực hiện các phép hợp nhất, đường bên phải của cây càng ngày càng dài ra. Nhằm khắc phục nhược điểm này, mỗi khi thực hiện hợp nhất theo phương pháp trên, ta tiến hành kèm theo một phép biến đổi cây. Như vậy, thuật toán hợp nhất hai cây nghiêng gồm hai bước sau: Bước 1. Hợp nhất cây S1 với S2 bằng cách hợp nhất đường bên phải của S1 với đường bên của S2 để nhận được cây S. Bước 2. Trao đổi cây con trái với cây con phải của tất cả các đỉnh nằm trên đường bên phải của cây S nhận được ở bước 1 trừ đỉnh cuối cùng (nó không có nhánh phải). Ví dụ. Giả sử ta cần hợp nhất hai cây nghiêng trong hình 12.2a. Thực hiện bước 1 của thuật toán, ta nhận được cây trong hình 12.2b, thực hiện bước 2 trên cây này, ta nhận được cây kết quả trong hình 12.2c. 3 T1 T2 8 2 5 T3 7 T4 T5 + (a) 2 8 T2 7 5 3 T5 T4 T1 T3 (b) T2 3 2 T5 T4 T1 8 7 T3 5 (c) Hình 12.2. Hợp nhất hai cây nghiêng. (a) Hai cây nghiêng cần hợp nhất (b) Cây nhận được bằng cách thực hiện phương pháp hợp nhất đơn giản: hợp nhất hai đường bên phải. (c) Cây kết quả sau khi trao đổi hai nhánh trái, phải của các đỉnh trên đường bên phải của cây (b) Nhận xét. Bước 2 của thuật toán hợp nhất là phép biến đổi cây mang tính heuristic nhằm hạn chế chiều dài đường bên phải của cây kết quả. Bây giờ chúng ta nói tới sự cài đặt thuật toán hợp nhất hai cây nghiêng gồm hai bước đã trình bày trên. Có thể cài đặt thuật toán này bởi hàm không đệ quy, chúng tôi để lại cách này cho độc giả xem như bài tập. Sau đây chúng ta sẽ cài đặt phép toán hợp nhất bởi hàm đệ quy. Chúng ta giả sử rằng, các đỉnh của cây nghiêng có cấu trúc sau: struct Node { keyType key ; // Các trường dữ liệu khác. Node* left ; // con trỏ tới đỉnh trái. Node* right ; // con trỏ tới đỉnh phải. } ; Giả sử root1, root2 là các con trỏ trỏ tới gốc hai cây nghiêng cần hợp nhất. Hàm hợp nhất đệ quy là như sau: Node* Merg(Node* & root1, Node* & root2) { if ((root1 = = NULL) ((root2 ! = NULL) && (root2 à key) < (root1 à key))) swap (root1, root2) ; // Sau lệnh này, nếu một trong hai cây rỗng thì cây rỗng là root2, // nếu cả hai cây đều khác rỗng thì root1 à key <= root2à key if (root1! = NULL) root1 à right = Merg(root1 à right, root2) ; if (root1 à right! = NULL) swap (root1 à left, root1 à right) ; return root1 ; } Ở đầu mục này, chúng ta đã chỉ ra rằng, các phép toán hàng ưu tiên khác Insert, DeleteMin, Decreasekey được thực hiện như thế nào thông qua phép hợp nhất. Từ đó, sử dụng hàm Merg, bạn đọc dễ dàng cài đặt được các hàm cho các phép toán còn lại trên hàng ưu tiên. Chú ý rằng, bước 2 của thuật toán hợp nhất là bước điều chỉnh cây với mong muốn hạn chế chiều dài của đường bên phải của cây kết quả. Thời gian thực hiện phép hợp nhất trong trường hợp xấu nhất vẫn là O(n), trong đó n là tổng số đỉnh của hai cây cần hợp nhất. Nhưng chúng ta sẽ chỉ ra rằng, nhờ có phép biến đổi cây trong bước 2 mà thời gian chạy trả góp của phép hợp nhất sẽ là O(logn). 12.3.2 Phân tích trả góp Trong mục này chúng ta sẽ đánh giá thời gian chạy trả góp của phép toán Merg trên cây nghiêng. Trước hết, chúng ta cần đến khái niệm đỉnh nặng, đỉnh nhẹ. Định nghĩa 12.1. Trong cây nhị phân, một đỉnh được gọi là đỉnh nặng nếu số đỉnh của cây con phải của nó lớn hơn số đỉnh của cây con trái. Một đỉnh không phải là đỉnh nặng sẽ được gọi là đỉnh nhẹ. Từ định nghĩa trên, chúng ta có các nhận xét sau: Các đỉnh lá của cây là đỉnh nhẹ. Khi thực hiện hợp nhất hai cây nghiêng S1 và S2 thì chỉ có các đỉnh nằm trên đường bên phải của hai cây đó là thay đổi trạng thái nặng, nhẹ. Hơn nữa, các đỉnh nặng nằm trên đường bên phải của hai cây đó sẽ trở thành đỉnh nhẹ trong cây hợp nhất (tại sao?) Chẳng hạn, khi ta hợp nhất hai cây nghiêng trong hình 12.3a và 12.3b, các đỉnh nằm trên đường bên phải của hai cây đó là 2, 6 và 3, trong đó 2 là đỉnh nặng, còn 6 và 3 là đỉnh nhẹ. Trong cây hợp nhất 12.3c, đỉnh nặng 2 trở thành đỉnh nhẹ, và đỉnh nhẹ 3 trở thành đỉnh nặng, đỉnh 6 vẫn còn là đỉnh nhẹ. 3 2 5 4 H L 6 L 8 + 9 7 (a) (b) 2 3 8 6 L 4 H 5 L L 7 9 (c) Hình 12.3. Sự thay đổi trạng thái nặng, nhẹ của các đỉnh khi thực hiện hợp nhất Định lý 12.1. Số đỉnh nhẹ trên đường bên phải của cây nghiêng n đỉnh nhiều nhất là ëlognû + 1. Thật vậy, giả sử cây nghiêng T có gốc là đỉnh v, cây con trái là TL và cây con phải là TR. v T = TL TR Giả sử số đỉnh của cây T là n, của cây con trái TL là nL, của cây con phải TR là nR. Ta có n = nL + nR + 1. Nếu v là đỉnh nhẹ thì nL ³ nR. Do đó n ³ 2nR + 1 > 2nR hay nR < Từ đó ta suy ra rằng, số đỉnh nhẹ trên đường bên phải của cây T nhiều nhất là k, trong đó k là số nguyên lớn nhất sao cho 1 < hay logn > k Cây con phải cuối cùng có thể chỉ gồm một đỉnh (lá), mà đỉnh lá là đỉnh nhẹ. Vậy số đỉnh nhẹ trên đường bên phải của cây nghiêng nhiều nhất là ëlognû + 1. Các nhận xét đã đưa ra và định lý 12.1 sẽ được sử dụng để đánh giá thời gian chạy trả góp của phép hợp nhất. Bây giờ chúng ta xác định hàm tiềm năng f trên một họ các cây nghiêng D = {Si}, trong đó Si là cây nghiêng. Hàm f được xác định như sau f(D) = trong đó ri là số đỉnh nặng trong cây Si. Định lý 12.2. Giả sử các cây nghiêng S1, S2 có số đỉnh là n1, n2 tương ứng. Thời gian chạy trả góp của phép hợp nhất Merg(S1, S2) là O(logn), trong đó n = n1 + n2. Giả sử đường bên phải của cây S1 chứa l1 đỉnh nhẹ và h1 đỉnh nặng, còn đường bên phải của cây S2 chứa l2 đỉnh nhẹ và h2 đỉnh nặng. Như vậy, số đỉnh trên đường bên phải của cây S1 là l1 + h1, của cây S2 là l2 + h2. Do đó, thời gian thực tế để thực hiện phép hợp nhất là c = l1 + l2 + h1 + h2. Chúng ta đánh giá sự thay đổi tiềm năng khi thực hiện phép hợp nhất. Như nhận xét đã đưa ra, khi thực hiện phép hợp nhất, chỉ có các đỉnh nằm trên đường bên phải của hai cây là thay đổi trạng thái nặng, nhẹ. Tất cả các đỉnh nặng trên đường bên phải của hai cây S1 và S2 trở thành đỉnh nhẹ. Mặt khác khả năng nhiều nhất là tất cả các đỉnh nhẹ trên đường bên phải của hai cây đó trở thành đỉnh nặng. Do đó sự thay đổi tiềm năng nhiều nhất là l1 + l2 – h1 – h2. Từ các kết luận trên, ta có thể đánh giá thời gian trả góp của phép hợp nhất như sau: = c + (thay đổi tiềm năng) = l1 + l2 + h1 + h2 + (l1 + l2 – h1 – h2) = 2(l1 + l2) Nhưng theo định lý 12.1, ta có; l1 £ logn1 + 1 và l2 £ logn2 + 1 Vậy £ 2(logn1 + logn2 + 2) £ 4logn trong đó n = n1 + n2. (Bất đẳng thức sau cùng được suy ra từ bổ đề sau: Nếu a + b £ c, trong đó a, b, c là các số thực dương, thì loga + logb £ 2logc – 2) Bất đẳng thức cuối cùng đã hoàn thành chứng minh định lý. Từ định lý 12.2 và thủ tục thực hiện các phép toán Insert, DeleteMin, Decreasekey bằng cách sử dụng phép hợp nhất, chúng ta suy ra kết luận sau: Thời gian trả góp của các phép toán Merg, Insert, DeleteMin, Decreasekey trên cây nghiêng n đỉnh là O(logn), còn thời gian của phép toán FindMin là O(1). Chúng ta còn phải chứng tỏ rằng, thời gian trả góp của một dãy phép toán hàng ưu tiên trên các cây nghiêng là cận trên của thời gian chạy thực tế của dãy phép toán đó. Chúng ta thực hiện dãy phép toán xuất phát từ một họ các hàng ưu tiên chỉ có một phần tử. Như vậy trạng thái ban đầu Do là một họ các cây nghiêng chỉ có một đỉnh gốc. Theo định nghĩa hàm tiềm năng, ta có f(Do) = 0. Giả sử Di là họ các cây nghiêng nhận được sau khi ta thực hiện phép toán thứ i trong dãy. Từ định nghĩa hàm tiềm năng, ta có f(Di) ³ 0 với mọi i. Vận dụng các kết luận đã đưa ra ở cuối mục 11.4, chúng ta suy ra khẳng định cần chứng minh.