Đề Xuất Thuật Toán Hiệu Quả Cho Bài Toán Tập Đỉnh Thống Trị Có Trọng Số Nhỏ Nhất

Luận văn thạc sĩ toán học nghiên cứu máy tính một thuật toán hiệu quả cho tập đỉnh thống trị có trọng số nhỏ nhất, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải pháp

• Tác giả: Đinh Văn Viết
• Người hướng dẫn: PGS. Hoàng Xuân Huấn
• Trường học: Đại Học Quốc Gia Hà Nội
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Thuật Toán Hiệu Quả Cho Bài Toán Tập Đỉnh Thống Trị Có Trọng Số Nhỏ Nhất
• Loại tài liệu: Luận Văn
• Năm xuất bản: 2021
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH SÁCH KÝ HIỆU VÀ VIẾT TẮT
• 1. CHƯƠNG 1: GIỚI THIỆU BÀI TOÁN TẬP ĐỈNH THỐNG TRỊ CÓ TRỌNG SỐ NHỎ NHẤT
• 1.1. Bài toán tập đỉnh thống trị có trọng số cực tiểu và các bài toán liên quan
• 1.2. Các nghiên cứu liên quan
• 1.3. Các ứng dụng liên quan đến bài toán tập đỉnh thống trị
• 1.4. Một số định lý quan trọng
• 1.4.1. Định lý Cook-Levin
• 1.4.2. Định lý không có bữa trưa miễn phí
• 2. CHƯƠNG 2: THUẬT TOÁN KẾT HỢP TÌM KIẾM VỚI SỐ LƯỢNG HÀNG XÓM LỚN
• 2.1. Thuật toán HLNS
• 2.2. Thuật toán khái tạo cho tập đỉnh thống trị
• 2.3. Các thuật toán xóa các đỉnh trong tập đỉnh thống trị
• 2.4. Các thuật toán sửa tập đỉnh
• 2.5. Các thuật toán xóa bỏ đỉnh dư thừa trong tập đỉnh thống trị
• 3. CHƯƠNG 3: THỰC NGHIỆM VÀ KẾT QUẢ
• 3.1. Giới thiệu thực nghiệm
• 3.2. Kết quả thực nghiệm
• 3.2.1. Thực nghiệm trên TH1
• 3.2.2. Thực nghiệm trên TH2
• 4. CHƯƠNG 4: ỨNG DỤNG CHỌN NGƯỜI ĐIỀU HÀNH CHO NHÓM MODERATOR-SELECTOR
• 4.1. Giới thiệu ứng dụng chọn người điều hành cho nhóm moderator-selector
• 4.2. Cách sử dụng ứng dụng
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Bài Toán Tập Đỉnh Thống Trị Có Trọng Số Nhỏ Nhất

Bài toán tập đỉnh thống trị có trọng số nhỏ nhất (Minimum Weighted Dominating Set - MWDS) là một bài toán tối ưu tổ hợp kinh điển trong lý thuyết đồ thị. Bài toán này thuộc lớp NP-khó, nghĩa là không có thuật toán nào được biết có thể giải quyết nó một cách chính xác trong thời gian đa thức cho mọi trường hợp. MWDS có nhiều ứng dụng thực tế quan trọng, từ thiết kế mạng lưới cảm biến không dây đến phân tích mạng xã hội. Do tính NP-khó của nó, các nhà nghiên cứu đã tập trung vào việc phát triển các giải thuật gần đúng và phương pháp heuristics để tìm kiếm các giải pháp chấp nhận được trong thời gian hợp lý. Các thuật toán này thường sử dụng các kỹ thuật như giải thuật tham lam, giải thuật di truyền, và phương pháp heuristics đặc biệt để khám phá không gian tìm kiếm một cách hiệu quả. Theo tài liệu gốc, "Nhiều ứng dụng được tạo ra để đáp ứng sự phát triển của các mạng lưới từ sự phát triển của xã hội".

