Tài liệu Phương pháp tối ưu đàn kiến giải bài toán tìm tập thống trị nhỏ nhất của một đồ thị

ĐẠI HỌC THÁI NGUYÊN .. TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG LÊ THÁI HÒA PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN GIẢI BÀI TOÁN TÌM TẬP THỐNG TRỊ NHỎ NHẤT CỦA MỘT ĐỒ THỊ LUẬN VĂN THẠC SĨ KHOA HỌC Thái Nguyên - Năm 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG LÊ THÁI HÒA PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN GIẢI BÀI TOÁN TÌM TẬP THỐNG TRỊ NHỎ NHẤT CỦA MỘT ĐỒ THỊ Chuyên ngành: Khoa học máy tính Mã số: 60.48.01.01 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. ĐỖ ĐỨC ĐÔNG Thái Nguyên - Năm 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn i LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi, dƣới sự chỉ dẫn của TS. Đỗ Đức Đông. Các số liệu, kết quả nêu trong luận văn là trung thực, bảo đảm tính khách quan, luận văn này cho đến nay chƣa đƣợc bảo vệ tại bất kỳ hội đồng nào và chƣa hề đƣợc công bố trên bất kỳ phƣơng tiện nào khác. Các tài liệu tham khảo có nguồn gốc xuất xứ rõ ràng. Tác giả xin chịu trách nhiệm về những lời cam đoan trên. Thái nguyên, ngày 23 tháng 7 năm 2015 Tác giả luận văn Lê Thái Hòa Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn ii LỜI CẢM ƠN Em xin chân thành cảm ơn thầy giáo TS. Đỗ Đức Đông đã trực tiếp giao cho em đề tài, tận tình hƣớng dẫn và tạo mọi điều kiện cho em hoàn thành luận văn. Em xin chân thành cảm ơn các thầy cô giáo, các cán bộ nhân viên phòng đào tạo, ban lãnh đạo Trƣờng Đại học Công nghệ thông tin và Truyền thông đã giúp đỡ tạo điều kiện cho em hoàn thành bản luận văn này. Em xin bày tỏ lòng cảm ơn của mình đến giáo sƣ Raka Jovannovic, ngƣời đã chia sẻ cho em rất nhiều tài liệu về thuật toán tối ƣu hóa đàn kiến và cũng là ngƣời đã cung cấp cho em bộ dữ liệu để em thử nghiệm trong bài luận văn này. Cuối cùng, em xin chân thành cảm ơn sự quan tâm giúp đỡ của gia đình, bạn bè và tập thể lớp Cao học K12I đã cổ vũ động viên em hoàn thành tốt luận văn của mình. Thái nguyên, ngày 23 tháng 7 năm 2015 Học viên Lê Thái Hòa Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn iii MỤC LỤC LỜI CAM ĐOAN .......................................................................................... i LỜI CẢM ƠN ............................................................................................... ii MỤC LỤC .................................................................................................... iii Danh mục các ký hiệu và chữ viết tắt ........................................................... v Danh mục các bảng ..................................................................................... vii Danh mục các hình ..................................................................................... viii MỞ ĐẦU ....................................................................................................... 1 Chƣơng 1. BÀI TOÁN TÌM TẬP THỐNG TRỊ NHỎ NHẤT CỦA MỘT ĐỒ THỊ ......................................................................................................... 3 1.1. Bài toán tối ƣu tổ hợp tổng quát ......................................................... 3 1.2. Bài toán tìm tập thống trị nhỏ nhất của một đồ thị (MWDSP) ........... 5 1.3. Các cách tiếp cận hiện nay giải quyết bài toán tìm tập thống trị nhỏ nhất của đồ thị ............................................................................................ 5 1.3.1. Thuật toán tham lam tìm tập phủ đỉnh nhỏ nhất. .......................... 5 1.3.2. Thuật toán tham lam 1 (Greedy1) ................................................. 6 1.3.2. Thuật toán tham lam 2 (Greedy2) ................................................. 9 1.4. Một số ứng dụng trong thực tế về bài toán MWDSP ....................... 10 1.5. Kết luận chƣơng ................................................................................ 11 Chƣơng 2. PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN.................................... 13 2.1. Kiến tự nhiên và kiến nhân tạo ......................................................... 13 2.1.1. Kiến tự nhiên............................................................................... 13 2.1.2. Kiến nhân tạo .............................................................................. 17 2.2. Phƣơng pháp ACO cho bài toán TƢTH tổng quát ........................... 18 2.2.1. Đồ thị cấu trúc............................................................................. 18 2.2.2. Thuật toán ACO tổng quát .......................................................... 20 2.3. Phƣơng pháp ACO giải bài toán ngƣời chào hàng ........................... 23 2.3.1. Bài toán TSP và đồ thị cấu trúc .................................................. 23 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn iv 2.3.2. Các thuật toán ACO giải bài toán TSP ....................................... 24 2.3.2.1. Hệ kiến AS ........................................................................... 27 2.3.2.2. Hệ đàn kiến ACS ................................................................. 30 2.3.2.3. Hệ kiến Max-Min ................................................................ 33 2.3.2.4. Phƣơng pháp Max-Min trơn: SMMAS (Smoothed Max Min Ant System) ....................................................................................... 36 2.4. Một số lƣu ý khi sử dụng các thuật toán ACO ................................. 36 2.4.1. Thông tin heuristic ...................................................................... 37 2.4.2. Số lƣợng kiến .............................................................................. 37 2.4.3. Tham số bay hơi.......................................................................... 38 2.5. Kết luận chƣơng ................................................................................ 38 Chƣơng 3. PHƢƠNG PHÁP TỐI ƢU HÓA ĐÀN KIẾN GIẢI BÀI TOÁN TÌM TẬP THỐNG TRỊ NHỎ NHẤT CỦA ĐỒ THỊ................................. 39 3.1. Xây dựng lời giải .............................................................................. 40 3.2 Cập nhật mùi cho bài toán MWDSP .................................................. 41 3.3. Thực nghiệm và đánh giá .................................................................. 43 3.4. Kết luận chƣơng ................................................................................ 48 KẾT LUẬN ................................................................................................. 49 TÀI LIỆU THAM KHẢO ........................................................................... 51 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn v Danh mục các ký hiệu và chữ viết tắt Kí hiệu và chữ viết tắt Ý nghĩa Cận trên của vết mùi Cận giữa của vết mùi Vết mùi đƣợc khởi tạo ban đầu Vết mùi trên cạnh Vết mùi trên đỉnh  Thông tin heuristic trên cạnh  Thông tin heuristic trên đỉnh Số vòng lặp trong thuật toán ACO Số kiến sử dụng trong thuật toán ACO Tham số bay hơi 3-LAS Three-Level Ant System (Hệ kiến ba mức) ACO Ant Colony Optimization (Tối ƣu đàn kiến) ACS Ant Colony System (Hệ đàn kiến) AS Ant System (Hệ kiến) G-best Global-best (Lời giải tốt nhất tính đến thời điểm hiện tại) I-best Iteration-best (Lời giải tốt nhất trong bƣớc lặp hiện tại) MLAS Multi-level Ant System (Hệ kiến đa mức) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn vi MMAS Max-Min Ant System (Hệ kiến Max Min) MWDSP Bài toán tìm tập thống trị nhỏ nhất của đồ thị SMMAS Smoothed Max-Min Ant System (Hệ kiến Max Min trơn) TSP Bài toán ngƣời chào hàng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn vii Danh mục các bảng Trang Bảng 2.1: Thuật toán ACO theo thứ tự thời gian xuất hiện……….. 26 Bảng 3.1: Kết quả thực nghiệm trên bộ dữ liệu 1 với kích thƣớc nhỏ…………………………………………………………………. 44 Bảng 3.2: Kết quả thực nghiệm trên bộ dữ liệu 2 với kích thƣớc nhỏ…………………………………………………………………. 45 Bảng 3.3: Kết quả thực nghiệm trên bộ dữ liệu 1 với kích thƣớc lớn…………………………………………………………………. 46 Bảng 3.4: Kết quả thực nghiệm trên bộ dữ liệu 2 với kích thƣớc lớn…………………………………………………………………. 47 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn viii Danh mục các hình Trang Hình 1.1: Thuật toán tham lam tìm tập phủ đỉnh ..……………….. 6 Hình 1.2: Một ví dụ về đồ thị làm cho Greedy1 sai kết quả……….. 7 Hình 1.3: Thuật toán tính trong Greedy1_new……………….. 8 Hình 1.4: Thuật toán tính  trong Greedy2_new……………….. 10 Hình 2.1: Thực nghiệm cây cầu đôi………………………………... 15 Hình 2.2: Tỉ lệ các con kiến chọn đƣờng đi………………………... 15 Hình 2.3: Thí nghiệm bổ xung……………………………………... 16 Hình 2.4: Đồ thị cấu trúc tổng quát cho bài toán cực trị hàm ………………………………………………………... 20 Hình 2.5: Thuật toán ACO………………………………………… 21 Hình 2.6: Thuật toán ACO giải bài toán TSP có sử dụng tìm kiếm cục bộ……………………………………………………………… 25 Hình 3.1: Thuật toán cập nhật mùi SMMAS cho bài toán MWDSP 42 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 1 MỞ ĐẦU Hiện nay, có rất nhiều bài báo, luận văn, luận án hay các công trình nghiên cứu đề cập đến vấn đề giải quyết các bài toán tối ƣu tổ hợp. Đa số các bài toán này thuộc lớp các bài toán NP – khó. Trừ các bài toán cỡ nhỏ có thể tìm lời giải bằng cách tìm kiếm vét cạn, còn lại thì thƣờng không thể tìm đƣợc lời giải tối ƣu. Đối với các bài toán kích thƣớc lớn không có phƣơng pháp giải đúng. Hiện nay, ngƣời ta thƣờng tìm lời giải gần đúng nhờ các thuật toán mô phỏng tự nhiên nhƣ giải thuật di truyền (Genetic Algorithm - GA), tối ƣu bầy đàn (Particle Swarm Optimization -PSO)… Trong các phƣơng pháp mô phỏng tự nhiên, tối ƣu hóa đàn kiến (Ant Colony Optimization - ACO) là cách tiếp cận metaheuristic tƣơng đối mới, đƣợc giới thiệu bởi Dorigo năm 1991 đang đƣợc nghiên cứu và ứng dụng rộng rãi cho các bài toán TƢTH - khó. Các thuật toán ACO mô phỏng cách tìm đƣờng đi của các con kiến thực. Trên đƣờng đi, mỗi con kiến thực để lại một vết hoá chất gọi là vết mùi (pheromone trail) và theo vết mùi của các con kiến khác để tìm đƣờng đi. Đƣờng có nồng độ vết mùi càng cao thì càng có nhiều khả năng đƣợc các con kiến chọn. Nhờ cách giao tiếp gián tiếp này đàn kiến tìm đƣợc đƣờng đi ngắn nhất từ tổ tới nguồn thức ăn. Theo ý tƣởng đó, các thuật toán ACO sử dụng kết hợp thông tin kinh nghiệm (heuristic) và học tăng cƣờng qua các vết mùi của các con kiến nhân tạo để giải các bài toán TƢTH bằng cách đƣa về bài toán tìm đƣờng đi tối ƣu trên đồ thị cấu trúc tƣơng ứng của bài toán. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 2 Bài luận văn này em trình bày phƣơng pháp tối ƣu hóa đàn kiến ACO để giải quyết bài toán tìm tập thống trị nhỏ nhất của một đồ thị vô hƣớng. Em sẽ thử nghiệm trên các đồ thị với kích cỡ khác nhau, mật độ cạnh khác nhau, các chức năng phân phối trọng số trên các đỉnh khác nhau để thấy đƣợc hiệu quả của thuật toán đề xuất so với một số thuật toán đang đƣợc sử dụng. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 3 Chƣơng 1. BÀI TOÁN TÌM TẬP THỐNG TRỊ NHỎ NHẤT CỦA MỘT ĐỒ THỊ Trong các bài toán thực tế cũng nhƣ trong lý thuyết, ta thƣờng phải tìm các giá trị cho các biến rời rạc để cực trị hàm mục tiêu nào đó. Các bài toán này thƣờng dễ phát biểu nhƣng lại khó giải do chúng thuộc loại tối ƣu tổ hợp (TƢTH) NP - khó. Chƣơng này giới thiệu các bài toán tối ƣu tổ hợp dƣới dạng tổng quát, bài toán tìm tập thống trị nhỏ nhất và các cách tiếp cận hiện nay. 1.1. Bài toán tối ƣu tổ hợp tổng quát Trong đời sống thực tế ta thƣờng phải giải quyết nhiều bài toán TƢTH quan trọng. Chẳng hạn nhƣ: tìm đƣờng đi ngắn nhất nối hai điểm trên một đồ thị đã cho, lập kế hoạch phân phối nguồn hàng tới nơi tiêu thụ với chi phí cực tiểu, lập thời khóa biểu cho giáo viên và học sinh thuận lợi nhất, định tuyến cho các gói dữ liệu trong Internet, lập lịch hợp lý cho các hệ thống sản xuất, đối sánh các chuỗi gen trong sinh học phân tử v.v… Mỗi bài toán TƢTH ứng với một bộ ba ( S , f , ) trong đó: - S là tập hữu hạn trạng thái (lời giải tiềm năng hay phƣơng án); - f là hàm mục tiêu xác định trên ; -  là tập các ràng buộc. Mỗi phƣơng án s  S thỏa mãn các ràng buộc  gọi là phƣơng án trả lời (hay lời giải). Mục đích của ta là tìm phƣơng án chấp nhận đƣợc s* tối ƣu hóa toàn cục hàm mục tiêu , tức là một phƣơng án s* tốt nhất. Chẳng hạn với bài toán cực tiểu thì ta phải tìm với mọi phƣơng án trả lời . Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 4 Mỗi bài toán đều có thể chỉ ra một tập hữu hạn gồm { } sao cho mỗi phƣơng án trong thành phần đều biễu diễn đƣợc nhờ và  có các đặc liên kết các thành phần trong nó. Cụ thể hơn, các tập điểm sau: là tập các vectơ trên 1) Ký hiệu { } Khi đó, mỗi phƣơng án định nhờ ít nhất một vectơ trong 2) Tồn tại tập con nào đó của 3) Từ của : đƣợc xác trong . và ánh xạ , trong đó tập rỗng với mọi có độ dài không quá từ lên sao cho không có thể xây dựng đƣợc từ tập con nhờ thủ tục mở rộng tuần tự dƣới đây. nhƣ sau: ta mở rộng tuần tự thành là mở rộng đƣợc với mọi i) Ta xem . là mở rộng đƣợc và chƣa thuộc ii) Giả sử ràng buộc , xác định tập con . Từ tập của , sao cho với mọi ) là mở rộng đƣợc. thì iii) Áp dụng thủ tục mở rộng từ các phần tử đƣợc mọi phần tử của cho phép ta xây dựng . Nhƣ vậy, mỗi bài toán TƢTH đƣợc xem là một bài toán cực trị hàm có biến, trong đó mỗi biến nhận giá trị trong tập hữu hạn kể cả giá trị rỗng. Nói một cách khác, nó là bài toán tìm kiếm trong không gian vectơ độ dài không quá trên đồ thị đầy đủ có các đỉnh có nhãn trong tập . Chú ý: Với các bài toán TƢTH có dạng giải tích: Tìm cực trị hàm trong đó mỗi biến nhận giá trị trong tập hữu hạn ứng và các biến này thỏa mãn các ràng buộc  nào đó, thì Số hóa bởi Trung tâm Học liệu – ĐHTN tƣơng là tập http://www.lrc.tnu.edu.vn 5 là các vectơ và trong tập , là tập - chiều, trong đó thành phần còn nhận giá trị là tập các vectơ thỏa mãn các ràng buộc . 1.2. Bài toán tìm tập thống trị nhỏ nhất của một đồ thị (MWDSP) { Cho một đồ thị vô hƣớng cạnh của đồ thị. Với mỗi đỉnh Một tập thống trị của } trong đó là tập đỉnh, có gắn một trọng số là một tập đều kề với ít nhất một đỉnh thuộc tập  là tập . sao cho mọi đỉnh thuộc . Trong các tập thống trị đó, tập thống trị nhỏ nhất là tập thống trị mà tổng trọng số của tất cả các đỉnh thuộc nhỏ nhất. Bài toán tìm tập thống trị nhỏ nhất của đồ thị thuộc lớp bài toán NP- khó và có nhiều ứng dụng trong thực tế. Đã có nhiều nhà nghiên cứu đƣa ra các phƣơng pháp khác nhau để giải quyết bài toán trên, tuy nhiên các thuật toán này chƣa thực sự hiệu quả. 1.3. Các cách tiếp cận hiện nay giải quyết bài toán tìm tập thống trị nhỏ nhất của đồ thị 1.3.1. Thuật toán tham lam tìm tập phủ đỉnh nhỏ nhất. Trƣớc hết ta xét đồ thị mà chƣa quan tâm đến trọng số của các đỉnh (coi mỗi đỉnh đều có trọng số bằng 1). Khi đó bài toán trở thành “Tìm tập phủ đỉnh có số lƣợng đỉnh ít nhất”. Để dễ hình dung ta gọi: - Tập các đỉnh đã đƣợc chọn vào làm kết quả là các đỉnh tô màu đen ( ). - Tập các đỉnh không thuộc nhƣng kề với ít nhất một đỉnh thuộc gọi là các đỉnh tô màu xám ( ). Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 6 - Các đỉnh còn lại là các đỉnh chƣa đƣợc phủ gọi là đỉnh tô màu trắng ( ). Trong tài liệu [4] ngƣời ta đƣa ra ý tƣởng nhƣ sau: Tại mỗi lần lặp ta kết nạp thêm một đỉnh mới thuộc hoặc vào Việc ƣu tiên chọn đỉnh nào đó kết nạp vào | |( cho đến khi . đƣợc xác định bởi giá trị của là những đỉnh trắng kề với ). Thuật toán đƣợc mô ta nhƣ sau: ; While ; Do ; Begin Tìm (| | lớn nhất). ; { }; ; End; Hình 1.1: Thuật toán tham lam tìm tập phủ đỉnh 1.3.2. Thuật toán tham lam 1 (Greedy1) Với ý tƣởng trình bày trong tài liệu [12] ngƣời ta biến đổi đồ thị ban đầu thành đồ thị đầy đủ bằng cách thêm các cạnh vào đồ thị. Khi đó những cạnh ban đầu của đồ thị có trọng số bằng 1 (kí hiệu bằng màu đen), cạnh đƣợc thêm vào có trọng số bằng 0 (kí hiệu bằng màu đỏ). Khi thêm một đỉnh vào tập ta phải cập nhật lại đồ thị, tất cả những cạnh liên thuộc với đỉnh đó sẽ đƣợc tô màu đỏ, những đỉnh kề với nó bằng cạnh màu đen sẽ đƣợc tô thành màu xám. Nhƣ vậy sau khi ta kết nạp đƣợc đổi thành đỉnh vào thì đồ thị đƣợc biến . Khi đó trọng số của cạnh của đồ thị đƣợc biểu diễn nhƣ sau: (1.1) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 7 Lƣu ý chỉ nhận giá trị bằng 0 hoặc bằng 1. Khi muốn kết nạp một đỉnh nào đó vào thì giải pháp đƣợc chọn để ƣu tiên nhƣ sau: ∑ (1.2) (1.3) thực chất là số lƣợng những đỉnh kề Từ (1.1) và (1.2) ta thấy với mà chƣa đƣợc phủ (còn là đỉnh màu trắng). Nhƣ vậy việc chọn một đỉnh để kết nạp vào dựa trên hai tiêu chí: + Số lƣợng đỉnh màu trắng kề với nó càng nhiều càng tốt. + Trọng số của đỉnh đó càng nhỏ càng tốt. Phép cộng 1 vào tử số để đảm bảo đƣợc việc so sánh giữa các đỉnh không còn kết nối nữa, tức là những đỉnh cô lập (khi đó ta sẽ chọn đỉnh nào có trọng số nhỏ hơn). Theo công thức (1.3) ta thấy rằng khi đồ thị chỉ gồm các đỉnh cô lập thì việc lựa chọn đỉnh nào chỉ phụ thuộc vào trọng số của nó chứ không phân biệt đỉnh đó đã đƣợc phủ hay chƣa. Tức là có thể chọn thêm vào kết quả đỉnh đã đƣợc tô màu xám mà không kề với bất kỳ đỉnh màu trắng nào. A 1 C B 6 5 Một ví dụ về đồ thị làm cho Greedy1 sai kết quả. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 8 Ta có đỉnh A là đỉnh đã đƣợc chọn, bây giờ xét tiếp đỉnh B và C, ta có: nên theo Greedy1 thì đỉnh tiếp theo đƣợc chọn vào Vì làm kết quả là đỉnh B, sau đó mới chọn đỉnh C. Kết quả cuối cùng bằng . (kết quả này sai so với kết quả thực tế). Ta có thể cải tiến thuật toán này bằng cách thêm vào đồ thị ban đầu những cạnh khuyên với Khi đó nếu một đỉnh màu xám nằm cô lập (đã đƣợc phủ bởi đỉnh khác) thì giá trị của nó sẽ bằng không, trong khi một đỉnh màu trắng nằm cô lập thì giá trị của nó lại bằng 1. Vì vậy ta không cần cộng thêm 1 vào tử số, đồng thời tránh đƣợc sai sót nhƣ trong ví dụ trên (cải tiến này đƣợc minh họa trong chƣơng 3 bằng thuật toán Greedy1_new). Khi đó công thức (1.3) sẽ đƣợc biến đổi nhƣ sau: (1.4) For to do If kề và là đỉnh mầu trắng then ; Hình 1.3: Thuật toán tính Số hóa bởi Trung tâm Học liệu – ĐHTN trong Greedy1_new. http://www.lrc.tnu.edu.vn 9 1.3.2. Thuật toán tham lam 2 (Greedy2) Trong thuật toán tham lam 1 việc lựa chọn các đỉnh chỉ coi trọng số lƣợng các đỉnh kề với nó chứ không quan tâm đến tổng trọng số của các đỉnh kề với nó. Tài liệu [6], [11] đã cải tiến công thức trên bằng việc cho thêm tổng trọng số của các đỉnh màu trắng kề với nó. Nếu tổng trọng số này càng lớn thì càng đƣợc ƣu tiên. ∑  (1.5) Cũng tƣơng tự nhƣ thuật toán trƣớc, tại công thức (1.5) giả sử đồ thị chỉ gồm các đỉnh thuộc W và R (màu trắng và màu xám) nằm cô lập. Lúc đó với mọi , làm cho  nhƣ vậy sẽ không có tiêu chí để chọn lựa đỉnh nào là đỉnh tiếp theo kết nạp vào kết quả. Trên thực tế ta thấy việc chọn những đỉnh màu xám không có ý nghĩa gì mà chỉ làm xấu đi kết quả. Vì vậy, để thuật toán tốt hơn ta vẫn phải thêm vào đồ thị ban đầu những cạnh với . Do đó ta có thể sửa công thức (1.5) thành công thức sau:  ∑ (1.6) Cải tiến này làm cho kết quả tốt hơn đáng kể so với thuật toán Greedy2 trong [11] (ta gọi thuật toán đã cải tiến là Greedy2_new). Trong hai thuật toán tham lam đã đề cập ở trên việc thêm những cạnh khuyên vào đồ thị làm cho thuật toán cải thiện đáng kể vì tránh đƣợc việc chọn những đỉnh màu xám vào tập kết quả trong khi nó không còn kề với một đỉnh màu trắng nào. Việc chỉnh sửa công thức chỉ là thay đổi cho phù hợp sau khi đã thêm các cạnh khuyên chứ không phải là nguyên nhân chủ yếu làm cho kết quả tốt hơn. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 10 For to do If kề và là đỉnh mầu trắng then { }  ; Hình 1.4: Thuật toán tính  trong Greedy2_new. 1.4. Một số ứng dụng trong thực tế về bài toán MWDSP Đa số các bài toán về đồ thị đều đƣợc áp dụng rộng rãi trong thực tế, bài toán MWDSP cũng không ngoại lệ, có thể đƣa ra một số ứng dụng cụ thể nhƣ sau: Ứng dụng 1: Ứng dụng trong việc chọn địa điểm để xây dựng cột phát sóng điện thoại. Giả sử một công ty viễn thông muốn phát sóng điện thoại di động cho tất cả ngôi làng, do địa hình phức tạp nên khi xây dựng cột phát sóng tại ngôi làng thì đƣơng nhiên ngôi làng sẽ đƣợc phủ sóng, ngoài ra có thể có một số ngôi làng khác cũng sẽ đƣợc phủ sóng. Do giá thành mặt bằng để thuê đặt cột phát sóng, cũng nhƣ nhiều yếu tố khác làm cho việc xây dựng và thuê đặt địa điểm của các cột phát sóng tại các ngôi làng là khác nhau. Vấn đề đặt ra cho công ty này là làm sao xây dựng các Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn