CHƯƠNG 1 BÀI TOÁN CÂY KHUNG VỚI CHI PHÍ LỘ TRÌNH NHỎ NHẤT 1.1 Giới thiệu bài toán cây khung với chi phí lộ trình nhỏ nhất. Bài toán cây khung với chi phí lộ trình nhỏ nhất (Minimum Routing Cost Spanning Tree - MRCT) còn có tên khác là Shortest Total Path Length Spanning Tree thuộc lớp NP-khó. Đối với bài toán MRCT, số lượng và vị trí các nút mạng được đưa ra theo thứ tự ưu tiên và giá của cây được xác định bởi giá của các liên kết. Lưu lượng của một liên kết là tổng của tất cả các yêu cầu truyền thông giữa tất cả các cặp nút truyền trực tiếp hay gián tiếp qua liên kết đó.
Mục đích của chúng ta là tìm ra cây khung của đồ thị với tổng độ dài đường đi giữa mọi cặp đỉnh trên cây khung là cực tiểu. Độ dài đường đi giữa 2 đỉnh được tính bằng tổng trọng số của các cạnh trên đường đi nối giữa 2 đỉnh này với nhau. Xây dựng cây khung chi phí lộ trình nhỏ nhất cũng tương đương với việc xây dựng cây khung sao cho độ dài trung bình giữa mọi cặp đỉnh là nhỏ nhất. Bài toán được phát biểu như sau: Cho G là một đơn đồ thị vô hướng liên thông có trọng số là độ trễ (chí phí) không âm.
Mục tiêu của bài toán là tìm cây khung T là một cây khung nào đó của G sao cho độ trễ trung bình của tất cả các mối liên lạc giữa tất cả các cặp đỉnh trên cây là nhỏ nhất. Ma trận khoảng cách duv xác định trọng số khoảng cách giữa các cặp R R đỉnh, trong đó chi phí lộ trình của một cặp đỉnh (u,v) ký hiệu là dT (u,v) là tổng trọng R R số trên tất cả các cạnh của đường đi trên cây T nối đỉnh u với đỉnh v. Ta gọi chi phí lộ trình (Routing cost) của cây khung T ký hiệu là C(T) là tổng các chi phí lộ trình giữa mọi cặp đỉnh thuộc cây T được tính theo công thức sau: C (T ) = ∑ u ,v dT (u , v) (1) trong đó dT (u,v) được tính toán theo cấu trúc cây T. T là cây khung với chi phí R R lộ trình nhỏ nhất nếu c(T) ≤ c(T') với T' là cây khung bất kì.
Bài toán MRCT là bài toán thuộc lớp NP-Khó. Một số nhận xét về bài toán MRCT như sau: 11 • Bài toán MRCT trên đồ thị tổng quát là tương đương với bài toán MRCT trên đồ thị trong không gian metric. • Tồn tại thuật toán xấp xỉ với tỉ lệ 1.577 để giải MRCT trong trường hợp đồ thị tổng quát với độ phức tạp thời gian tính cỡ () • Cây khung k-star là cây khung mà có tối đa k nút trong. Cây khung định tuyến k-star nhỏ nhất (minimum routing cost k-star) là một lời giải xấp xỉ cho bài toán MRCT • Với giá trị k cho trước cây khung định tuyến k-star nhỏ nhất trên không gian metric có thể tìm được trong thời gian đa thức F E E B G D C A H I Hình 1.1: Một cây khung 3-star trong đó B,C,E là các nút trong và A,D,E,F,G,H là các nút lá F G E E B D C A H Hình 1.2: Cây khung 1-star với B là nút trong và các nút còn lại là nút lá 12 Ví dụ 1: Cho cây khung T như hình vẽ sau: Hình 1.3: Cây khung 2-star Theo công thức (1), ta có : d T (v1,v 2) + d T (v 1,v3 ) + d T (v 1,v4 ) + d T (v1 ,v5 ) + d T (v2 ,v3) + d T (v 2 ,v4) + R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R d T (v2,v 5) + dT (v 3 ,v4) + d T (v3 ,v5) + d T (v4 ,v5 ) = 98.
R R R R R R R R R R R R R R R R R R R R R R R R Do dT (vi ,vj ) = dT (vj ,vi ), nên C(T) = 98 x 2 = 196 R R R R R R R R R R R R Bài toán MRCT đặt ra là tìm một cây khung có chi phí lộ trình nhỏ nhất trong tất cả các cây khung có thể có của G. Theo công thức của Cayley thì số cây khung của đồ thị n nút là nn-2 và có n P P cây hình sao trong số đó. Khoảng cách giữa 2 cây Ti và Tj là dhij ={0,1,.,n-2} được R R R R P P R R định nghĩa như sau: n −1 u −1 dhij = ∑ | luvi − luvj | = ∑∑ | luvi − luvj | P P R R u ,v ∈V u =1 v =0 liuv =1 nếu có liên kết từ u đến v trong T i và li uv =0 nếu ngược lại. P P R R R R P P R R Vậy số các liên kết giống nhau của cây T i và T j được tính bằng: n-1-½d hij R R R R P P R Cũng giống như các bài toán cây khung có ràng buộc khác thì bài toán MRCT thuộc dạng NP-khó, chính xác là thuộc MAX SNP-khó có nghĩa là nó không thể được giải được trong thời gian xấp xỉ hàm mũ trừ khi P=NP.
Để làm cơ sở tính toán cho bài toán MRCT, ta có định nghĩa sau: Routing load: Cho T là một cây khung của G, ký hiệu E(T) là tập các cạnh của cây T, (u,v)∈ E(T). Khi loại cạnh (u,v) khỏi cây T thì cây T được tách thành hai đồ thị con là X và Y có số đỉnh lần lượt là |V(X)|, |V(Y)|. Khi đó routing load (tải năng) của cạnh (u,v) được định nghĩa theo công thức sau: l(T,(u,v)) = 2V(X)V(Y). 13 Gọi SP G (u,v) là đường đi ngắn nhất giữa hai đỉnh u và v trên đồ thị G.
Khi G R R là một cây thì SPG (u,v) là đường đi đơn duy nhất giữa hai đỉnh u và v. Từ khái niệm R R routing load ta có công thức tính Routing cost theo công thức (1) có thể viết như sau: C (T ) = ∑ l (T , (u , v )). Ngoài chi phí của các cạnh thì hình dáng của cây khung ảnh hưởng rất nhiều đến chi phí lộ trình của cây khung. Ví dụ: cho đồ thị G với tất cả các cạnh có trọng số là 1 và 2 cây khung T 1 và R R T 2 của G.
Khi đó cây T 1 là MRCT R R R R R R R R Hình 1.4: Đồ thị G và routing cost của hai cây khung T1 và T 2 của GR R R R Dựa vào công thức (1) trọng số của các cạnh là yếu tố quan trọng nhất để tính routing cost. Mặt khác dựa vào công thức (2) ta thấy hình dạng (topology) của cây cũng là yếu tố quyết định cho việc xây dựng cây khung nhỏ nhất. Ví dụ cho T1 là R R cây chỉ có một nút trong (hình sao) với mỗi cạnh có trọng số là 5 và T2 là đường R R thẳng với mỗi cạnh có trọng số là 1, giả sử cả hai cây là cây khung của một đồ thị có n đỉnh. Nếu xét tổng trọng số các cạnh (cây khung nhỏ nhất) cây T2 tốt hơn cây R R T 1.
Mặt khác, nếu xét về routing cost cây T 1 có routing load của mỗi cạnh đều bằng R R R R 14 2(n-1) vì mỗi cạnh đều có một đỉnh lá do đó C(T 1 )=10(n-1)2 trong khi cây T 2 =(v 1 , R R P P R R R R v2 ,. , 2(n-1) và C(T2 ) R R tính như sau: n( n − 1)(2n − 1) n(n − 1)(n + 1) C(T2 )= ∑ 2i ( n − i) = n 2 (n − 1) − = 3 3 R R 1≤i ≤n −1 Cây T 1 sẽ tốt hơn cây T 2 nhiều khi n đủ lớn.5: Hai topology cây ảnh hưởng đến routing cost 1.2 Các thuật toán Meta-heuristics giải bài toán MRCT. Các thuật toán Metaheuristics có thể phân làm hai lớp: lớp thứ nhất bao gồm các thuật toán lặp lại quá trình tinh chỉnh một lời giải để tìm lời giải tốt hơn và lớp thứ hai bao gồm các thuật toán lặp lại quá trình tinh chỉnh một tập nhiều lời giải (một quần thể các lời giải) để tìm tập lời giải tốt hơn và khi quá trình kết thúc thì lời giải tốt nhất của quần thể ở thế hệ cuối cùng sẽ là lời giải cần tìm. Ở lớp thứ nhất có các thuật toán điển hình như: Thuật toán tham lam (Greedy), thuật toán tìm kiếm leo đồi (Hill Climbing Search), thuật toán tìm kiếm ưu tiên tối ưu (Best First Search-BFS), thuật toán Tabu Search (Tabu Search - TS), thuật toán tìm kiếm cục bộ (Local Search), thuật toán tôi luyện thép (Simulated Annealing - SA), thuật toán Đại hồng thủy(Great Deluge-GD),… Ở lớp thứ hai có các thuật toán điển hình như: Thuật toán di truyền (Genetic Algorithm - GA) , thuật toán Memetic (Memetic Algorithms - MA), thuật toán đàn kiến (Ant Colony Optimizationv- ACO), thuật toán tối ưu bầy đàn (Particle Swarm Optimization - PSO), thuật toán 15 tìm kiếm sự hòa hợp (Harmony Search – HS), thuật toán bầy Ong (Bees Algorithm - BA), thuật toán Firefly Algorithm (FA), … Ngoài họ các thuật toán Metaheuristic trên còn một số thuật toán xấp xỉ (Approximation Algorithms) được sử dụng trong việc giải quyết bài toán MRCT.
Gần đây Grout [8] đã xây dựng một thuật toán xấp xỉ dựa trên phương pháp tham lam để giải bài toán MRCT gọi là thuật toán Add cho ra kết quả rất tốt trên các đồ thị đồng nhất (tức là trọng số của các cạnh là như nhau) và có độ phức tạp tính toán thấp hơn so với thuật toán của Wong. Tư tưởng chủ đạo của thuật toán này là dựa trên giả định rằng một cây khung sẽ có chi phí lộ trình thấp nếu nó có càng nhiều nút lá càng tốt. Vì vậy thuật toán chủ yếu xoay quanh việc xây dựng cây khung với nhiều nút lá nhất có thể. Mặc dù thuật toán không đưa ra được một đánh giá nào về cận dưới hay cận trên cho kết quả thu được nhưng khi áp dụng trong thực tiễn thì thuật toán cho ra kết quả khá tốt.
Khiếm khuyết của thuật toán này là đối với các đồ thị không đồng nhất, kết quả cho ra khá tồi. Dựa trên thuật toán Add của Grout, Campos và các cộng sự [9] gần đây đã phát triển thuật toán Campos cho ra kết quả tương đối tốt trên cả đồ thị đồng nhất lẫn không đồng nhất.