1.1. Định Nghĩa Bài Toán Tập Đỉnh Thống Trị Có Trọng Số

Cho một đồ thị G = (V, E), trong đó V là tập hợp các đỉnh và E là tập hợp các cạnh, mỗi đỉnh v ∈ V có một trọng số w(v) > 0. Một tập đỉnh D ⊆ V được gọi là tập đỉnh thống trị nếu mọi đỉnh không thuộc D đều kề với ít nhất một đỉnh trong D. Bài toán MWDS là tìm một tập đỉnh thống trị D sao cho tổng trọng số của các đỉnh trong D là nhỏ nhất. Bài toán này có thể được mô hình hóa bằng cách sử dụng lập trình tuyến tính và Integer Programming, nhưng việc giải quyết các mô hình này thường rất tốn kém về mặt tính toán cho các đồ thị lớn. "Bài toán tập đỉnh thống trị có trọng số nhỏ nhất (MWDS) là một trong những bài toán NP-Hard kinh điển được nhiều nhà nghiên cứu quan tâm và đã được ứng dụng vào trong thực tiễn."

1.2. Độ Phức Tạp Tính Toán Của Bài Toán MWDS

Do tính NP-khó của bài toán, việc tìm kiếm một thuật toán hiệu quả (ví dụ: thời gian đa thức) để giải quyết MWDS là một thách thức lớn. Các giải thuật chính xác thường có độ phức tạp thời gian theo cấp số mũ, khiến chúng không phù hợp cho các đồ thị lớn. Do đó, các nhà nghiên cứu thường tập trung vào việc phát triển các giải thuật gần đúng và phương pháp heuristics để tìm kiếm các giải pháp chấp nhận được trong thời gian hợp lý. Việc đánh giá hiệu năng thuật toán thường được thực hiện bằng cách so sánh các giải pháp tìm được với các giải pháp tối ưu đã biết hoặc với các giải pháp tìm được bằng các thuật toán khác. Theo tài liệu gốc, "Tuy đã có rất nhiều thuật toán được đề xuất, nhưng các thuật toán vẫn chưa đủ hiệu quả để giải quyết bài toán trên."

II. Thách Thức và Vấn Đề Khi Giải Bài Toán Tập Đỉnh Thống Trị

Giải bài toán tập đỉnh thống trị có trọng số nhỏ nhất đặt ra nhiều thách thức đáng kể. Một trong những thách thức chính là tính NP-khó của bài toán, khiến việc tìm kiếm giải pháp tối ưu trở nên cực kỳ khó khăn cho các đồ thị lớn. Việc thiết kế các thuật toán hiệu quả đòi hỏi sự cân bằng giữa độ chính xác và thời gian tính toán. Ngoài ra, việc mô hình hóa bài toán một cách phù hợp để áp dụng các phương pháp giải quyết hiện có cũng là một vấn đề quan trọng. Việc lựa chọn các tham số phù hợp cho các thuật toán (ví dụ: số lượng quần thể trong thuật toán di truyền) cũng có thể ảnh hưởng đáng kể đến hiệu suất của chúng. Các ràng buộc về bộ nhớ và khả năng xử lý cũng có thể giới hạn khả năng giải quyết các đồ thị rất lớn. Theo tài liệu, "Việc tìm ra tập đỉnh này giúp việc phân tích thiết kế trên mạng hiệu quả hơn, do thông thường các tác động lên đồ thị sẽ ảnh hưởng chủ yếu bởi tập đỉnh chính."

2.1. Khó Khăn Trong Tìm Kiếm Giải Pháp Tối Ưu

Không gian tìm kiếm cho bài toán MWDS là rất lớn, đặc biệt là đối với các đồ thị lớn. Việc tìm kiếm một giải pháp tối ưu đòi hỏi phải duyệt qua một số lượng lớn các tập đỉnh tiềm năng, điều này có thể trở nên bất khả thi về mặt tính toán. Các giải thuật chính xác như thuật toán nhánh cận có thể được sử dụng để tìm kiếm giải pháp tối ưu cho các đồ thị nhỏ, nhưng chúng không thể mở rộng cho các đồ thị lớn hơn. Do đó, cần phải sử dụng các giải thuật gần đúng và phương pháp heuristics để tìm kiếm các giải pháp chấp nhận được trong thời gian hợp lý.

