Ứng dụng của thuật toán LCA và RMQ trong bài toán xác định băng thông cực đại

Chia sẻ: Minh Minh | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

35
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nghiên cứu này quan tâm tới bài toán LCA và RMQ cùng một số cách tiếp cận để giải quyết chúng. Bên cạnh đó, các tác giả phân tích một ứng dụng quan trọng của lý thuyết đồ thị và mạng máy tính - Bài toán đường truyền bằng thông cực đại.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Ứng dụng của thuật toán LCA và RMQ trong bài toán xác định băng thông cực đại

JOURNAL OF SCIENCE OF HNUE FIT., 2011, Vol. 56, pp. 91-101 ỨNG DỤNG CỦA THUẬT TOÁN LCA VÀ RMQ TRONG BÀI TOÁN XÁC ĐỊNH BĂNG THÔNG CỰC ĐẠI Đoàn Thị Thu Huyền(∗) Học viên cao học K20, Khoa CNTT Trường Đại học Sư phạm Hà Nội Lê Minh Hoàng Trường Đại học Sư phạm Hà Nội (∗) Email: huyendtt88@gmail.com Tóm tắt. Nghiên cứu này quan tâm tới bài toán LCA và RMQ cùng một số cách tiếp cận để giải quyết chúng. Bên cạnh đó, các tác giả phân tích một ứng dụng quan trọng của lý thuyết đồ thị và mạng máy tính: Bài toán đường truyền bằng thông cực đại. Kết quả chính đạt được của nghiên cứu là chỉ ra phép quy dẫn từ bài toán truy vấn băng thông cực đại về bài toán truy vấn LCA trên cây nhị phân đầy đủ, từ đó có thể áp dụng các thuật toán LCA hay RMQ một cách trực tiếp để trả lời mỗi truy vấn trong thời gian hằng số. Các đánh giá về phương pháp có thể chứng minh được bằng lý thuyết và hứa hẹn nhiều mở rộng trong việc ứng dụng xử lý đồ thị động. 1. Mở đầu Bài toán LCA và bài toán RMQ là hai bài toán cổ điển nhưng những nghiên cứu mới về mở rộng của hai bài toán này vẫn được phát triển bởi phạm vi ứng dụng rộng rãi trong lý thuyết cũng như trong thực tế. Tầm quan trọng của bài toán LCA và RMQ thể hiện ở 3 điểm: (1) Những thuật toán kinh điển giải quyết bài toán LCA và RMQ đều là những thuật toán mẫu mực về tính hiệu quả, được chứng minh và đánh giá rõ ràng trong các giáo trình cấu trúc dữ liệu và giải thuật; (2) Rất nhiều thuật toán và ứng dụng thực tế khác cần trả lời truy vấn LCA và RMQ bên trong để tiền xử lý dữ liệu hoặc sử dụng kết quả để xử lý tiếp, việc tăng tốc thuật toán LCA và RMQ sẽ làm tăng tốc thuật toán tổng thể; (3) Có phương pháp quy dẫn tuyến tính từ bài toán LCA sang bài toán RMQ và ngược lại, cho phép phát triển những thuật toán chung cho cả hai bài toán. Bài toán tìm tiền bối chung gần nhất (Lowest Common Ancestors - LCA) phát biểu như sau: Cho một cây có gốc và một loạt các truy vấn. Mỗi truy vấn nhận vào một cặp nút (u, v) và trả về nút tiền bối chung của cả u và v có độ sâu lớn nhất. 91
Đoàn Thị Thu Huyền và Lê Minh Hoàng Bài toán LCA được đề xuất đầu tiên bởi Aho, Hopcroft và Ullman [1]. Rất nhiều thuật toán đã được phát triển với thời gian tiền xử lý tuyến tính, và trả lời mỗi truy vấn trong thời gian hằng số [6,7]. Đặc biệt, Omer Berkman và Uzi Vishkin [8] đã chỉ ra rằng nếu xây dựng một chu trình Euler trên phiên bản có hướng của cây rồi liệt kê các nút theo đúng thứ tự được thăm trong một danh sách, khi đó tiền bối chung gần nhất của hai nút bất kỳ sẽ là đỉnh có độ sâu nhỏ nhất nằm giữa hai nút trong danh sách. Lúc này, truy vấn LCA trở thành truy vấn tìm giá trị nhỏ nhất trong một phạm vi (Range-Minimum Query - RMQ). Bài toán RMQ quản lý một danh sách A gồm n phần tử và trả lời một loạt các truy vấn. Mỗi truy vấn có dạng RMQ(i, j) nhận vào một cặp số (i, j) là chỉ số của hai phần tử trong mảng và trả về chỉ số của phần tử nhỏ nhất trong mảng con A[i..j]. Trong thuật toán quy dẫn từ bài toán LCA về bài toán RMQ sử dụng chu trình Euler, mỗi bài toán LCA tổng quát sẽ được quy dẫn về một trường hợp hạn chế của bài toán RMQ - khi danh sách là số nguyên mà hai phần tử liên tiếp hơn kém nhau đúng 1 đơn vị. Gabow, Bentley và Tarjan [6] lại đề xuất phép quy dẫn tuyến tính theo hướng ngược lại - từ bài toán RMQ về bài toán LCA - bằng cách sử dụng một cấu trúc dữ liệu là cây descartes (cartesian trees). Trước khi có kết quả này, hầu hết các thuật toán RMQ như sử dụng bảng thưa (sparse tables) hay cây quản lý đoạn (segment trees) đều không đạt được yêu cầu:Thời gian tiền xử lý O(n) và thời gian trả lời mỗi truy vấn O(1). Kết quả của Gabow, Bentley và Tarjan cho phép quy dẫn tuyến tính bài toán RMQ về bài toán LCA, sau đó bài toán LCA lại có thể quy dẫn tuyến tính về một trường hợp hạn chế của bài toán RMQ bằng chu trình Euler. Như vậy người ta chỉ cần phát triển các thuật toán RMQ trong trường hợp hạn chế và đã có những thuật toán trả lời truy vấn RMQ trong thời gian O(1) sau một phép tiền xử lý trong thời gian O(n) [4]. Nội dung nghiên cứu chính của bài báo gồm: Giới thiệu bài toán đường truyền băng thông cực đại giữa mọi cặp máy; Trình bày phép quy dẫn về cây khung lớn nhất và bài toán LCA; Mô tả thuật toán quy dẫn sử dụng cây nhị phân đầy đủ đối ngẫu; Kết quả cài đặt thực nghiệm và kết luận. 2. Nội dung nghiên cứu 2.1. Bài toán đường truyền băng thông cực đại Bài toán đường truyền băng thông cực đại phát biểu như sau: Cho mạng gồm n máy và m cáp nối biểu diễn bởi đồ thị vô hướng liên thông có trọng số G = (V, E, b). Trong đó tập đỉnh V là tập các máy, tập cạnh E là tập các cáp nối và hàm trọng số b : E → R cho mỗi cạnh e = (u, v) một trọng số (hay băng thông) b(e) = b(u, v) là băng thông của dây cáp mạng e. Mỗi đường đi từ s tới t trên đồ thị tương ứng 92
Ứng dụng của thuật toán LCA và RMQ trong bài toán xác định băng thông cực đại với một đường truyền từ máy s tới máy t. Định nghĩa băng thông của một đường truyền là băng thông nhỏ nhất của một dây cáp mạng trên đường truyền. Tức là nếu Ps = p1 , p2 , . . . , pk = t là một đường truyền từ máy s tới máy t thì băng thông của đường truyền này, ký hiệu b(P ) = min1≤i
Đoàn Thị Thu Huyền và Lê Minh Hoàng Như vậy, thuật toán Dijkstra có thể sửa đổi để tìm đường truyền băng thông cực đại xuất phát từ một đỉnh. Bằng sự hỗ trợ của một số cấu trúc dữ liệu hàng đợi ưu tiên như Fibonacci Heaps, thời gian thực hiện giải thuật Dijkstra là: O(|V | log |V | + |E|) Ta cũng có thể sửa đổi thuật toán Floyd để tìm băng thông cực đại giữa mọi cặp đỉnh trong thời gian O(|V |3 ). Trong trường hợp đồ thị thưa, việc xác định đường truyền băng thông cực đại giữa mọi cặp đỉnh có thể sử dụng thuật toán Johnson (thực hiện |V | lần Dijkstra với tất cả các cách chọn đỉnh xuất phát), với thời gian thực hiện giải thuật là: O(|V |2 log |V | + |V ||E|). Thuật toán Dijkstra và thuật toán Floyd hoàn toàn có thể tìm băng thông cực đại trong trường hợp đồ thị có trọng số âm, thậm chí có chu trình âm. Việc chứng minh tính đúng đắn của thuật toán có thể làm tương tự như trong lý thuyết bài toán đường đi ngắn nhất [3]. Tuy nhiên với những cách tiếp cận đơn giản kể trên, để tính băng thông cực đại giữa hai đỉnh mất thời gian O(|V | log |V | + |E|) và để tính băng thông cực đại giữa mọi cặp đỉnh mất thời gian O(|V |3 ). Kết quả lý thuyết và thực nghiệm đều cho thấy chương trình cài đặt các giải thuật trên thực hiện khá chậm trong trường hợp đồ thị lớn và số truy vấn nhiều. Điều này chỉ ra sự cần thiết của những thuật toán hiệu suất cao sẽ được trình bày trong những phần sau. 2.2. Quy dẫn về cây khung lớn nhất Cây khung lớn nhất của đồ thị là cây khung có tổng trọng số cạnh lớn nhất. Những thuật toán tìm cây khung nhỏ nhất đều có thể áp dụng để tìm cây khung lớn nhất bằng cách đổi dấu tất cả các trọng số cạnh của đồ thị. Bổ đề sau đây là cở sở cho phép quy dẫn bài toán đường truyền băng thông cực đại về bài toán tìm đường đi trên cây. Bổ đề 2.2. (Phép quy dẫn về đường đi trên cây khung lớn nhất) Gọi T là cây khung lớn nhất của đồ thị G, khi đó với mọi cặp đỉnh (s, t) tồn tại một đường truyền băng thông cực đại từ s tới t là đường đi đơn duy nhất từ s tới t trên cây khung T . Chứng minh. Trong số các đường truyền băng thông cực đại từ s tới t, chọn P là một đường truyền có ít cạnh ngoài T nhất. Ta sẽ chứng minh rằng P không chứa cạnh ngoài T . Thật vậy nếu trên P có cạnh e(u, v) ∈ / T , việc kết nạp e vào T sẽ tạo ra đúng một chu trình đơn C. Cạnh e phải là cạnh có băng thông nhỏ nhất trong số cách 94
Ứng dụng của thuật toán LCA và RMQ trong bài toán xác định băng thông cực đại cạnh thuộc C vì nếu có cạnh e′ ∈ C có b(e′ ) < b(e), thì ta có thể loại e′ khỏi T và bổ sung vào T cạnh e, được cây khung mới lớn hơn cây khung T , điều này mâu thuẫn với giả thiết T là cây khung lớn nhất. Vì e là cạnh có băng thông nhỏ nhất trong các cạnh thuộc C, ta có thể thay thế cạnh e = (u, v) trên đường truyền P bởi các cạnh còn lại của chu trình C sau khi đã loại bỏ đi cạnh e, điều này không làm giảm băng thông của đường truyền mà còn thu được một đường truyền mới chứa ít cạnh ngoài T hơn so với đường P , điều này mâu thuẫn với cách chọn P là đường truyền băng thông cực đại chứa ít cạnh ngoài T nhất. Bổ đề 2 cho phép chúng ta chỉ cần quan tâm tới những cạnh thuộc cây khung lớn nhất mà không cần quan tâm tới những cạnh khác của đồ thị. Đường đi đơn giữa hai đỉnh trên cây khung là duy nhất, được thực hiện bằng cách di chuyển từ một đỉnh lên tiền bối chung gần nhất sau đó di chuyển tới đỉnh còn lại. Từ đó ta có thuật toán: Chọn một đỉnh bất kỳ làm gốc, dùng một thuật toán tìm kiếm trên đồ thị (BFS/DFS) để xác định thứ tự cha/con của các đỉnh trên cây khung cũng như độ sâu của chúng. Với mỗi đỉnh v, ký hiệu d[v] là độ sâu của đỉnh v, ký hiệu p[0, v] là đỉnh cha của đỉnh v(quy ước p[0, "gốc" ] = 0). Ký hiệu q[0, v] là trọng số cạnh nối v với đỉnh cha p[0, v] của nó. Với 1 ≤ i ≤ lg |V |, các giá trị p[i, v] được định nghĩa là đỉnh tiền bối của v, đến được từ v sau 2i bước di chuyển lên gốc và giá trị q[i, v] là băng thông nhỏ nhất của một cạnh trên đường di chuyển, dễ dàng tính được những giá trị này bằng các công thức truy hồi sau: u := p[i − 1, v] p[i, v] := p[i − 1, u] q[i, v] := min{q[i − 1, v], q[i − 1, u]} Phép tiền xử lý cho phép ta cài đặt phép nhảy xa bằng con trỏ p[..]: Để từ nút v đi lên k bước về phía gốc, ta phân tích k thành tổng các lũy thừa của 2 bằng thuật toán chuyển đổi cơ số nhị phân: k = 2i1 + 2i2 + ... + 2ij . Sau đó từ v nhảy lên u1 = p[i1 , v], từ u1 nhảy lên u2 = p[i2 , u1], từ u2 nhảy lên u3 = p[i3 , u2 ]. . . cuối cùng ta nhảy lên uj = p[ij , uj−1], hoàn thành phép di chuyển k bước chỉ bằng O(lg k) phép nhảy. Để trả lời mỗi truy vấn về băng thông cực đại giữa s và t. Ta di chuyển từ s và t lên nút tiền bối chung và trả về băng thông nhỏ nhất của một cạnh trên đường di chuyển: Trước hết là từ nút sâu hơn nhảy lên cho bằng độ sâu của nút còn lại, sau đó từ hai nút nhảy theo các bước từ xa đến gần cho tới khi tới được nút tiền bối chung. function Query(s, t ∈ V ) : R; 6 Trả về băng thông giữa s và t 95
Đoàn Thị Thu Huyền và Lê Minh Hoàng begin β := +∞; if d[s] < d[t] then //Đảo giá trị s và t; for i := [lg |V |] downto 1 do //Chỉnh cho 2 đỉnh cùng độ sâu if d[s] − 2i ≥ d[t] then begin //Cho s nhảy lên 2i bước β := min{β, q[i, s]}; s := p[i, s]; end; if s 6= t then begin for i := [lg |V |] downto 1 do if p[i, s] 6= p[i, t] then begin //Nhảy cả s và t lên 2i bước β := min{β, q[i, s], q[i, t]}; s := p[i, s]; t := p[i, t]; end; β := min{β, q[0, s], q[0, t]}; end; return β; end; Sau các phép tiền xử lý: Tìm cây khung lớn nhất (O(|V | log |V | + E))xác định các con trỏ nhảy xa (O(|V | lg |V |)), việc tìm băng thông cực đại giữa hai đỉnh bất kỳ có thể thực hiện trong thời gian O(lg |V |). Kết quả này tỏ ra tốt hơn thuật toán Dijkstra nếu phép truy vấn băng thông cực đại được gọi thực hiện nhiều lần. Thuật toán sử dụng cây nhị phân đầy đủ đối ngẫu. Thời gian thực hiện giải thuật O(lg |V |) cho mỗi truy vấn băng thông cực đại đã là khá tốt trong các ứng dụng thực tế, khi mà pha tiền xử lý chỉ cần thực hiện một lần với thời gian không đáng kể. Tuy nhiên vẫn còn có phương pháp tốt hơn nữa để trả lời mỗi truy vấn băng thông cực đại. Thuật toán dưới đây dựa trên cơ chế xây dựng cây nhị phân đầy đủ đối ngẫu song song với quá trình tìm cây khung lớn nhất, nó có những ưu điểm chính sau: - Có thể trả lời mỗi truy vấn băng thông cực đại trong thời gian hằng số (O(1)). - Dễ dàng tìm lại đường truyền băng thông cực đại sau mỗi truy vấn. - Việc tìm băng thông cực đại được trả lời trực tiếp bằng truy vấn LCA trên cây nhị phân đầy đủ mà không cần các cấu trúc dữ liệu phụ trợ như con trỏ nhảy xa. Điều này cho phép áp dụng trực tiếp các thuật toán LCA hay quy dẫn về bài 96
Ứng dụng của thuật toán LCA và RMQ trong bài toán xác định băng thông cực đại toán RMQ mà không cần một sửa đổi nào. - Chính vì việc có thể áp dụng trực tiếp các thuật toán LCA và RMQ, phương pháp này có cơ hội mở rộng để xử lý truy vấn động: khi băng thông của các cạnh liên tục thay đổi đi kèm với các truy vấn băng thông cực đại. Với đồ thị gồm n đỉnh, m cạnh, trước hết, ta xây dựng cây khung lớn nhất bằng thuật toán Kruskal. Thuật toán Kruskal trước hết khởi tạo một họ các tập rời nhau S1 , S2 , . . . , Sn , mỗi tập chứa một đỉnh của đồ thị. Với mỗi tập Si , ta cho tương ứng với nó một cây nhị phân đầy đủ B(Si ) chứa các đỉnh của Si trong lá. Ban đầu tất cả các cây B(Si ) cũng chỉ gồm một nút duy nhất chứa một đỉnh của Si . Thuật toán Kruskal duyệt các cạnh theo thứ tự từ băng thông lớn tới băng thông nhỏ. Mỗi khi duyệt cạnh (u, v), thuật toán xác định Si và Sj lần lượt là hai tập chứa u và v. Nếu Si 6= Sj , hai tập này sẽ được hợp nhất lại thành một tập Sk , tức là thuật toán hủy đi hai tập Si ,Sj và kết nạp vào một tập Sk = Si ∪ Sj . Song song với quá trình đó, ta tạo một nút nhánh chứa cạnh (u,v), cho B(Si ) và B(Sj ) lần lượt là con trái và con phải nút nhánh này để được cây B(Sk ) tương ứng với tập Sk mới tạo ra. Khi thuật toán Kruskal kết thúc và xác định cây khung lớn nhất T . Ta cũng thu được một cây nhị phân B với các nút lá là các đỉnh và các nút nhánh là các cạnh. Đây là cây nhị đầy đủ (full binary trees) - mỗi nút nhánh có đúng 2 nút con. Thuật toán xây dựng cây nhị phân đầy đủ đối ngẫu. Input: G = (V, E, b) có các đỉnh đánh số từ 1 tới n và m cạnh đánh số từ 1 tới m. Cạnh ei nối hai đỉnh ui , vi Output: Cây khung lớn nhất T và cây nhị phân đầy đủ đối ngẫu B. Sắp xếp ds cạnh: b(e1 )b(e2 ) ≥ ... ≥ b(em ); for u := 1 to n do begin Su := u; B(Su ) := Node(u); end; T := Ø; for i := 1 to m do begin Si := ”F indSet”(ui ); Sj := ”F indSet”(vj ); if Si 6= Sj then begin T := T ∪ {ei }; Sk := ”Union”(Si , Sj ); B(Sk ) := Node(ei ); 97
Đoàn Thị Thu Huyền và Lê Minh Hoàng B(Sk ).Lef t := B(Si ); B(Sk ).Right := B(Sj ); end; end; S :="Tập duy nhất còn lại trong họ tập rời nhau" ; ∗ return Cây khung lớn nhất T , cây nhị phân đầy đủ đối ngẫu B = B(S ∗ ); Để tìm băng thông cực đại giữa đỉnh s và đỉnh t: từ lá s và t trên cây nhị phân đầy đủ B, ta tìm nút tiền bối chung gần nhất của chúng. Băng thông của cạnh e chứa trong nút tiền bối chung gần nhất chính là băng thông cực đại của đường truyền từ s tới t. Tính đúng đắn của thuật toán có thể chứng minh như sau: Nếu cạnh e nằm trong nút tiền bối chung gần nhất, thì e là cạnh đầu tiên thuật toán Kruskal kết nạp vào cây khung mà cho phép đi giữa s và t trên cây. Những cạnh đã kết nạp trước đó luôn tách s,t vào hai thành phần liên thông khác nhau, những cạnh kết nạp sau đó đều có băng thông nhỏ hơn e. Vì vậy đường đi từ s tới t trên cây khung lớn nhất có cạnh e là cạnh mang băng thông nhỏ nhất, đó chính là băng thông cực đại giữa s và t. Bởi phép truy vấn băng thông cực đại được thực hiện trực tiếp bởi truy vấn LCA trên cây nhị phân đầy đủ, bất kỳ thuật toán LCA nào cũng có thể áp dụng được. Cũng có thể áp dụng phép quy dẫn về bài toán RMQ và sử dụng các thuật toán RMQ. Định lí 2.1. Có thể trả lời mỗi truy vấn băng thông cực đại trong thời gian O(1) với thời gian tiền xử lý O(|E| log |E|). Chứng minh. Thuật toán sắp xếp danh sách cạnh có thể dùng HeapSort hoặc Merge Sort O(|E| log |E|). Nếu dùng các thuật toán sắp xếp số học còn có thể đạt hiệu quả cao hơn. Thuật toán Kruskal với cấu trúc dữ liệu dùng các tập rời nhau (disjoint-set forest) kết hợp với hai kỹ thuật: hợp theo hạng (union-by-rank) và nén đường (path compression) có thời gian thực hiện O(|E|α(|V |)) CITATION Cormen_IA l1033 [3]. Phép dựng cây nhị phân đầy đủ mất thời gian O(|V |). Vì đồ thị liên thông nên E = Ω(|V |), ta có tổng thời gian tiền xử lý là O(|E| log |E|). Trong trường hợp các cặp đỉnh trong các truy vấn băng thông cực đại được biết trước, có thể dùng thuật toán Tarjan’s Offline LCA để trả lời toàn bộ k truy vấn trong thời gian O(n + k). Một phương pháp khác là mất thêm thời gian O(n) để quy dẫn về bài toán RMQ, sau đó mỗi truy vấn LCA được lại được quy dẫn về một truy vấn RMQ, thực hiện trong thời gian O(1), phương pháp này có thể sử dụng ngay cả khi các truy vấn là không biết trước. 98
Ứng dụng của thuật toán LCA và RMQ trong bài toán xác định băng thông cực đại 2.3. Cài đặt thực nghiệm Mặc dù các kết quả thu được có thể chứng minh chặt chẽ bằng lý thuyết. Việc cài đặt thêm một vài thực nghiệm là cần thiết để đánh giá tác động của hằng số ẩn trong ký pháp đánh giá thời gian thực hiện giải thuật. Các thực nghiệm được cài đặt trên máy tính có cấu hình như sau: CPU AMD 64X2 5200MHz (2600MHz/core), RAM 4GB, hệ điều hành Windows 7 64 bit, môi trường phát triển RAD Studio XE. Dữ liệu là 10 nhóm đồ thị, mỗi nhóm chứa 10 đồ thị ngẫu nhiên có số đỉnh (n) bằng số hiệu nhóm ×105 . Thời gian thực hiện với một nhóm được tính bằng thời gian trung bình thực hiện trên một đồ thị của nhóm. Có ba thuật toán được thử nghiệm: - Thuật toán A: Sử dụng con trỏ nhảy xa như đã đề cập ở mục 3. - Thuật toán B: Sử dụng cây nhị phân đầy đủ đối ngẫu và thuật toán Tarjan’s Offline LCA [7]. - Thuật toán C: Sử dụng cây nhị phân đầy đủ đối ngẫu, dùng chu trình Euler quy dẫn về bài toán RMQ sau đó thực hiện thuật toán RMQ [4]. Thuật toán Dijkstra và Floyd đã có nhiều nghiên cứu khác đánh giá, hơn nữa, chúng có thời gian thực hiện quá chậm, không thích hợp với kích thước đồ thị lớn và số truy vấn nhiều. Trong các thực nghiệm, thời gian trả lời riêng lẻ từng truy vấn băng thông cực đại là rất nhỏ và rất khó đo được trên máy tính. Chúng tôi khắc phục bằng cách đo tổng thời gian thực hiện trên 10 triệu truy vấn ngẫu nhiên. Thực nghiệm 1. Được tiến hành để đo riêng thời gian tiền xử lý với từng thuật toán. Thời gian nhập/xuất dữ liệu và dựng cây khung lớn nhất không được tính vì những pha này có mặt trong cả ba thuật toán. Giải thuật Tarjan’s Offline LCA không cần tiền xử lý dữ liệu mà chỉ cần biết trước danh sách các truy vấn, vì vậy thuật toán B không có mặt trong thực nghiệm này Thời gian tiền xử lý dữ liệu của thuật toán A và thuật toán C chỉ phụ thuộc vào số đỉnh của đồ thị. Hình 1 là biểu đồ thời gian tiền xử lý dữ liệu (tính bằng giây). Cả hai thuật toán đều mất thời gian ít hơn 0,6 giây để tiền xử lý, ngay cả với những đồ thị có tới 1 triệu đỉnh. Thuật toán A mất thời gian O(n log n) để tiền xử lý dữ liệu (chủ yếu vào việc tính sẵn bảng các con trỏ nhảy xa), trong khi đó thuật toán C chỉ mất thời gian O(n). Đồ thị biến thiên thời gian tiền xử lý của C có xu hướng như một đường thẳng. 99
Đoàn Thị Thu Huyền và Lê Minh Hoàng Hình 1. Hình 2. Thực nghiệm 2. Được tiến hành để đo thời gian trả lời 10 triệu truy vấn của từng thuật toán, không tính thời gian nhập/xuất dữ liệu, dựng cây khung và tiền xử lý. Biểu đồ thời gian thực hiện giải thuật được chỉ ra trong Hình 2. Thuật toán A trả lời k truy vấn trong thời gian O(k log n). Với đồ thị cỡ 1 triệu đỉnh, thuật toán A cần thời gian xấp xỉ 21,31 giây để trả lời 10 triệu truy vấn. Thuật toán B trả lời k truy vấn trong thời gian O(n + k), trong thực nghiệm với số truy vấn cố định và số đỉnh nhỏ hơn rất nhiều so với số truy vấn, kích thước đồ thị tác động rất ít lên thời gian thực hiện giải thuật. Đây cũng là thuật toán đạt tốc độ tốt nhất trong thử nghiệm (7,8 giây cho 10 triệu truy vấn trên đồ thị 1 triệu đỉnh) Thuật toán C trả lời k truy vấn trong thời gian O(k), không phụ thuộc kích thước đồ thị. Mặc dù vậy, đồ thị biến biến thiên thời gian của thuật toán C chỉ có xu hướng là hàm hằng bắt đầu từ những giá trị n > 900.000. Lý do là khi đồ thị có kích thước nhỏ, phần lớn dữ liệu sẽ được nạp vào bộ nhớ cache của CPU và xử lý nhanh hơn trường hợp phần lớn dữ liệu phải lưu trữ trong RAM đối với đồ thị lớn.z 3. Kết luận Bài toán LCA và bài toán RMQ là hai bài toán có mỗi quan hệ chặt chẽ. Nhiều thuật toán đã được phát triển, cho phép trả lời mỗi truy vấn LCA hay RMQ trong thời gian O(1). Nghiên cứu này khảo sát bài toán đường truyền bằng thông cực đại trên mạng vô hướng, kỹ thuật quy dẫn về cây khung lớn nhất và bài toán tìm đường đi đơn trên cây khung. Đóng góp chính của nghiên cứu là đưa ra mô hình dựng cây nhị phân đầy đủ đối ngẫu, quy việc tìm băng thông cực đại về tìm nút LCA, và từ đó có thể áp dụng trực tiếp các thuật toán LCA hoặc RMQ để trả lời các truy vấn băng thông cực đại trong thời gian thời gian O(1). Một trong những mở rộng của bài toán tìm băng thông cực đại là đưa vào xử lý trực tuyến trong tình trạng băng thông của các cạnh luôn biến đổi đi kèm với các truy vấn. Trong trường hợp này, cấu trúc cây khung lớn nhất có thể bị biến động 100
Ứng dụng của thuật toán LCA và RMQ trong bài toán xác định băng thông cực đại mỗi khi băng thông của một cạnh bị thay đổi. Điều này làm cho tất cả các thuật toán có pha tiền xử lý dữ liệu đều gặp khó khăn do phải tổ chức lại dữ liệu từ đầu. Việc phát triển các thuật toán quy dẫn động là vô cùng cần thiết để nhanh chóng chuyển đổi mỗi truy vấn băng thông cực đại về một truy vấn LCA, đó cũng là một hướng nghiên cứu tiếp theo của đề tài. REFERENCES [1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, 1973. On finding lowest common ancestors in trees. Proceedings of the fifth annual ACM symposium on Theory of computing, pp. 253-265, 1973. [2] Stephen Alstrup, Cyril Gavoille, Haim Kaplan, and Theis Rauhe, 2004. Nearest Common Ancestors: A Survey and a New Algorithm for a Distributed Environ- ment. Theory of Computing Systems, Vol. 37, No. 3, pp. 441-456. [3] Thomas H. Cormen, Charles Eric Leiserson, Ronald Linn Rivest, and Clifford Stein, 2009. Introduction to Algorithms. 3rd ed.: MIT Press. [4] Johannes Fische and Volker Heun, 2007. A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array. Lecture Notes in Computer Science, Vol. 4614, pp. 459-470. [5] Johannes Fische and Volker Heun, 2006. Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE. Lecture notes in Com- puter Science, Vol. 4009, pp. 36-48. [6] Harold N. Gabow, Jon Louis Bentley, and Robert E. Tarjan, 1984. Scaling and related techniques for geometry problems. Proceedings of the sixteenth annual ACM symposium on Theory of computing, pp. 135-143. [7] Dov Harel and Robert Endre Tarjan, 1984. Fast Algorithms for Finding Nearest Common Ancestors. SIAM Journal on Computing, Vol. 13, No. 2, pp. 338-355. [8] Uzi Vishkin Omer Berkman, 1993. Recursive Star-Tree Parallel Data Structure. SIAM Journal on Computing, Vol. 22, No. 2, pp. 221-242. ABSTRACT Apply LCA and RMQ algorithm in Finding maximum-bandwidth paths problem This paper focused on algorithms to solve LCA/RMQ problems and analyzed an important application of graph theory and computer network: Finding Maximum- Bandwidth Paths. Our main result is proposing a reduction from Maximum-Bandwidth problems to LCA problems on a complete binary tree. Afterwards, LCA and RMQ algorithms can be directly used to answer each query in constant time. Evaluations on this method can be theoretically proved, and it promises to be extended for finding maximum-bandwidth paths in dynamic networks. 101