CHƯƠNG IX CÁC THUẬT TOÁN XỐP x ỉ
3. BÀI TOÁN PHỦ Đ ÌN H
Cho G = (V, E) là một đồ thị vô hướng. Một phủ đỉnh của G là một tập con V' các đỉnh của V, V' C V, sao cho nếu (ằ, v) là một cạnh của G thỡ hoặc u e hoặc V e V' (hoặc cả II và V'
đều thuộc K'). Kích thước của phủ đỉnh V ' là số đỉnh của tập
Bài toán phủ đỉnh là tìm một phủ đỉnh có kích thước cực tiểu trong một đồ thị vô hướng cho trước. Một phủ đỉnh như vậy được gọi là một phủ đỉnh tối ưu. Như đã được chứng minh trong chương VIII, bài toán tìm một phủ đỉnh tối ưu là NP-khó vì bài toán quyết định liên quan với nó là NP- đầy đủ.
Tuy bài toán tìm một phủ đỉnh tối uu trong một đồ thị vô hưáng G = (V'', E) cho trước có thể là rất khó, việc tìm một phủ đỉnh gần tối ưu lại không là quá khó. Thuật toán xấp xỉ sau đây, có tên là Xapxi-Phudinh, với đầu vào là một đồ thị vô hướng G và trả về một phủ đỉnh có kích thước không vượt quá hai lần kích thước của một phủ đỉnh tối uii.
Để tìm một phủ đỉnh gần tối ưu, thuật toán Xapxi-Phudinh hoạt động như sau:
- Chọn một cạnh bất kì e = (u, v) thuộc E;
- Thêm vào phủ đỉnh gần tối ưu c (được khởi gán là tập rỗng) các đầu mút của e-, - Loại khỏi E tất cả các cạnh liên thuộc vứi e;
- Lặp lại những thao tác trên chừng nào trong E vẫn còn có cạnh để chọn.
Cụ thể ta có thuật toán Xapxi-Phudinh như sau:
Xapxi-Phudinh (G) 1 C ^ 0
2 E' <— E(G) // nhằm ẹii7 nguyên tập cạnh E của đồ thị G H 3 w h ile E' 0
4 do chọn (u,v) là một cạnh hất kì thuộc E ’ 5 C <- C u Ị u, vj
6 loại khỏi E' mọi cạnh liên thuộc với u hoặc V
1 r e t u r n c
276
Ta hãy phân tích và đánh giá độ phức tạp của thuật toán Xapxi-Phudinh. Biến c sẽ chứa phủ đỉnh gần tối ưu được xây dựng.
Dòng 1 khởi gán c là tập rỗng.
Dòng 2 gán cho E' một bản sao của tập cạnh E(G) của đồ thị đầu vào G.
Vòng lặp gồm các dòng 3, 4, 5, 6 lặp lại nhiều lần việc lấy đi một cạnh (u, v) khỏi E', thêm các đầu mút lí và V vào c và loại tất cả các cạnh thuộc E' được phủ bởi ư hoặc V.
Bằng cách sử dụng một cấu trúc dữ liệu thích hợp để biểu diễn tập cạnh F , cùng với sự phân tích ở trên, ta thấy thời gian chạy của thuật toán Xapxi-Phudinh chính bằng Od^l).
Ta có định lí sau:
ĐỊNH LÍ 9.1. Thuật toán Xapxi-Phudinh có cận thương bằng 2.
Chứng minh
Tập đỉnh c được thuật toán Xapxi-Phudinh trả về rõ ràng là một phủ đỉnh vì thuật toán thực hiện các vòng lặp cho tới khi mọi cạnh trong E{G) đều được phủ bởi một đỉnh nào đó thuộc c .
Gọi R là tập cạnh được chọn ở dòng 4 bơi thuật toán Xapxi-Phudinh. Theo cách thức hoạt động của Xapxi-Phudinh, không có hai cạnh nào trong R có đỉnh chung, vì nnỗi khi một cạnh được chọn ở dòng 4, tất cả những cạnh liên thuộc với các đầu mút của cạnh đó đều bị loại khỏi E' như được chỉ rõ ở dòng 6. Do đó, mỗi lần thực hiện dòng 5 lại thêm vào c hai đỉnh mới. Suy ra |C| = 2 |/?|. Tuy nhiên để phủ các cạnh trong R, mọi phủ đỉnh và nói riêng một phủ đỉnh tối ưu, phải chứa ít nhất một đầu mút của mỗi cạnh trong R. Vì không có hai cạnh nào trong R có chung một đầu mút, không có đỉnh nào trong phủ liên thuộc với quá một cạnh trong R. Từ đó, |/?ị < |C‘| và |C| < 2|C‘|. Định lí được chứng minh.
Sau đây là một ví dụ nhằm minh hoạ sự hoạt động của thuật toán Xapxi-Phudinh, tìm một phủ đỉnh gần tối ưu trên đồ thị G = (V, E) được cho như sau (h.9.1).
íb) (c)
H ình 9.1. H oạt động của thuật toán Xapxi-Phuđinh
(a) Đồ thị đầu vào G có 5 đỉnh, 6 cạnh.
(b) Cạnh (a, b), nét đậm, là cạnh đầu tiên được chọn bởi thuật toán Xapxi-Phudinh.
Các đỉnh a và b được thêm vào tập c, được khởi gán là tập rỗng. Cạnh (a, b) được thêm vào R, là tập các cạnh được chọn bởi thuật toán Xapxi-Phudinh (dòng 4 của thuật toán). Các cạnh (a, đ), (b,c), {b, e), đường nét đứt, được loại đi vì hiện giờ chúng được phủ bởi một đỉnh nào đó thuộc c.
(c) Cạnh (c, d) được thêm vào R, tập các cạnh được chọn bởi thuật toán Xapxi- Phudinh. Hai đỉnh c và í/ được thêm vào c. Cạnh (d, e) được loại đi khỏi E(G).
Phủ đỉnh trả về bởi Xapxi-Phudinh là lập c = { a, b, c, d }.
Phủ đỉnh tối ưu chỉ gồm hai đỉnh bvà d.
4. BÀI TO Á N NGƯỜI BÁN HÀNG RONG (CÒN GỌI LÀ BÀI TO ÁN NGƯỜI ĐI DU LỊCH- THE TR AVELING -SALESM AN PR OBLEM )
Bài toán người bán hàng rong có thể được phát biểu như sau: Cho trước một đồ thị vô hướng đầy đủ G - (\^, E), trong đó mỗi cạnh (h,v) e e c ó liên kết với một chi phí c { i i , v ) , là một số nguyên không âm. Cần tìm một chu trình Hamilton (một tua) của G với chi phi cực tiểu.
Để tiện lập luận, ta mở rộng phép kí hiệu và kí hiệu c(A) là chi phí tổng cộng của các cạnh thuộc tập con A ^ E . Như vậy
c(A) = e /1c(u,v).
Trong nhiều tình huống thực tế, khi phải di chuyển qua nhiều điểm khác nhau, việc đi thẳng từ một vị trí u tới một vị trí w bao giờ củng là rẻ nhất. Còn như chọn cách đi qua mộl điểm trung gian V thì không thể ít tốn kém hơn. Ta hình thức hoá khái niệm đó, bằng cách nói rằng hàm chi phí c thoả mãn bất đẳng thức tam giác nếu với mọi đỉnh u, V, w e V, ta có
c(u,w) < c(i4,v) + c(v,vv).
Bất đẳng thức tam giác có ý nghĩa khá tự nhiên, và trong nhiều ứng dụng thực tiễn, bấi đẳng thức tam giác được thoả mãn một cách tự động. Chẳng hạn, nếu các đỉnh của đổ thị là các điểm trên mặt phẳng và chi phí của việc di chuyển giữa hai điểm là khoảng cách ơclii thông thường giữa chúng thì đương nhiên bất đẳng thức tam giác được thoả mãn.
Có thể chứng minh rằng (hãy xem như một bài tập) việc buộc hàm chi phí phải thoả mãn bất đẳng thức tam giác không làm thay đổi tính NP-đầy đủ của bài toán người bán hàng rong. Và như vậy, dường như không có khả năng tìm được một thuật toán thời gian đa thức đế giải chính xác bài toán này. Thay vào đó, ta cần tìm những thuật toán xấp xỉ tốt.
4.1. BÀI TOÁN NGƯỜI BÁN HÀNG RONG VỚI BẤT ĐẲNG t h ứ c t a m g iá c
Trong mục nhỏ này, chúng ta sẽ xem xét một thuật toán xấp xỉ giải bài toán người bán hàng rong, với hàm chi phí thoả bất đẳng thức tam giác và có cận thương bằng 2. Thuật toán này tính một tua (tức một chu trình Hamilton) gần tối ưu của đồ thị G, sử dụng thuật toán Prim tính cây bao trùm cực tiểu. Chúng ta sẽ thấy rằng, khi hàm chi phí thoả mãn bất đẳng thức tam giác, thì tua mà thuật toán xấp xỉ trả về có chi phí không vượt quá hai lần so với chi phí của một tua tối uu.
Thuật toán xấp xỉ mà ta sẽ xây dựng để tìm một tua gần tối ưu trên một đồ thị đầy đủ G = (V, E) cho trước dựa trên ý tưởng sau:
278
- Chọn trên đồ thị G một đỉnh bất kì r làm đỉnh gốc;
- Xuất phát từ đỉnh gốc r, xây dựng một cây bao trùm nhỏ nhất T trên đồ thị G bằng thuật toán Prim;
- Xuất phát từ gốc r, thăm các đỉnh của T theo một thứ tự trước (có nghĩa theo thứ tự: thăm gốc, thâm cây con trái, thăm cây con phải) rồi trở về đỉnh gốc r;
- Tua xác định ở trên chính là tua gần tối ưu tìm được.
Cụ thể, ta có thuật toán Xapxi-nguoidulich-tua như sau:
Xapxi-nguoidulich-tua (G, c)
1 Chọn một đỉnh r thuộc V{G) làm đỉnh gốc;
2 Xây dựng một cây bao trùm nhỏ nhất T trên G, sử dụng thuật toán Prim;
3 Gọi L là danh sách các đỉnh được thăm theo một thứ tự trước trên T; 4 Trả về chu trình Hamilton H thăm các đỉnh theo thứ tự của L.
Vì đầu vào của thuật toán Xapxi-nguoidulich-tua là một đồ thị đầy đủ, theo nghĩa giữa hai đỉnh bất kì của đồ thị đểu có một cạnh nối chúng với nhau, nên thời gian chạy của Xapxi- nguoidulich-tua là 0(1E|) = 0 (|v f).
Bây giờ, chúng ta sẽ chứng minh định lí 9.2, khẳng định rằng nếu hàm chi phí đối với một trường hợp của bài toán người du lịch thoả mãn bất đẳng thức tam giác thì thuật toán Xapxi-nguoidulich-tua trả về một tua có chi phí không vượt quá hai lần chi phí của một tua tối ưu.
ĐỊNH LÍ 9.2. Xapxi-nguoidulich-tua là một thuật toán xấp xỉ có cận thương bằng 2 đối với bài toán người du lịch trong trường hợp hàm chi phí thoả mãn bất đẳng thức tam giác.
Chứng minh. Với tập đỉnh V cho trước của đồ thị G, gọi //* là một tua tối ưu và / / là lua được trả về bởi thuật loán Xapxi-nguoidulich-tua. Khi đó, việc chứng minh định lí 9.2 tương đương với việc phải chứng minh c{H) < lc { tí). Dễ thấy là, xuất phát từ một chu trình Hamilton bất kì, nếu ta loại đi một cạnh khỏi chu trình đó, ta sẽ có được một cây bao trùm (đương nhiên không nhất thiết là nhỏ nhất!). Vì vậy, nếu T là một cây bao trùm nhỏ nhất trên đồ thị G thì
cỢ) < citT). (9.4)
Cho T là một cây. Một hành trình duyệt thăm dầy đủ (a full walk) của T liệt kê các đỉnh khi chúng được thăm lần đầu cũng như được quay trở lại sau lần viếng thăm một cây con.
Ta gọi hành trình đó là w . Trong ví dụ của chúng ta (H. 9.2), hành trình duyệt thăm đầy đủ cho thứ tự các đỉnh như sau: a, b, c, b, h, b, a, d, e,f, e, g, e, d, a.
Vì hành trình duyệt thăm đầy đủ đi qua mồi cạnh của T đúng hai lần, ta có
c{W) = 2 cỢ) (9.5)
Từ (9.4) và (9.5), suy ra c(W) < 2 c{H*) (9.6)
Như vậy, chi phí của w không vượt quá hai lần chi phí của một tua tối ưu.
Dễ thấy, nói chung wkhông phải là một tua vì nó thâm một số đỉnh hơn một lần. Tuy nhiên, theo'bất đẳng thức tam giác, ta có thể loại bỏ sự viếng thăm một đỉnh bấl kì khỏi wmà không làm chi phí tăng lên. Thực vậy, nếu một đỉnh V được loại khỏi w, giữa các lần viếng thăm u và w, kết quả sẽ là thứ tự dịch chuyển trực tiếp từ u tới w. Bằng cách áp dụng liên tiếp thao tác đó, ta có thể lấy đi khỏi w tất cả các đỉnh trừ ra các đỉnh được viếng thãm lần đầu tiên.Trong ví dụ của ta ở hình 9.2 cho kết quả là thứ tự sau:
ơ , b , c j i , d , e , f , g .
Thứ tự đó chính là thứ tự có được của việc duyệt theo thứ tự trước của cây T. Gọi H là chu trình ứng với việc duyệt theo thứ tự trước đó. Đó là một chu trình Hamilton vì mỗi đỉnh được thăm đúng một lần, và thực sự đó chính là chu trình được tính bởi thuật toán Xapxi- nguoidulich-tua. Vì Hcó được từ việc loại một số đỉnh khỏi hành trình duyệt thăm đầy đủ w,
ta có c{H) < c(W).
Kết hợp với bất đẳng thức cịW) < 2c(H*) ở trên, ta có cựỉ) < 2 c{tT).
Định lí 9.2 được chứng minh.
Tuy định !í 9.2 cho một cận thương khá đẹp, nhưng thuật toán Xapxi-nguoidulich-tua thưcmg không phải là sự lựa chọn tốt nhất cho bài toán người du lịch. Trong thực hành, còn có những thuật toán xấp xỉ tốt hơn nhiều, như được chỉ rõ trong các tài liệu tham khảo được dẫn ở cuối chương.
Sau đây là một ví dụ minh hoạ sự hoạt động của thuật toán Xapxi-nguoidulich-tua trên đồ thị đầy đủ G được cho trên hình 9.2 [4J.
é
(i> € )
(a)
Hình 9.2
280
a) Các đỉnh của đồ thị đầy đủ G = (V', E), nằm trên một lưới ô vuông.
b) Một cây bao trùm T gốc a, được xác định theo thuật toán Prim.
c) Một hành trình duyệt thăm đầy đủ cây T theo thứ tự ơ, b, c, b, h, h, a, d, e,f, e, g, e, d, a tương ứng với thứ tự trước a, h, c, h, d, e,f, g.
d) Tua H được trả về bởi thuật toán Xapxi-nguoidulich-tua, có tổng chi phí xấp xỉ 19.074.
e) Tua tối uu H* với chi phí xấp xỉ 14.715.
4.2. BÀI TOÁN NGƯỜI DU LỊCH TổNG QUÁT
Bây giờ ta chuyển sang nghiên cứu bài toán người du lịch trong đó hàm chi phí không thoả mãn bất đẳng thức tam giác. Ta sẽ chứng minh rằng trong trường hợp này không thể tìm được những tua xấp xỉ tốt trong thời gian đa thức nếu như không có p = NP.
Ta có định lí sau:
ĐỊNH LÍ 9.3. Nếu p NP và p > 1 thì không tồn tại một thuật toán xấp xỉ thời gian đa thức với cận thương p cho bài toán người du lịch tổng quát.
Chứng minh. Ta chứng minh bằng phản chứng. Giả sử ngược lại, với một p > 1 nào đó, có một thuật toán xấp xỉ thời gian đa thức A với cận thương là p. Không giảm tổng quát, giả sử p là một số nguyên, vì trong trường hợp cần thiêì, ta có thể làm tròn nó. Bây giờ ta sẽ chỉ ra rằng có thể dùng thuật toán A như thế nào để giải các trường hợp của bài toán chu trình Hamilton trong thời gian đa thức. Và nếu đúng như vậy, vì đã biết bài toán chu trình Hamilton (nhắc lại là bài toán: Cho trước một đồ thị G = (\", E). Quyết định xem G có chu trình Hamilton hay không?) là NP-đầy đủ, nên nếu giải được nó trong thời gian đa thức thì sẽ suy ra P = NP.
Cho G = 0 ', E) là inộl Irường hợp của bài toán chu trình Hamilton. Trên cơ sở sử dụng thuật toán xấp xỉ A, được giả định là có tồn tại, ta muốn xác định một cách hiệu quả rằng G có chứa inộl chu trình Hamilton hay không.Ta chuyển G thành một trường hợp của bài toán người du lịch như sau. Gọi G' = E') là đồ thị đầy đủ trên V, có nghĩa:
E' = { (//, v): //, V e V vh. u
Gán cho mỗi cạnh thuộc £" một chi phí nguyên như sau;
1 nếu (//, v) e E,
c { i i , V') = <
p| V^l + 1 trường hợp ngược lại.
Các biểu diễn của G' và của c có thể được tạo ra từ một biểu diễn của G trong thời gian đa thức iheo \ ' và E .
Bây giờ, ta hãy xét bài toán người du lịch ứng với (ơ , c). Nếu đồ thị ban đầu G có một chu trình Hamilton H, thì hàm chi phí c gán cho mỗi cạnh của H một chi phí bằng 1, và như vậy, (ơ', c) chứa một tua có chi phí bằng I vi . Ngược lại, nếu G không chứa một chu trình
Hamilton, thì mọi tua của G' phải chứa ít nhất một cạnh không thuộc E và tua đó phải có chi phí ít nhất là
(p| l/| + 1) + (I vi - 1) > pl vi .
Vì các cạnh không thuộc G có chi phí cao như vậy, có một khoảng cách lớn giữa chi phí của một tua là một chu trình Hamilton trong G (có chi phí là I K| ) với chi phí của một tua bất kì khác (có chi phí lớn hơn pl vi ).
Vậy điều gì sẽ xảy ra nếu ta áp dụng thuật toán xấp xỉ A cho bài toán người du lịch ứng với (G\ c)? Vì A được đảm bảo sẽ trả về một tua có chi phí không vượt quá p lần chi phí của một tua tối ưu, nên nếu G chứa một chu trình Hamilton thì A phải trả về chu trình đó. Còn nếu G không có chu trình Hamilton, thì A trả về một tua với chi phí lófn hơn p . Do đó, ta có thể dùng A để giải bài toán chu trình Hamilton trong thời gian đa thức. Điều này chỉ có thể xảy ra nếu P = NP.
5. BÀI TO ÁN PHỦ TẬP
Một trường hợp (X F) của bài toán phủ tập bao gồni một tập hữu hạn X và một họ F cắc tập con của X, sao cho mọi phần tử của X thuộc ít nhất một tập con trong F:
Với một tập con S e F, ta nói s phủ các phần tử của nó. Bài toán là tìm một tập con c
của F có kích thước cực tiểu c sao cho các phần tử của c phủ tất cả X:
X = u , e c - 5 . ( 9 . 7 )
Một họ con C bất kì của F thoả phương trình (9.7) được nói là phủ X. Hình 9.3 sau đày minh hoạ cho bài toán phủ tập, trong đó X gồm 13 hình tròn, F gồm các tập 5|, S2, ....
Hình 9.3, Một ví dụ của bài toán phủ tập
282 36CTDI PTPMFMB
Bài toán phủ tập rõ ràng là một bài toán tối ưu và mô hình hoá nhiều bài toán chọn lựa tài nguyên. Nó tổng quát hoá bài toán phủ đỉnh là một bài toán NP-đầy đủ. Do đó bài toán phủ tập cũng là NP-khó. Tuy nhiên, thuật toán xấp xỉ được trình bày ở mục 3 để giải bài toán phủ đỉnh không áp dụng được ở đây và chúng ta cần có những cách tiếp cận khác. Đối với bài toán phủ tập ở đây, chúng ta sẽ đề xuất một heuristic "háu ăn" với một cận thương lôgarit.
Một thuật toán xấp xỉ háu ăn
Phương pháp "háu ăn" làm việc như sau: tại mỗi bước, nó lấy ra một tập s phủ nhiều nhất các phần tử chưa được phủ. Theo cách đó, ta có được thuật toán háu ăn như sau.
Phu-dinh-haư-an{X, F) 1 V
1 C < r-0 3 w h i l e U ^ 0
4 do chọn một phần ứ s e F làm cực đại s n ơ 5 ư < r - ư - s
6 C < - C u { 5 } 7 r e t u r n c
Giải thích một cách chi tiết, thuật toán Phu-dinh-hau-an hoạt động như sau:
Tại mỗi bước, tập u chứa tập những phần tử chưa được phủ. Tập c chứa phủ đang được xây dựng. Dòng 4 là bước quyết định theo cách háu ăn. Tập được chọn là tập con s phủ được nhiều nhất có thể những phần tử chưa được phủ. Sau khi s được chọn, các phần tử của nó được lấy đi khỏi ơ, còn s thì được đưa vào c. Khi thuật toán kết thúc, c chứa một họ con của F mà lìỌ con này phủ X.
Thuật toán Phu-dinh-hau-an có thể được cài đặt dễ dàng để chạy trong thời gian đa thức theo I v à I F I. Thực vậy, vì số lần lặp của vòng lặp gồm các dòng 3, 4, 5, 6 nhiều nhất bằng min( AI, F ), trong khi Ihân của vòng lặp có thể được cài đặt để chạy trong thời gian 0(1 a1 I F I ). Từ đó suy ra có một cài đặt chạy trong thời gian 0(1 a1 I f I min(| .xị, I f I )).
Để chứng tỏ thuật toán Phu-dinh-hau-an là một thuật toán xấp xỉ có ý nghĩa trong thực hành, ta cần chứng minh rằng nó trả về một phủ tập không lớn hơn quá nhiều một phủ tập
í / Ị
tối ưu. Sau đây, để thuận tiện cho lập luận, ta sẽ kí hiệu số điều hoà HI - là H{d).
/=I i ĐỊNH LÍ 9.4. Thuật toán xấp xỉ Phu-dinh-hau-an có cận thương bằng
H(max { I s | : S e F}).
Chứng minh. Chứng minh được tiến hành bằng việc gán một chi phí cho mỗi tập được chọn bởi thuật toán, phân bố chi phí đó trên các phần tử được phủ lần đầu tiên và sau đó dùng những chi phí này để suy ra mối quan hệ mong muốn giữa kích thước của một phủ tập tối ưu