2.2. Hạn Chế Của Các Thuật Toán Hiện Tại

Mặc dù có nhiều thuật toán đã được phát triển để giải quyết bài toán MWDS, nhưng không có thuật toán nào hoạt động tốt trong mọi trường hợp. Các giải thuật tham lam có thể tìm kiếm giải pháp nhanh chóng, nhưng chúng thường không đảm bảo tìm được giải pháp tối ưu hoặc thậm chí là gần tối ưu. Các giải thuật di truyền và thuật toán bầy đàn có thể khám phá không gian tìm kiếm một cách hiệu quả hơn, nhưng chúng có thể tốn kém về mặt tính toán và đòi hỏi việc điều chỉnh các tham số một cách cẩn thận. Theo tài liệu gốc, "Các thuật toán matheuristic có ưu điểm là đưa ra lời giải đủ tốt trong một thời gian hợp lý so với các thuật toán tham lam hoặc các thuật toán ngẫu nhiên."

III. Thuật Toán HLNS Giải Pháp Hiệu Quả Cho Tập Đỉnh Thống Trị

Bài toán tối ưu hóa tổ hợp này đòi hỏi các phương pháp tiếp cận sáng tạo. Một phương pháp hiệu quả là thuật toán HLNS (Hybrid Large Neighborhood Search), kết hợp tìm kiếm trong lân cận lớn với các chiến lược khác để cải thiện hiệu suất. Thuật toán này cho phép khám phá không gian giải pháp rộng lớn hơn so với các phương pháp truyền thống. Theo tài liệu gốc, "Luận văn này đề xuất thuật toán kết hợp tìm kiếm với số lượng hàng xóm lớn (HLNS) để giải quyết bài toán đạt chất lượng kết quả tốt trong lượng thời gian xác định trên một số bộ dữ liệu chuẩn.". Điều này đặc biệt quan trọng khi đối mặt với tính NP-khó của bài toán, nơi các giải pháp tối ưu rất khó tìm thấy.

3.1. Nguyên Lý Hoạt Động Của Thuật Toán HLNS

Thuật toán HLNS hoạt động bằng cách lặp đi lặp lại việc phá hủy một phần của giải pháp hiện tại và sau đó xây dựng lại nó. Quá trình phá hủy thường liên quan đến việc loại bỏ một số đỉnh khỏi tập đỉnh thống trị hiện tại, trong khi quá trình xây dựng lại liên quan đến việc thêm các đỉnh mới để khôi phục tính chất thống trị. Việc lựa chọn các đỉnh để loại bỏ và thêm vào thường được thực hiện một cách ngẫu nhiên, nhưng có thể được hướng dẫn bởi các phương pháp heuristics để cải thiện hiệu quả. Theo tài liệu gốc, "Thuật toán LNS sử dụng hai phép toán là DEL (phép xóa) và REPAIR (phép sửa) để tìm kiếm lời giải có chất lượng tốt, trong đó để tạo ra ứng viên mới S+ sẽ được tạo ra từ lời giải hiện tại S."

3.2. Ưu Điểm Của Thuật Toán Tìm Kiếm Lân Cận Lớn

Thuật toán HLNS có một số ưu điểm so với các thuật toán khác. Thứ nhất, nó có thể khám phá không gian tìm kiếm rộng lớn hơn, giúp tìm kiếm các giải pháp tốt hơn. Thứ hai, nó có thể dễ dàng kết hợp với các phương pháp heuristics khác để cải thiện hiệu suất. Thứ ba, nó có thể được điều chỉnh để giải quyết các biến thể khác nhau của bài toán MWDS. Tuy nhiên, thuật toán HLNS cũng có một số hạn chế. Nó có thể tốn kém về mặt tính toán, đặc biệt là đối với các đồ thị lớn. Ngoài ra, việc điều chỉnh các tham số của thuật toán có thể đòi hỏi nhiều thử nghiệm.

