Tài liệu Tổng luận về lớp bài toán thiết kế mạng

ĐẠI HỌC QUỐC GIA HÀ NỘI KHOA CÔNG NGHỆ Võ Việt Hùng TỔNG LUẬN VỀ LỚP BÀI TOÁN THIẾT KẾ MẠNG LUẬN VĂN THẠC SĨ Hà Nội — 2003 ĐẠI HỌC QUỐC GIA HÀ NỘI KHOA CÔNG NGHỆ Võ Việt Hùng TỔNG LUẬN VỀ LỚP BÀI TOÁN THIẾT KẾ MẠNG Chuyên ngành: Công nghệ thông tin Mã số: 1.01.10 LUẬN VĂN THẠC SĨ Người hướng dẫn khoa học: GS TSKH Phan Đình Diệu Hà Nội - 2003 Mục lục Danh mục các chữ viết tắt ..........................................................................1 Lời giới thiệu..............................................................................................2 Chương 1. Mở đầu .....................................................................................5 1.1. Một số khái niệm và ký hiệu trong lý thuyết đồ thị...................5 1.2. Một số hàm trên đồ thị .............................................................7 1.3. Các định lý đối ngẫu trong lý thuyết QHTT .............................9 1.4. Mô hình lát cắt - Bài toán thiết kế mạng .................................10 Phần 1. Thuật toán dựa trên QHTT .....................................................13 Chương 2. Phương pháp gốc-đối ngẫu .....................................................14 2.1. Lý luận chung ........................................................................14 2.2. Thuật toán Goemans-Williamson ...........................................17 2.3. Thuật toán 2 f max -xấp xỉ cho bài toán SND .............................22 2.4. Thuật toán 2 H f max -xấp xỉ cho bài toán SND .......................27 Chương 3. Kỹ thuật làm tròn liên tiếp ......................................................31 3.1. Lý luận chung ........................................................................31 3.2. Bài toán SND trên đa đồ thị vô hướng ....................................32 3.3. Bài toán thiết kế mạng trên đồ thị có hướng ...........................38 Phần 2. Thuật toán đồ thị ......................................................................43 Chương 4. Các bài toán 2-liên thông........................................................44 4.1. Lý luận chung ........................................................................44 4.2. Bài toán 2-EC .........................................................................45 4.3. Bài toán 2-VC ........................................................................46 Chương 5. Các bài toán k-EC ..................................................................52 5.1. Bài toán k-EC trên đồ thị đơn giản .........................................52 5.2. Bài toán k-EC trên đa đồ thị ...................................................62 5.3. Phân tích Gabow ....................................................................69 Chương 6. Các bài toán k-VC ..................................................................75 6.1. Đồ thị vô hướng .....................................................................76 6.2. Đồ thị có hướng .....................................................................81 Chương 7. Một số đánh giá và phương hướng nghiên cứu .......................83 Tài liệu tham khảo ....................................................................................86 1 Danh mục các chữ viết tắt QHTT: quy hoạch tuyến tính QHN: quy hoạch nguyên (trong luận văn này, khi nhắc đến QHN ta ngầm hiểu là quy hoạch tuyến tính nguyên) MC: minimum cardinality MW: minimum weight đpcm: điều phải chứng minh NVLV: người viết luận văn 2 Lời giới thiệu. Nhu cầu thực tế của bài toán thiết kế mạng. Các bài toán thiết kế mạng có nhiều ứng dụng trên thực tế, chúng thường xuất hiện trong các vấn đề liên quan đến xây dựng hệ thống giao thông và hay gặp khi cần thiết kế mạng truyền thông. Các hệ thống cần xây dựng này đều đòi hỏi phải đảm bảo hệ thống vẫn vận hành tốt bất chấp xảy ra hỏng hóc ở một số điều kiện nhất định. Mục tiêu của bài toán thiết kế mạng là tìm ra mạng có chi phí nhỏ nhất mà có tính tin cậy như vậy. Giả sử, ta coi mạng truyền thông là một đồ thị G với tập cạnh E là tất cả các liên kết có thể có của mạng. Ký hiệu cạnh e ab là đường truyền có thể lập giữa trạm a và trạm b, c e là chi phí để lập đường truyền đó. Khi đó, mạng cho phép các trạm kết nối được với nhau rẻ nhất chính là cây khung nhỏ nhất của đồ thị G. Tuy nhiên mạng truyền thông như vậy quá nhạy cảm với các sự cố, bởi nó có thể bị tê liệt do hỏng thậm chí chỉ một đường kết nối hoặc một trạm làm việc. Để mạng truyền thông tin cậy hơn người ta cần dựa trên những đồ thị liên thông cao hơn. Một mạng gọi là k liên thông cạnh (hoặc đỉnh) nếu mạng cho phép các trạm vẫn liên lạc được với nhau ngay cả khi có tới k-1 đường kết nối (hoặc trạm) bị hỏng. Nhu cầu lập mạng rẻ và chịu lỗi dẫn đến đòi hỏi giải quyết bài toán tìm đồ thị bộ phận k-liên thông có giá nhỏ nhất. Giải xấp xỉ các bài toán thiết kế mạng. Ta biết rằng việc tìm phương án tối ưu trong các bài toán tối ưu hoá NP-khó là “khó” như nhau. Về mặt lý thuyết, điều này giúp người thiết kế thuật toán tránh được những công sức vô ích khi cố gắng giải bài toán NP-khó, tuy nhiên trên thực tế, những bài toán tối ưu hoá mà ta hay gặp và cần giải lại hầu hết là những bài toán NP-khó. Để “đối phó” với các bài toán NP-khó này, ta cần một thái độ thực tế hơn, đó là chấp nhận hy sinh điều kiện tìm phương án tối ưu nhưng thay vào đó là tìm ra “nhanh” (trong thời gian đa thức) phương án “gần” tối ưu. Đây là vấn đề thiết kế thuật toán xấp xỉ, một trọng tâm nghiên cứu của lý thuyết thuật toán xấp xỉ. 3 Lớp bài toán thiết kế mạng có vai trò trung tâm trong lý thuyết tối ưu hoá tổ hợp, nó bao gồm nhiều bài toán tổ hợp cơ bản, như bài toán cây Steiner, bài toán Survivable Network Design, … và phần lớn các bài toán này là NP-khó ngay cả khi ta chỉ xét chúng ở những dạng hết sức đơn giản. Thời gian gần đây, mảng thiết kế thuật toán xấp xỉ cho các bài toán thiết kế mạng trở nên sôi nổi với sự xuất hiện của nhiều kết quả nghiên cứu đáng chú ý. Những kết quả này khá đa dạng, từ những phương pháp có tính tổng quát trên toàn bộ lĩnh vực thiết kế thuật toán xấp xỉ như phương pháp gốc-đối ngẫu, kỹ thuật làm tròn liên tiếp đến những kỹ thuật dựa trên lý thuyết đồ thị, mang đặc thù riêng của lớp bài toán như DFS-cây, họ vân hay lý thuyết cặp ghép. Do tính thực tiễn cao và sự phong phú về lý luận của lớp bài toán, người viết luận văn (NVLV) lựa chọn đề tài nghiên cứu về thiết kế thuật toán xấp xỉ trong lớp bài toán thiết kế mạng cho đợt bảo vệ lần này. Đóng góp của luận văn. Các kết quả nghiên cứu về lớp bài toán thiết kế mạng của NVLV được trình bày trong luận văn bao gồm: - NVLV cố gắng cung cấp một cách nhìn có hệ thống về các hướng tiếp cận gần đây đối với lớp bài toán thiết kế mạng, đồng thời đưa ra một số phân tích và đề xuất một số hướng nghiên cứu trong lớp bài toán này. - NVLV trình bày một số kỹ thuật, kết quả nổi bật hoặc mới nhất (làm tròn liên tiếp, DFS, ứng dụng định lý Mader và lý thuyết cặp ghép) trong các bài toán SND, k-EC, k-VC và 2-liên thông. - NVLV chỉ ra một ví dụ cho thấy không thể áp dụng lập luận đếm để chứng minh mọi phương án cực biên tối ưu đều có thành phần 1 trong bài toán SND trên đồ 2 thị có hướng. - NVLV đưa ra một lược đồ phân bố chặt chẽ hơn và do đó có chứng minh tường minh hơn bất đẳng thức Cheriyan-Thrimella (trong khẳng định 3) của bài toán kEC. 4 Bố cục của luận văn. Luận văn bao gồm hai phần “Thuật toán dựa trên QHTT” và “Thuật toán đồ thị” tương ứng với hai hướng tiếp cận chủ yếu của các thuật toán xấp xỉ trong lớp bài toán thiết kế mạng. Trước khi bắt đầu phần 1, trong chương 1, NVLV điểm lại một số khái niệm, định lý cơ sở và ký hiệu trong lý thuyết đồ thị và QHTT mà sẽ được sử dụng ở các chương sau; Phần 1 gồm hai chương: chương 2 trình bày và phân tích một số vấn đề khi áp dụng phương pháp gốc-đối ngẫu vào giải bài toán SND. Nội dung chương 3 là kỹ thuật làm tròn liên tiếp. Trong chương này, NVLV cũng đưa ra ví dụ cho thấy không thể áp dụng lập luận đếm để chứng minh mọi phương án cực biên tối ưu đều có thành phần 1 trong bài toán SND trên đồ thị có hướng. Phần 2 2 của luận văn bao gồm ba chương về các thuật toán xấp xỉ thuần tuý dựa trên đồ thị. Chương 4 trình bày một số kỹ thuật đồ thị được áp dụng để giải xấp xỉ các bài toán 2-liên thông. Chương 5 thảo luận về bài toán k-EC, NVLV cũng đưa ra chứng minh bất đẳng thức Cheriyan-Thrimella của mình trong chương này. Chương 6 là ứng dụng của định lý Mader và lý thuyết cặp ghép trong giải xấp xỉ bài toán k-VC. Cuối cùng, chương 7 là một số đánh giá và phương hướng nghiên cứu có thể phát triển trên cơ sở tổng hợp các chương 2, 3, 4, 5, 6. 5 Chương 1: Mở đầu. 1.1. Một số khái niệm và ký hiệu trong lý thuyết đồ thị. Trong các khái niệm và ký hiệu dưới đây, nếu không có những chỉ dẫn khác đi ta ngầm định là đang bàn trên đa đồ thị vô hướng G V,E . - uv là cạnh nối đỉnh u với đỉnh v , cũng dùng ký hiệu uv để chỉ một cung đi từ u đến v trong đồ thị có hướng. M E , deg M v là số cạnh của M kề với v . deg E v là bậc của v trong đồ thị. Ký hiệu E v là tập các cạnh kề với v , deg v N v là tập các đỉnh kề với v . - Đường đi u v là đường đi có 2 đỉnh mút là u, v . Gọi 2 đường đi là rời đỉnh nếu các đỉnh chung chỉ là các đỉnh mút. Tập k đôi một rời đỉnh. Cho A, B V P - S A V, lẫn gọi v0 và V P G S uv u S, v 2 đường đi gọi là rời đỉnh nếu chúng V , đường đi P v0 v1...vk gọi là đường đi A B nếu vk , với V P B v0 , v1 ,..., vk . S là tập các cạnh của lát cắt S, S , nếu không nhầm S là lát cắt và gọi là k-cắt nếu lát cắt có đúng k cạnh. Cạnh e gọi là rời khỏi S nếu e S . Với x Q E , ký hiệu x S xe . e - Xét đồ thị có hướng G V,E ,M E, S V , ký hiệu deg M ,out v là số cung của M đi từ v ; deg M ,in v là số cung của M đi đến v , S đến S , in (S ) out S là tập các cung đi từ S là tập các cung đi từ S đến S . - Giả sử G là đồ thị vô hướng. Ký hiệu L G là đồ thị tuyến (line graph) của đồ thị G , xây dựng đồ thị này như sau: L G nhận E làm tập đỉnh; với e, f E , ef là cạnh của L G khi và chỉ khi e, f là 2 cạnh kề nhau trong G (2 cạnh có chung một đỉnh mút). Giả sử G có hàm trọng số w . trên tập các cạnh, ký hiệu G D là đồ thị có hướng lập ra từ G bằng cách thay mỗi cạnh e uv bởi 2 cung uv và vu có 6 trọng số w e . - Đồ thị vô hướng G V , E gọi là k-EC nếu V k 1 và nếu xóa khỏi G ít hơn k cạnh bất kỳ thì đồ thị còn lại luôn liên thông. Tương tự, gọi G nếu V V , E là k-VC k 1 và nếu xóa khỏi G ít hơn k đỉnh bất kỳ thì đồ thị còn lại luôn liên thông. - Đồ thị có hướng gọi là liên thông mạnh nếu với mọi cặp đỉnh có thứ tự u, v đều có đường đi có hướng từ u đến v . Đồ thị có hướng G V V , E gọi là k-EC nếu k 1 và nếu xóa đi ít hơn k cung bất kỳ thì đồ thị còn lại luôn liên thông mạnh. Định nghĩa tương tự cho k-VC. - Cạnh uv của đồ thị k-EC (k-VC) G gọi là tới hạn với tính chất k-EC (k-VC) nếu G \ uv không là k-EC (k-VC). Định nghĩa tương tự cho đồ thị có hướng. - Giả sử u ,v là 2 đỉnh khác nhau, ký hiệu u ,v là số cạnh nhỏ nhất có thể xoá đi để u không liên thông với v , ta cũng nói u ,v là k-EC với nhau nếu Như vậy, trong đồ thị k-EC, u,v k u v u,v k. V . - Tập cạnh M gọi là phủ đỉnh v nếu v kề với ít nhất 1 cạnh của M , ngược lại gọi là không phủ. Tập cạnh M gọi là tập bao quát nếu M phủ mọi đỉnh v của đồ thị. Tức là, deg M v 1, v V . - Tập cạnh M gọi là một cặp ghép của G nếu không có hai cạnh nào của M có chung đầu mút. Tức là, deg M v toàn nếu deg M v 1, v V . Cặp ghép M gọi là cặp ghép hoàn 1, v V . Đồ thị G gọi là factor-critical nếu v V , G \ v có một cặp ghép hoàn toàn. Ký hiệu số hụt của đồ thị là def G , xác định như sau def G - A, B n 2 max M , M là cặp ghép của G . V gọi là xuyên qua nhau nếu cả A \ B, B \ A, A B đều khác rỗng. Như vậy nếu A, B không xuyên qua nhau thì hoặc A, B rời nhau hoặc một tập chứa hoàn toàn tập còn lại. Ta nói một họ L gồm các tập con của V tạo thành một họ vân nếu 7 không có 2 tập nào trong họ xuyên qua nhau. Họ vân L gọi là phủ tập cạnh F nếu F  A . A L 1.2. Một số hàm trên đồ thị. Các hàm trên đồ thị được định nghĩa sau đây có thể dùng để tổng quát hoá nhiều bài toán thực tế, mặt khác một số thuật toán xấp xỉ cho bài toán thiết kế mạng về bản chất là có thể áp dụng cho hàm. Bởi vậy, ngoài định nghĩa các hàm, ta sẽ nêu và chứng minh một số tính chất quan trọng của chúng. Hàm proper. Hàm f : 2V 0 được gọi là proper nếu nó có các tính Z , f V chất đối xứng và tối đại sau đây. - Tính đối xứng : f S - Tính tối đại: f A f V \S , S B V max f A , f B , A , B V ,A B Trong trường hợp hàm f proper chỉ lấy giá trị trong tập 0,1 , ta nói f là hàm proper 0,1 . Hàm submodular. Hàm f : 2V - f (S ) -f A f (V \ S ) , S f B Z ,f V 0 được gọi là submodular nếu: V max f A B f A B ,f A \ B Hàm intersecting supermodular. Hàm f : 2v f B \ A , A, B Z , f V V 0 được gọi là intersecting supermodular nếu: - f A f B f A B f A B , A, B Hàm crossing supermodular. Hàm f : 2v V mà A Z , f V B 0 được gọi là crossing supermodular nếu: - f A f B f A B f A B , Hàm supermodular yếu. Hàm f : 2v A, B V mà A Z , f V B ,A B V 0 được gọi là supermodular 8 yếu nếu: - f (S ) f (V \ S ) , S -f A f B V max f A B f A Hàm uncrossable. Hàm h : 2V - h(S ) h(V \ S ), S - h( A) h( B) 1 thì hoặc h( A B ,f A \ B f B \ A , A, B V 0 được gọi là uncrossable nếu 0,1 , h V V B) B) 1 hoặc h( A \ B) h( A h( B \ A) 1 Một số tính chất cơ bản của các hàm. Tính chất 1: Mọi hàm proper đều là hàm supermodular yếu. Chứng minh: Giả sử f : 2v Z f A f A A f B B max f A B , dễ có đpcm. Giả sử A là hàm proper, ta sẽ chứng minh f thoả mãn B ,f A \ B B f B \ A , A, B V. Nếu , ta có: f A max f A B , f A\ B (1) f B max f A B , f B\ A (2) f A f A max f A B, f B\ A max f A B , f B\ A (3) f B f B max f A B , f A\ B max f A B , f A\ B (4) Giả sử f A B min f A B,f A B , f A \ B , f B \ A , cộng hai bất đẳng thức (1), (2) ta nhận được f A f B f A \ B f B \ A max f A Các trường hợp khác ta cũng lý luận tương tự. B f A B , f A\ B f B\ A  Tính chất 2: Cho tập cạnh F E trong đa đồ thị G V , E , thế thì hàm F . là submodular. Tính chất 3: Cho hàm supermodular yếu f và véctơ x Q E trên đồ thị vô hướng, 9 thế thì hàm f ( S ) x( ( S )) cũng là supermodular yếu. 1.3. Các định lý đối ngẫu trong lý thuyết QHTT. Cho đến nay một mảng lớn trong lý thuyết thuật toán xấp xỉ được xây dựng trên cơ sở lý thuyết quy hoạch tuyến tính (QHTT), mà kỹ thuật làm tròn liên tiếp và phương pháp gốc-đối ngẫu trong các chương 2, 3 là những minh chứng cụ thể. Bởi vậy, trước tiên ta sẽ điểm lại một số tính chất toán học cơ bản của lý thuyết QHTT mà những nghiên cứu về thuật toán xấp xỉ hay dùng. QHTT là các bài toán tối ưu một hàm mục tiêu tuyến tính trong khi phải thoả mãn một hệ các bất phương trình tuyến tính (các ràng buộc). Gọi nghiệm của hệ các ràng buộc là phương án chấp nhận được. Gọi z * là giá trị tối ưu của một QHTT (cực tiểu hoá), để nghiên cứu về cận dưới của z * người ta lập QHTT đối ngẫu với QHTT ban đầu (gọi là QHTT gốc). Cách xây dựng QHTT đối ngẫu đem lại nhiều tính chất thú vị: ví dụ, đối ngẫu của QHTT đối ngẫu là QHTT gốc. Giá trị của các phương án chấp nhận được của QHTT đối ngẫu là chặn dưới giá trị tối ưu của QHTT gốc, và ngược lại mọi giá trị của phương án chấp nhận được của QHTT gốc là chặn trên giá trị tối ưu của QHTT đối ngẫu. Bởi vậy, nếu ta tìm được các phương án chấp nhận được của cặp QHTT đối ngẫu có cùng giá trị hàm mục tiêu thì các phương án này là các phương án tối ưu. Xem chi tiết về cơ sở toán học của lý thuyết QHTT ở [Goe01] và ứng dụng trong lý thuyết thuật toán xấp xỉ ở [Vaz01]. Sau đây ta sẽ phát biểu các tính chất toán học này ở dạng hình thức. n QHTT cực tiểu hoá ở dạng chuẩn: min n aij x j c j x j thoả mãn j 1 bi , i 1,.., m j 1 xj 0, j 1,.., n m QHTT đối ngẫu là: max m i 1 bi yi thoả mãn aij yi c j , j 1,.., n i 1 yi 0, i 1,.., m Định lý 1 (định lý đối ngẫu): QHTT gốc có giá trị tối ưu hữu hạn khi và chỉ khi 10 QHTT đối ngẫu của nó cũng có giá trị tối ưu hữu hạn. Hơn nữa, nếu x* y1* ,..., ym* là các phương án tối ưu của các QHTT gốc, đối ngẫu tương ứng và y* n m c j x*j thì x1* ,..., xn* bi yi* . j 1 i 1 Định lý 2 (định lý đối ngẫu yếu): Nếu x x1 ,..., xn và y y1 ,..., ym là các phương án chấp nhận được của các QHTT gốc, đối ngẫu tương ứng thì n m bi yi . cjxj j 1 i 1 Định lý 3 (các điều kiện độ lệch bù): Nếu x và y là các phương án chấp nhận được của các QHTT gốc, đối ngẫu tương ứng thì x và y là các phương án tối ưu khi và chỉ khi chúng thoả mãn các điều kiện sau đây: - Điều kiện độ lệch bù gốc: với j 1, n hoặc x j 0 hoặc m aij yi cj . i 1 - Điều kiện độ lệch bù đối ngẫu: với i 1, m hoặc yi 0 hoặc n aij x j bi . j 1 Như ta sẽ thấy ở chương 2, các điều kiện độ lệch bù đóng vai trò hết sức quan trọng trong việc thiết kế thuật toán cũng như phân tích tỷ suất hiệu quả của các thuật toán xấp xỉ xây dựng theo phương pháp gốc-đối ngẫu. 1.4. Mô hình lát cắt – Bài toán thiết kế mạng. Định lý Menger: Cho đồ thị G V , E và A, B V . Thế thì số đỉnh nhỏ nhất tách A khỏi B bằng số đường đi A B rời đỉnh lớn nhất (trong định lý này, khái niệm rời đỉnh được hiểu với nghĩa nghiêm ngặt, tức là không chung đỉnh nào, kể cả đầu mút). (Xem [D00]). Hệ quả 1: Cho các đỉnh a b V. i. Nếu ab E thì số đỉnh khác a, b nhỏ nhất tách a khỏi b bằng số đường đi a b 11 rời đỉnh lớn nhất. ii. Số cạnh nhỏ nhất tách a khỏi b bằng số đường đi a b rời cạnh lớn nhất. Chứng minh: i. áp dụng định lý Menger với A N a ,B ii. áp dụng định lý Menger trên đồ thị tuyến L G với A Nb . E a ,B Eb . Hệ quả 2: i. Đồ thị là k-VC khi và chỉ khi giữa 2 đỉnh phân biệt bất kỳ có ít nhất k đường đi rời đỉnh. ii . Đồ thị là k-EC khi và chỉ khi giữa 2 đỉnh phân biệt bất kỳ có ít nhất k đường đi rời cạnh. Mô hình lát cắt Giả sử u, v là 2 đỉnh phân biệt của đồ thị G , từ u ,v cạnh tách u khỏi v ta lập được một lát cắt u v có kích thước không lớn hơn u ,v . Vì vậy, u ,v không nhỏ hơn kích thước mincut u v . Đồng thời số đường đi u v rời cạnh lớn nhất không thể vượt quá kích thước mincut u v . Theo định lý Menger, u ,v bằng số đường đi u v rời cạnh lớn nhất. Vì vậy, số đường đi u v rời cạnh lớn nhất cũng chính là kích thước mincut u v . Từ nhận xét này, đối với nhiều bài toán liên thông trong lớp bài toán thiết kế mạng, người ta quy các yêu cầu liên thông giữa các cặp đỉnh về ràng buộc kích thước tối thiểu của mỗi lát cắt. Mô hình hoá bài toán theo các lát cắt như vậy gọi là mô hình lát cắt (cut-covering). Ví dụ, trong bài toán k-EC, yêu cầu liên thông quy về S f S, S S V với f S k, S max ruv u V ; hay trong bài toán SND là S , v S , ruv là yêu cầu liên thông của cặp đỉnh u, v . Từ đây trở về sau, để chỉ f , tuỳ theo ngữ cảnh ta sẽ dùng thuật ngữ hàm yêu cầu cắt hoặc hàm yêu cầu liên thông. Phát biểu bài toán. Bài toán thiết kế mạng (Network Design Problem). Cho đồ thị G (V , E ) (có 12 hướng hoặc vô hướng, G là đa đồ thị hoặc đồ thị đơn giản) có hàm giá không âm Q , hàm yêu cầu cắt f : 2V c:E quy định số cạnh (cung) ít nhất mà lát Z cắt S, S cần chứa. Tìm đồ thị bộ phận GOPT của G có giá nhỏ nhất thoả hàm f , tức là EOPT S f S, S V. Trong các bài toán thiết kế mạng, ta nói tập cạnh H S f S, S H thoả f nếu: V . Tức là với mọi tập đỉnh S số cạnh của H rời khỏi S ít nhất là f S . Ta lập biến xe 0,1 cho mỗi cạnh e với ý nghĩa như sau, xe phận chứa e và xe 1 nếu đồ thị bộ 0 nếu ngược lại. Khi đó, QHN của bài toán thiết kế mạng (trong trường hợp đồ thị đơn giản không chứa cạnh lặp) theo mô hình lát cắt sẽ là: ce xe thoả mãn min e E x( ( S )) xe f ( S ), S 0,1 , e V E Trên thực tế ta hay gặp một trường hợp riêng của bài toán thiết kế mạng, ở đó yêu cầu liên thông được chỉ ra bằng hàm yêu cầu liên thông nguyên không âm r (.,.) như sau: với mỗi cặp đỉnh phân biệt u,v V phải có ít nhất r (u, v) đường đi u v rời cạnh. Bài toán này gọi là bài toán SND, phát biểu đầy đủ của bài toán như sau: Bài toán Survivable Network Design (SND): Cho (đa) đồ thị vô hướng G (V , E ) , hàm giá không âm c : E Q , hàm yêu cầu liên thông r : V V Tìm đồ thị bộ phận GOPT , mà giữa hai đỉnh phân biệt u,v r (u, v) đường đi u v rời cạnh, có giá min Z . V bất kỳ luôn có ít nhất ce xe nhỏ nhất. e EOPT Theo định lý Menger, ta có thể nghiên cứu bài toán SND trên mô hình lát cắt của bài toán thiết kế mạng với f (S ) max r u, v u S , v S , tức là f S là yêu cầu cắt lớn nhất mà lát cắt S, S cần thoả. 13 14 Chương 2: Phương pháp gốc-đối ngẫu. 2.1. Lý luận chung. Sự phát triển của ngành tối ưu hoá tổ hợp trong thời gian qua chịu ảnh hưởng lớn của lý thuyết QHTT. Nhiều ý tưởng, công cụ trong tối ưu hoá tổ hợp bắt nguồn từ những tính chất toán học được biết trong QHTT. Phương pháp gốc-đối ngẫu là một trong những công cụ như vậy. Dantzig, Ford, Fullkerson là những người đầu tiên đề xuất phương pháp gốc-đối ngẫu để giải các QHTT, mặc dù phương pháp tự nó không trở thành thuật toán để giải các QHTT nhưng nó đã được áp dụng rộng rãi trong lĩnh vực tối ưu hoá tổ hợp. Theo định lý về độ lệch bù trong lý thuyết QHTT (xem chương 1), cặp phương án đối ngẫu là các phương án tối ưu khi và chỉ khi chúng thoả mãn các điều kiện độ lệch bù. Vận dụng định lý này, phương pháp gốc-đối ngẫu xây dựng thuật toán giải QHTT như sau: xuất phát từ một phương án đối ngẫu y chấp nhận được, ta hoặc là tìm được một phương án gốc x thoả mãn điều kiện độ lệch bù gốc đối với y (và qua đó y cũng thoả mãn điều kiện độ lệch bù đối ngẫu), điều này chứng tỏ x , y tìm được là các phương án tối ưu. Trong trường hợp không tìm được phương án gốc x như vậy, ta sẽ lập được một phương án giúp cải tiến phương án y thành phương án đối ngẫu mới có giá trị hàm mục tiêu cao hơn. Việc tìm phương án x để x , y đồng thời thoả mãn các điều kiện độ lệch bù như vậy quy về giải một quy hoạch tuyến tính gọi là quy hoạch gốc hạn chế RP (Restricted Primal). Điểm đặc biệt của quy hoạch này là hàm mục tiêu không chứa hệ số và giá trị tối ưu của hàm mục tiêu bằng 0 tương đương với việc tìm được phương án gốc tối ưu. Nếu giá trị tối ưu >0 thì từ phương án tối ưu của quy hoạch đối ngẫu DRP (Dual Restricted Primal) của quy hoạch RP ta xây dựng được phương án đối ngẫu y mới có giá trị hàm mục tiêu cao hơn. Về tổng thể, việc giải QHTT bằng phương pháp đối ngẫu như trên thông qua việc giải một dãy các QHTT khác, cho nên nếu xét mục đích giải QHTT tổng quát thì phương pháp này không dẫn đến một đột phá nào. Tuy nhiên đối với các 15 bài toán trong lớp P, các QHTT hạn chế không trọng số đơn giản hơn QHTT gốc nhiều và thường là có thể giải bằng các thuật toán tổ hợp. Thực tế cho thấy, nhiều thuật toán giải các bài toán cơ bản trong tối ưu hoá tổ hợp hoặc được thiết kế hoặc có thể phân tích dựa trên phương pháp này. Ví dụ, các thuật toán tìm đường đi ngắn nhất của Dijsktra, tìm luồng cực đại của Ford-Fullkerson, . . . xem [PS88]. Mặc dù vậy ta biết rằng, nói chung các phương án tối ưu của QHTT làm yếu (từ mô hình QHN) của các bài toán NP-khó không phải là các phương án nguyên và cũng không thể mô hình hoá chúng ở dạng các QHTT có kích thước đa thức trừ khi NP=P. Vì vậy, không thể áp dụng trực tiếp phương pháp gốc-đối ngẫu ở trên để thiết kế thuật toán xấp xỉ cho các bài toán NP-khó. áp dụng phương pháp gốc-đối ngẫu thiết kế thuật toán xấp xỉ. Khi áp dụng phương pháp gốc-đối ngẫu để thiết kế thuật toán xấp xỉ, ta sẽ không cố thoả mãn tất cả các điều kiện độ lệch bù. Thay vào đó, ta chỉ đảm bảo điều kiện độ lệch bù gốc (điều này đóng vai trò quyết định trong việc đánh giá tỷ suất hiệu quả sau này). Dựa trên QHTT làm yếu từ mô hình QHN, thuật toán lần lượt cải tiến cặp phương án tuyến tính đối ngẫu nhằm tăng tính chấp nhận được của phương án gốc và tăng giá trị hàm mục tiêu của phương án đối ngẫu. Khi phương án gốc còn chưa là chấp nhận được thì tìm được hướng để tăng giá trị hàm mục tiêu của phương án đối ngẫu. Quá trình cải tiến đảm bảo: - Phương án gốc luôn nguyên và thoả mãn điều kiện độ lệch bù gốc nhưng có thể không là chấp nhận được. - Phương án đối ngẫu luôn chấp nhận được và có giá trị hàm mục tiêu tăng dần theo quá trình sửa đổi. Đánh giá tỷ suất hiệu quả. Xét cặp QHTT đối ngẫu của bài toán thiết kế mạng (xem chương 1), gọi F là tập cạnh của đồ thị bộ phận mà thuật toán gốc-đối ngẫu tìm ra. Tỷ suất hiệu quả của thuật toán được đánh giá thông qua so sánh giữa c F ce và giá trị của phương e F 16 án đối ngẫu y S f S . Do x thoả mãn điều kiện độ lệch bù gốc nên S V ce e F rằng F yS e F S :e S S yS F S . Nếu f . là hàm 0-1, và ta chứng minh được S V , yS 0 thì rõ ràng ta có thuật toán -xấp xỉ. Trên thực tế điều kiện này quá chặt, trong phương pháp gốc-đối ngẫu của Goemans-Williamson, nếu tại mỗi bước cải tiến phương án đối ngẫu (tăng giá trị của y S ) điều kiện trên đúng trên tổng thể các biến đối ngẫu được tăng (tức là nếu lấy giá trị trung bình trên tất cả các biến y S tăng trong bước cải tiến hiện tại) thì ta vẫn có thuật toán -xấp xỉ. Xem [Hoc96] để biết thêm chi tiết về các nguyên tắc thiết kế thuật toán xấp xỉ theo phương pháp gốc-đối ngẫu. Cho đến trước khi phương pháp gốc-đối ngẫu ra đời, việc tìm thuật toán xấp xỉ hiệu quả cho các bài toán tối ưu hoá tổ hợp phụ thuộc nhiều vào cấu trúc của bài toán. Điểm ưu việt của phương pháp gốc-đối ngẫu là ở chỗ, nó chỉ ra một sơ đồ tổng quát để có thể thiết kế thuật toán xấp xỉ cho các bài toán tối ưu hoá tổ hợp dựa trên mô hình QHN của chúng. Ngoài ra, so với phương pháp lặp liên tiếp, mà ta sẽ bàn ở chương 3 thuật toán thiết kế theo phương pháp gốc-đối ngẫu là thuật toán tổ hợp nó không đòi hòi giải QHTT và bởi vậy sẽ hiệu quả hơn trên thực tế. Nói chung, các bài toán thiết kế mạng đều là các bài toán NP-khó, ngay cả khi hạn chế chúng chỉ ở những dạng khá đơn giản. Ví dụ, bài toán cây Steiner là NP-khó, thậm chí khi hàm giá thoả mãn độ đo Euclid; hay bài toán tìm đồ thị bộ phận 2-EC nhỏ nhất cũng là NP-khó ngay cả khi các cạnh có cùng trọng số đơn vị. Bởi vậy, trong các nghiên cứu về bài toán thiết kế mạng, người ta dành nhiều sự quan tâm đến việc thiết kế thuật toán xấp xỉ cho chúng. Trên thực tế, những thành công đầu tiên của phương pháp gốc-đối ngẫu trong thiết kế thuật toán xấp xỉ là những thuật toán xấp xỉ cho một số bài toán thiết kế mạng. Agrawal, Klein, Ravi [AKR91] là những người đầu tiên áp dụng phương pháp gốcđối ngẫu để thiết kế thuật toán xấp xỉ. Các ông đã xây dựng được thuật toán 2-xấp