IV. Ứng Dụng Thực Tiễn Của Thuật Toán Tìm Tập Đỉnh Thống Trị

Bài toán tập đỉnh thống trị có trọng số có nhiều ứng dụng thực tế trong nhiều lĩnh vực khác nhau. Một trong những ứng dụng quan trọng nhất là trong thiết kế mạng lưới cảm biến không dây, nơi mục tiêu là chọn một tập hợp các cảm biến sao cho mọi khu vực trong mạng đều được theo dõi và chi phí triển khai là tối thiểu. Các ứng dụng khác bao gồm lựa chọn địa điểm cho các trạm phát sóng, phân tích mạng xã hội, và lập kế hoạch mạng lưới giao thông. Việc hiểu rõ các ứng dụng này có thể giúp các nhà nghiên cứu phát triển các thuật toán hiệu quả hơn cho bài toán MWDS. Theo tài liệu gốc, "Các mạng cảm biến được hình thành để thu thập các thông tin cần thiết phục vụ cho các ứng dụng thực tiễn."

4.1. Thiết Kế Mạng Lưới Cảm Biến Không Dây Tối Ưu

Trong mạng lưới cảm biến không dây, các cảm biến thường có chi phí triển khai và bảo trì khác nhau. Bài toán MWDS có thể được sử dụng để chọn một tập hợp các cảm biến sao cho mọi khu vực trong mạng đều được theo dõi và tổng chi phí là tối thiểu. Việc giải quyết bài toán này có thể giúp giảm chi phí triển khai và bảo trì mạng, đồng thời đảm bảo rằng mạng có thể thu thập dữ liệu một cách hiệu quả. Một ví dụ cụ thể là việc triển khai các mạng lưới cảm biến để theo dõi chất lượng không khí trong các thành phố, nơi có thể sử dụng bài toán MWDS để chọn các vị trí tối ưu cho các cảm biến.

4.2. Phân Tích Mạng Xã Hội và Ảnh Hưởng Cộng Đồng

Trong mạng xã hội, bài toán MWDS có thể được sử dụng để xác định một tập hợp những người có ảnh hưởng có thể lan truyền thông tin đến mọi người trong mạng. Việc chọn những người có ảnh hưởng phù hợp có thể giúp các nhà quảng cáo và các nhà hoạch định chính sách tiếp cận đối tượng mục tiêu của họ một cách hiệu quả. Theo tài liệu gốc, thuật toán còn được áp dụng cho "ứng dụng moderator-selector để chọn người điều hành cho một nhóm hoặc một tổ chức trên một mạng lưới cho trước."

V. Kết Quả Nghiên Cứu và Đánh Giá Hiệu Năng Thuật Toán HLNS

Các kết quả thực nghiệm cho thấy thuật toán HLNS có hiệu quả trong việc giải quyết bài toán tập đỉnh thống trị có trọng số nhỏ nhất trên nhiều bộ dữ liệu chuẩn. So với các thuật toán khác, HLNS thường đạt được các giải pháp tốt hơn trong thời gian hợp lý. Tuy nhiên, hiệu suất của thuật toán có thể phụ thuộc vào các tham số cụ thể được sử dụng và đặc điểm của đồ thị đầu vào. Việc đánh giá hiệu năng của thuật toán HLNS cần được thực hiện trên nhiều bộ dữ liệu khác nhau để đảm bảo tính tổng quát. Theo tài liệu gốc, "Thực nghiệm đã chỉ ra rằng thuật toán hiệu quả hơn các thuật toán đã có trên các bộ dữ liệu thực tế BHOSLIB và DIMACS."

5.1. So Sánh Thuật Toán HLNS Với Các Phương Pháp Khác

Việc so sánh thuật toán HLNS với các phương pháp khác là rất quan trọng để đánh giá hiệu quả của nó. Các thuật toán so sánh có thể bao gồm giải thuật tham lam, giải thuật di truyền, và các phương pháp heuristics khác. Các tiêu chí so sánh có thể bao gồm chất lượng của giải pháp tìm được, thời gian tính toán, và độ ổn định của thuật toán. Các kết quả so sánh có thể giúp xác định các tình huống mà HLNS hoạt động tốt nhất và các tình huống mà các thuật toán khác có thể phù hợp hơn.

5.2. Phân Tích Các Yếu Tố Ảnh Hưởng Đến Hiệu Năng

Hiệu năng của thuật toán HLNS có thể bị ảnh hưởng bởi nhiều yếu tố khác nhau, bao gồm kích thước và cấu trúc của đồ thị đầu vào, các tham số của thuật toán, và các phương pháp heuristics được sử dụng. Việc phân tích các yếu tố này có thể giúp hiểu rõ hơn về cách thức hoạt động của thuật toán và cách tối ưu hóa hiệu suất của nó. Ví dụ, việc điều chỉnh các tham số liên quan đến quá trình phá hủy và xây dựng lại giải pháp có thể ảnh hưởng đáng kể đến chất lượng của giải pháp tìm được.

VI. Kết Luận và Hướng Phát Triển Thuật Toán Tối Ưu Tập Đỉnh

Bài toán tập đỉnh thống trị có trọng số là một bài toán quan trọng với nhiều ứng dụng thực tế. Thuật toán HLNS là một phương pháp hiệu quả để giải quyết bài toán này, nhưng vẫn còn nhiều cơ hội để cải thiện hiệu suất của nó. Các hướng phát triển trong tương lai có thể bao gồm việc kết hợp HLNS với các phương pháp heuristics khác, phát triển các chiến lược phá hủy và xây dựng lại giải pháp hiệu quả hơn, và điều chỉnh thuật toán để giải quyết các biến thể khác nhau của bài toán MWDS. Theo tài liệu gốc, "Phân tích các mạng lưới sẽ giúp con người khai thác hiệu quả chúng."

6.1. Các Hướng Nghiên Cứu Mở Rộng Tiềm Năng

Các hướng nghiên cứu mở rộng có thể bao gồm việc khám phá các phương pháp heuristics mới để hướng dẫn quá trình tìm kiếm, phát triển các kỹ thuật để giảm độ phức tạp tính toán của thuật toán, và áp dụng thuật toán HLNS cho các bài toán liên quan khác. Ngoài ra, việc nghiên cứu các ứng dụng mới của bài toán MWDS có thể giúp thúc đẩy sự phát triển của các thuật toán hiệu quả hơn.

6.2. Tối Ưu Hóa Thuật Toán Cho Dữ Liệu Lớn

Việc tối ưu hóa thuật toán HLNS cho dữ liệu lớn là một thách thức quan trọng. Các kỹ thuật có thể được sử dụng để giảm độ phức tạp tính toán của thuật toán bao gồm việc sử dụng các cấu trúc dữ liệu hiệu quả, song song hóa thuật toán, và áp dụng các phương pháp xấp xỉ. Việc phát triển các thuật toán có thể xử lý dữ liệu lớn có thể mở ra nhiều ứng dụng mới cho bài toán MWDS.

Trích đoạn nội dung tài liệu

Mở Đầu Một lượng lớn các liên kết tồn tại trong thế giới hiện nay đã kết nối hầu hết mọi thā lại với nhau, và phát triển dần về số lượng tạo ra một số lượng khổng lồ các mạng lưới. Các mạng lưới được tạo ra từ các tổ chāc xã hội được hình thành á trong hầu hết các n¢i mà con ngưßi đang sinh sống. Với một xã hội hiện đại như ngày nay, trẻ con đến trưßng tham vào các tổ chāc trong trưßng học. Ngưßi lớn đi làm và tham gia vào rất nhiều tổ chāc và mạng lưới trong xã hội như: hệ thống tổ chāc lao động, hệ thống bảo hiểm xã hội, … Ngưßi già thưßng ít tham gia vào các tổ chāc h¢n, hầu hết trong số đó là các tổ chāc về hưu trí và hội những ngưßi bạn già.

Các tổ chāc này thưßng được hình thành một cách tự nhiên từ các nhu cầu cần thiết cÿa cuộc sống, hình thành các mạng lưới với đầy đÿ kích cỡ khác nhau. Các mạng lưới được tạo thành từ dựa trên các hệ thống khổng lồ như mạng điện, mạng INTERNET, và mạng viễn thông. Các mạng lưới này được phát triển mạnh mẽ trong thßi kỳ kỷ nguyên cÿa kỹ thuật số và trí tuệ nhân tạo. Hiện nay, các mạng điện cung cấp đÿ điện cho hàng tỷ ngưßi dùng á khắp n¢i trên thế giới với kết cấu rất linh hoạt và phong phú phụ thuộc vào địa hình.

Tiếp theo, các mạng xã hội nổi tiếng như Twitter, Wechat, QQ, Facebook, với số lượng ngưßi dùng từ vài trăm triệu đến tỷ ngưßi dùng. Trên các mạng này, mọi ngưßi được sử dụng rất nhiều tiện ích như nhắn tin, trò chuyện trực tiếp, ch¢i trò ch¢i cùng nhau. Cuối cùng, các mạng viễn thông hiện nay được phÿ song hầu như toàn bộ các n¢i tập trung đông đảo con ngưßi sinh sống, cho phép hàng triệu ngưßi dùng giao tiếp với nhau trong một khoảng rộng lớn một cách linh hoạt không bị gò bó như các mạng lưới cố định. Các mạng cảm biến được hình thành để thu thập các thông tin cần thiết phục vụ cho các āng dụng thực tiễn.

Các mạng lưới cảm biến được sử dụng rất nhiều trong thực tế và trong cuộc sống vạn vật kết nối như ngày nay. Đầu tiên, các āng dụng về nhà á thông minh cần đến hàng trăm cảm biến để thu thập các thông tin về môi trưßng, sāc khỏe, các tiện ích giải trí, và các công cụ hỗ trợ. Bên cạnh đó, các āng dụng về phư¢ng tiện đi lại như ô tô, máy bay, tàu vũ trụ cần rất nhiều các cảm biến với đầy đÿ các loại kể cả tối tân nhất hiện nay. Thêm vào nữa, các āng dụng bảo vệ môi trưßng cũng cần rất nhiều các cảm biến đến có thể theo dõi chính xác tình hình môi trưßng hiện nay, giúp các nhà điều hành 13 và ngưßi có trách nhiệm, cũng như toàn bộ dân cư āng phó kịp thßi với các điều kiện môi trưßng thay đổi thất thưßng phāc tạp như ngày nay.

Cuối cùng, các āng dụng liên quan đến hàng không vũ trụ đang được quan tâm nhất với các thiết bị chÿ yếu gồm các tổ hợp, mạng lưới phāc tạp giúp con ngưßi khám phá và chinh phục vũ trụ. Hầu hết các mạng lưới được hình thành với những khái đầu không quá phāc tạp phục vụ cho những đối tượng mục tiêu bình thưßng. Sau đó, cùng với sự phát triển cÿa đßi sống và nhu cầu thực tế, các mạng này phát triển với số lượng và kích thước như khổng lồ và đa dạng và thành phần. Chẳng hạn như, mạng xã hội Facebok với khái đầu chỉ khoảng vài chục ngàn ngưßi dùng, trong đó chÿ yếu là các sinh viên đại học.

Các tiện ích bạn đầu chÿ yếu là nhắn tin và chia sẽ ảnh cá nhân qua mạng. Khoảng chục năm về sau, mạng xã hội này đã phát triển lên đến vài trăm triệu ngưßi dùng với rất nhiều tiện ích và có tới cả trăm ngàn gian hàng trên mạng xã hội nay. Cho đến bây giß, hầu hết những ngưßi dùng INTERNET hiện đại đều biết đến mạng xã hội Facebook với h¢n tỷ ngưßi dùng á khắp mọi ngưßi trên thế giới với đÿ các thành phần từ ngưßi dân bình thưßng, doanh nhân cho đến các ngưßi nổi tiếng. Phân tích các mạng lưới sẽ giúp con ngưßi khai thác hiệu quả chúng.

Việc tìm hiểu về một mạng lưới sẽ giúp con ngưßi hiểu rõ h¢n các tính chất cÿa một mạng lưới, các thành phần liên quan và sự phát triển cÿa mạng lưới đó. Từ đó, họ sẽ đưa ra các quyết định vào mạng lưới đó để thu được hiệu quả lớn nhất cho chính họ. Chẳng hạn, việc triển khai INTERNET trên một phạm vi địa lý cần tìm hiểu về sự phân bố dân cư, tính chất địa lý cÿa vùng miền, yếu tố sử dụng cÿa ngưßi dụng để có thể quyết định đặt các thiết bị á các vị trí hợp lý giúp giảm thiểu công sāc chi phí, thßi gian triển khai mạng cũng như làm giảm chi phí bảo trì mạng này. Phân tích và khai thác các mạng lưới hiệu quả luôn tạo ra các giá trị to lớn cho ngưßi sử dụng, đặc biệt trong kỷ nguyên cÿa vạn vật kết nối (IOT).

Một trong những yếu tố được quan tâm là tập các nốt ảnh hưáng đến toàn bộ mạng lưới, và bài toán được quan tâm gần đây là bài toán tìm tập đỉnh thống trị có trọng số nhỏ nhất. Phân tích mạng lưới để khai thác và phát triển mạng lưới, giúp các hệ thống nên mạnh mẽ, hoạt động tốt h¢n, nhiều tính năng h¢n, giúp ngưßi dùng và nhà quản lý mạng có thêm nhiều lợi ích. Các mạng lưới phân tích bao gồm: mạng xã hội, mạng di động, mạng cảm biến, mạng lưới tổ chāc xã hội. Việc 14 khai thác từ các mạng này chÿ yếu khai thác tăng kích thước hệ thống, kích thích ngưßi dùng tham gia vào hệ thống, kích thích ngưßi dùng sử dụng dịch vụ trên mạng, kéo dài tuổi thọ cÿa mạng, giảm thiểu chi phí vận hành và bảo trì, và quản lý hệ thống.

Phân tích mạng xã hội và các tổ chāc xã hội liên quan đến các bài toán quản lý mạng xã hội, nguồn thông tin lan truyền trên mạng xã hội, bài toán về quảng cáo trên mạng xã hội. Việc phân tích mạng xã hội, giúp cho nhà phát hành sử dụng thông tin từ mạng xã hội hiệu quả để triển khai các dịch vụ và giảm thiểu chi phí vận hành hệ thống. Ngưßi dùng sử dụng các dịch vụ như quảng cáo trên mạng xã hội, tìm kiếm bạn bè, tạo dựng hình ảnh trên mạng xã hội, mạng lại lợi ích lớn h¢n cho họ. Các tổ chāc xã hội tốt h¢n khi chọn lựa được các nhà quản lý hiệu quả phù hợp và tối ưu.

Ví dụ: ngưßi dùng mạng xã hội Youtube thưßng hay xem những quảng cáo bao cao su DUREX á trên trong các nhóm youtuber nổi tiếng, và thưßng chia sẻ nó với những ngưßi bạn cÿa họ thông qua các mạng xã hội khác như Facebook, Zalo. Bài toán tìm tập đỉnh thống trị có trọng số nhỏ nhất trên mạng lưới được áp dụng để khai thác các yếu tố về việc tìm ra tập các thành phần có khả năng chi phối toàn bộ các thành phần còn lại trong mạng. Đó là được áp dụng cho đồ thị vô hướng để tìm ra một tập đỉnh chính có tổng trọng số nhỏ nhất sao cho các đỉnh không thuộc đã chọn kề với tập đỉnh đã chọn. Việc tìm ra tập đỉnh này giúp việc phân tích thiết kế trên mạng hiệu quả h¢n, do thông thưßng các tác động lên đồ thị sẽ ảnh hưáng chÿ yếu bái tập đỉnh chính.

Tại mỗi thành viên trong tập đỉnh chính, ngưßi dùng có thể tập trung dùng chúng để quản lý chi phối, hoặc xử lý các tác vụ nặng. Điều này giúp giảm thiểu các công việc phải làm trên toàn bộ hệ thống vì chỉ cần tập trung vào một tập đỉnh chính là một bộ phận cÿa mạng. Có rất nhiều nghiên cāu āng dụng về tập đỉnh trị đã được công bố về các āng dụng liên quan đến mạng xã hội, mạng di động, và mạng cảm biến, … Tuy rằng, các nghiên cāu về tập đỉnh thống trị có trọng số nhỏ nhất rất lâu nhưng hoàn toàn có giá trị trong kỷ nguyên cÿa kết nối vạn vật với một lượng dữ liệu khổng lồ được lưu chuyển và xử lý. Trong gần 20 năm gần đây, đã có rất nhiều nghiên cāu cho bài toán này.

Do bài toán được chāng minh thuộc lớp bài toán NP-hard nên cho đến thßi điểm nay vẫn chưa có một thuật toán hiệu quả để xử lý bài toán với kết quả chính xác trong thßi gian đa thāc. Các thuật toán chính xác hiện nay có độ phāc tạp tính toán theo hàm mũ, nên chỉ mang tính lý thuyết mà chưa thể áp dụng trong thực 15 tế. Các nghiên cāu này gồm các thuật toán chính xác cho tập đỉnh thống trị cÿa Fomin, Van Rooij dựa trên thuật toán nhánh và rút gọn [8][23]. Các thuật toán khả dụng hiện nay cho bài toán này là các thuật toán metaheuristic với các phư¢ng pháp kinh điển gồm tối ưu đàn kiến, giải thuật di truyền, tối ưu bầy đàn, các thuật toán memetic, các thuật toán tìm kiếm địa phư¢ng, và thuật toán matheuristic.

Các thuật toán matheuristic có ưu điểm là đưa ra lßi giải đÿ tốt trong một thßi gian hợp lý so với các thuật toán tham lam hoặc các thuật toán ngẫu nhiên. Các công trình nghiên cāu bao gồm: áp dụng thuật toán tối ưu đàn kiến để tìm tập đỉnh thống trị [17] [19], áp dụng thuật toán di truyền để tìm các tập thống trị [17], áp dụng thuật toán bầy đàn để tìm tập đỉnh thống trị [13], áp dụng các thuật toán memetic để tìm tập đỉnh thống trị [14], áp dụng thuật toán tìm kiếm địa phư¢ng với kỹ thuật cấu hình kiểm thử dựa trên các hàm điểm tần suất [26], các nghiên cāu lên quan đến matheuristic như kết hợp các thuật toán tham lam với quy hoạch nguyên và việc kết hợp tìm kiếm tabu với quy hoạch nguyên [1] [2]. Các thuật toán bầy đàn thì dựa vào số lượng cá thể và phư¢ng pháp phát triển quần thể nên thưßng chạy khá chậm hoặc là chúng bị tăng một lượng chi phí về thßi gian do kết hợp với cả các thuật toán tìm kiếm địa phư¢ng để cải thiện kết quả. Các thuật toán matheuristic là sự kết hợp với các thuật toán metaheuristic với quy hoạch nguyên.