Một Số Thuật Toán Giải Bài Toán Phủ Đỉnh

Luận văn thạc sĩ toán học nghiên cứu một số thuật toán giải bài toán phủ đỉnh, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải pháp cải thiện thực tiễn.

• Tác giả: Phùng Dương Hoàng
• Người hướng dẫn: GS.TS Đặng Quang Á
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Giải Bài Toán Phủ Đỉnh Bằng Các Thuật Toán Heuristic
• Loại tài liệu: luận văn
• Năm xuất bản: 2014
• Địa điểm: Thái Nguyên

Tóm tắt

I. Tổng quan về bài toán phủ đỉnh và thuật toán heuristic

Bài toán phủ đỉnh là một trong những bài toán nổi bật trong lý thuyết đồ thị. Mục tiêu của bài toán này là tìm một tập hợp các đỉnh sao cho mọi cạnh trong đồ thị đều có ít nhất một đầu mút thuộc tập hợp đó. Việc giải quyết bài toán này thường gặp khó khăn do tính chất NP-đầy đủ của nó. Các thuật toán heuristic đã được phát triển để tìm ra các giải pháp gần đúng trong thời gian hợp lý.

1.1. Khái niệm về bài toán phủ đỉnh

Bài toán phủ đỉnh được định nghĩa là tìm một tập con của các đỉnh sao cho mỗi cạnh trong đồ thị đều có ít nhất một đầu mút thuộc tập con đó. Đây là một bài toán NP-đầy đủ, có nghĩa là không có thuật toán nào có thể giải quyết nó trong thời gian đa thức cho mọi trường hợp.

1.2. Tại sao cần sử dụng thuật toán heuristic

Do độ phức tạp của bài toán phủ đỉnh, việc tìm kiếm giải pháp chính xác thường không khả thi. Các thuật toán heuristic cung cấp các phương pháp tìm kiếm giải pháp gần đúng, giúp tiết kiệm thời gian và tài nguyên tính toán.

II. Các thách thức trong việc giải bài toán phủ đỉnh

Giải bài toán phủ đỉnh không chỉ đơn thuần là tìm ra một tập hợp các đỉnh mà còn phải đối mặt với nhiều thách thức. Các thách thức này bao gồm việc xác định kích thước tối ưu của tập hợp, cũng như đảm bảo rằng mọi cạnh đều được bao phủ. Các phương pháp heuristic có thể giúp giảm thiểu độ phức tạp của bài toán.

2.1. Độ phức tạp tính toán

Bài toán phủ đỉnh thuộc lớp NP-đầy đủ, điều này có nghĩa là không có thuật toán nào có thể giải quyết nó trong thời gian đa thức cho mọi trường hợp. Điều này tạo ra thách thức lớn trong việc tìm kiếm giải pháp tối ưu.

2.2. Tìm kiếm giải pháp gần đúng

Việc tìm kiếm giải pháp gần đúng là một trong những thách thức lớn nhất. Các thuật toán heuristic như thuật toán tham lam có thể giúp tìm ra các giải pháp chấp nhận được trong thời gian ngắn hơn.

III. Phương pháp giải bài toán phủ đỉnh bằng thuật toán heuristic

Các phương pháp heuristic đã được áp dụng để giải quyết bài toán phủ đỉnh. Những phương pháp này thường dựa trên các nguyên lý như nguyên lý tham lam và nguyên lý vét cạn thông minh. Chúng giúp tìm ra các giải pháp gần đúng một cách hiệu quả.

3.1. Nguyên lý tham lam trong thuật toán

Nguyên lý tham lam là một trong những phương pháp phổ biến trong các thuật toán heuristic. Nó cho phép lựa chọn giải pháp tốt nhất tại mỗi bước mà không cần xem xét lại các lựa chọn trước đó.

3.2. Các thuật toán heuristic khác

Ngoài nguyên lý tham lam, còn có nhiều phương pháp khác như thuật toán di truyền và thuật toán mô phỏng nhiệt. Những phương pháp này cũng đã được áp dụng để giải bài toán phủ đỉnh với hiệu quả cao.

IV. Ứng dụng thực tiễn của bài toán phủ đỉnh

Bài toán phủ đỉnh có nhiều ứng dụng thực tiễn trong các lĩnh vực như mạng máy tính, quy hoạch đô thị và thiết kế mạch điện. Việc áp dụng các thuật toán heuristic giúp giải quyết các bài toán này một cách hiệu quả.

4.1. Ứng dụng trong mạng máy tính

Trong mạng máy tính, bài toán phủ đỉnh có thể được sử dụng để tối ưu hóa việc kết nối các nút trong mạng, đảm bảo rằng mọi kết nối đều được bao phủ.

4.2. Ứng dụng trong quy hoạch đô thị

Trong quy hoạch đô thị, bài toán phủ đỉnh giúp xác định các vị trí tối ưu cho các cơ sở hạ tầng, đảm bảo rằng mọi khu vực đều được phục vụ.

V. Kết luận và tương lai của nghiên cứu về bài toán phủ đỉnh

Nghiên cứu về bài toán phủ đỉnh và các thuật toán heuristic vẫn đang tiếp tục phát triển. Tương lai của nghiên cứu này hứa hẹn sẽ mang lại nhiều giải pháp mới và hiệu quả hơn cho các bài toán phức tạp trong thực tiễn.

5.1. Tương lai của các thuật toán heuristic

Các thuật toán heuristic sẽ tiếp tục được cải tiến và phát triển, giúp giải quyết các bài toán phức tạp hơn trong tương lai.

5.2. Nghiên cứu sâu hơn về bài toán phủ đỉnh

Cần có nhiều nghiên cứu hơn về các phương pháp giải quyết bài toán phủ đỉnh, đặc biệt là trong bối cảnh dữ liệu lớn và các ứng dụng thực tiễn.

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

ĐẠI HỌC THÁI NGUYÊN THÔNG PHÙNG DƢƠNG HOÀNG MỘT SỐ THUẬT TOÁN GIẢI BÀI TOÁN PHỦ ĐỈNH L Thái Nguyên - 20 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ i LỜI CAM ĐOAN Tôi xin cam đoan rằng, đây là công trình nghiên cứu của tôi trong đó có sự giúp đỡ tận tình của thầy giáo hướng dẫn và các thầy cô tại Viện CNTT, các thầy, cô giáo Trường Đại học Công nghệ Thông tin và Truyền thông, sự hỗ trợ của các đồng nghi. Các nội dung nghiên cứu và kết quả trong đề tài này là hoàn toàn trung thực. Trong luận văn, tôi có tham khảo đến một số tài liệu của một số tác giả đã được liệt kê tại phần Tài liệu tham khảo ở cuối luận văn. Thái Nguyên, tháng 6 năm 2014 Tác giả Phùng Dƣơng Hoàng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ ii LỜI CẢM ƠN Để hoàn thành chương trình cao học và viết luận văn này, tôi đã nhận được sự hướng dẫn, giúp đỡ và góp ý nhiệt tình của quý thầy cô trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên.

Trước hết, tôi xin chân thành cảm ơn đến quý thầy cô trường Đại học Công nghệ thông tin và truyền thông - Đại học Thái Nguyên, các thầy cô Viện CNTT, đặc biệt là những thầy cô đã tận tình dạy bảo cho tôi trong suốt thời gian học tập tại trường. Tôi xin gửi lời biết ơn sâu sắc đến GS.TS Đặng Quang Á đã dành rất nhiều thời gian và tâm huyết hướng dẫn nghiên cứu và giúp tôi hoàn thành luận văn tốt nghiệp. Nhân đây, tôi xin chân thành cảm ơn Ban giám hiệu trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên đã tạo rất nhiều điều kiện để tôi học tập và hoàn thành tốt khóa học. Mặc dù tôi đã có nhiều cố gắng hoàn thiện luận văn bằng tất cả sự nhiệt tình và năng lực của mình, tuy nhiên không thể tránh khỏi những thiếu sót, tôi rất mong nhận được những đóng góp quí báu của quý thầy cô và các bạn.

Lời cảm ơn sau cùng tôi xin dành cho gia đình và những người bạn đã hết lòng quan tâm và tạo điều kiện tốt nhất để tôi hoàn thành luận văn tốt nghiệp này! Tôi xin chân thành cảm ơn! Thái Nguyên, tháng 6 năm 2014 Học viên thực hiện Phùng Dƣơng Hoàng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ iii MỤC LỤC Trang Trang bìa phụ Lời cam đoan. ii Mục lục. iii Danh mục các hình. 1 Chƣơng 1: CÁC PHƢƠNG PHÁP HEURISTIC GIẢI CÁC BÀI TOÁN NP-C.

Giới thiệu chung về bài toán NP-C. Lớp bài toán P. Lớp bài toán NP. Lớp bài toán NP-đầy đủ (NP-Complete).

Một số bài toán NP-C trong lý thuyết đồ thị, trong quy hoạch nguyên. Khái niệm chung về các phương pháp Heuristic. Một số phương pháp Heuristic giải các bài toán NP-C. Thuật toán tham lam.

Giới thiệu chung. Thuật toán cho phương pháp tham lam. Giới thiệu về mạng nơ-ron. Lịch sử phát triển.

Mô hình mạng nơ-ron nhân tạo. Phạm vi ứng dụng của mạng nơ-ron. Mạng nơ-ron Hopfield. 18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ iv Chƣơng 2: BÀI TOÁN PHỦ ĐỈNH VÀ MỘT SỐ THUẬT TOÁN GIẢI BÀI TOÁN PHỦ ĐỈNH.

Giới thiệu bài toán phủ đỉnh. Một số thuật toán giải bài toán phủ đỉnh. Thuật toán tham. Thuật toán mới của Dharwadker.

32 Chƣơng 3: MÔ PHỎNG SỐ. Lựa chọn phương pháp sử dụng. Xây dựng chương trình. Phân tích và đánh giá kết quả.

58 TÀI LIỆU THAM KHẢO. 59 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ v DANH MỤC CÁC HÌNH Trang Hình 1.1: Mối quan hệ giữa lớp P và NP. Hình bài toán về tập độc lập.3: Mô hình mạng Hopfield .4: Lời giải tốt và xấu của bài toán sánh cặp có trọng .1: Thí dụ về phủ đỉnh .2: Thí dụ về bài toán phủ đỉnh theo phương pháp tham (n=7) .3: Thí dụ về bài toán phủ đỉnh theo phương pháp tham (n=13) .4: Thí dụ về bài toán phủ đỉnh theo Dharwadker (n=12).1: Chương trình tìm phủ đỉnh của một đồ thị n=12 .2: Phủ đỉnh của đồ thị n=4 .3: Phủ đỉnh của đồ thị n=6 .4: Phủ đỉnh của đồ thị n=6 .5: Phủ đỉnh của đồ thị n=7 .6: Phủ đỉnh của đồ thị n=8 .7: Phủ đỉnh của đồ thị n=8 .8: Phủ đỉnh của đồ thị n=10 .9: Phủ đỉnh của đồ thị n=11. 57 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ 1 LỜI NÓI ĐẦU Trong thực tế có rất nhiều bài toán phức tạp thuộc lớp bài toán NP- C và bài toán tối ưu có ràng buộc, cũng có nhiều công trình nghiên cứu để giải quyết các bài toán đó, trong đó có nhiều bài toán của lý thuyết đồ thị như: bài toán phủ đỉnh, bài toán tập độc lập, bài toán tô mầu đồ thị, bài toán người bán hàng rong, bài toán phẳng hóa đồ thị,.

nhiều bài toán quy hoạch nguyên như: bài toán ba lô, bài toán đóng thùng,. Vì các bài toán loại NP-C có độ phức tạp hàm mũ nên khi dữ liệu đầu vào lớn nên nói chung người ta không thể thu được lời giải đúng của bài toán và buộc phải tìm lời giải gần đúng. Có nhiều thuật toán heuristic với thời gian đa thức để tìm nghiệm xấp xỉ của các bài toán NP-C. Những năm gần đây trên thế giới đã đưa ra một số phương pháp và thuật giải nhằm giải quyết các bài toán tối ưu thuộc lớp NP-C và được áp dụng rộng rãi trong lĩnh vực Công nghệ thông tin.

Việc nghiên cứu và áp dụng những thành tựu mới vào việc phân tích, thiết kế, giải quyết một số bài toán là một trong những vấn đề nóng đang rất được quan tâm. Nhận thức được vấn đề đó và có sự gợi ý, định hướng của GS.TS Đặng Quang Á em đã mạnh dạn nghiên cứu đề tài: "Một số thuật toán giải bài toán phủ đỉnh". Nội dung cơ bản của luận văn gồm có ba chương: Chương một giới thiệu chung về bài toán NP-C; một số bài toán NP-C trong lý thuyết đồ thị, trong quy hoạch nguyên; giới thiệu một số phương pháp Heuristic giải các bài toán NP-C. Chương hai giới thiệu bài toán phủ đỉnh và một số phương pháp giải bài toán phủ đỉnh.

Chương ba ứng dụng. Qua luận văn này em xin chân thành cảm ơn: GS.TS Đặng Quang Á - Viện Công nghệ Thông tin đã tận tình giúp đỡ, động viên, định hướng, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ 2 hướng dẫn em nghiên cứu và hoàn thành luận văn. Em xin cảm ơn các thầy cô giáo trong viện Công nghệ thông tin, các thầy cô giáo Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên, đã giảng dạy và giúp đỡ em trong hai năm học vừa qua, cảm ơn sự giúp đỡ nhiệt tình của các bạn đồng nghiệp. Xin chân thành cảm ơn! Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ 3 Chƣơng 1 CÁC PHƢƠNG PHÁP HEURISTIC GIẢI CÁC BÀI TOÁN NP-C 1.

Giới thiệu chung về bài toán NP-C 1. Lớp bài toán P Định nghĩa 1.1: Ta gọi lớp P là lớp những bài toán quyết định giải được bằng máy tính Turing đơn định trong thời gian đa thức. Một ngôn ngữ L thuộc lớp P nếu có một hàm đa thức T(n) sao cho L=L(M) với một máy Turing đơn định nào đó có độ phức tạp thời gian T(n). Như vậy, lớp P gần như tương ứng với lớp các bài toán quyết định giải được trong thời gian đa thức, về mặt lý thuyết, có thể xem là lớp các bài toán dễ.

Lớp bài toán NP Ta gọi lớp NP là lớp các bài toán quyết định có thể giải được bằng máy tính Turing không đơn định trong khoảng thời gian đa thức. Một cách không hình thức, chúng ta nói một ngôn ngữ L thuộc lớp NP nếu tồn tại một máy tính Turing không đơn định M và một độ phức tạp thời gian T(n) sao cho L = L(M) và khi M được cho một nguyên liệu có độ dài n thì nó sẽ kiểm nhận sau không quá T(n) bước chuyển. Để nói về mối quan hệ giữa lớp P và lớp NP ta thấy do máy tính Turing đơn định là trường hợp đặc biệt của máy tính Turing không đơn định nên các bài toán thuộc lớp P sẽ thuộc lớp NP. Tuy P NP là rất hiển nhiên song ta vẫn chưa biết P = NP hay không, nhưng hầu hết các nhà nghiên cứu đều tin rằng P NP.

Từ đó ta có mô hình mô phỏng sau: NP P Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www. Mối quan hệ giữa lớp P và NP 1. Lớp bài toán NP-đầy đủ (NP-Complete) Định nghĩa 1.2: Ta nói L là bài toán thuộc loại NP-complete nếu các khẳng định sau đều đúng: 1) L thuộc NP. 2) Với mọi ngôn ngữ L' NP có một phép thu thời gian đa thức L' về L.

Bài toán NP-complete đầu tiên chúng ta sẽ xét là bài toán thỏa SAT (Boolean satisfiability). Chúng ta sẽ chứng tỏ rằng ngôn ngữ của mọi máy Turing không đơn định (NTM) thời gian đa thức đều có một phép thu thời gian đa thức về SAT. Khi đã có được một số bài toán thuộc NP-complete (NP-C) chúng ta có thể chứng minh một bài toán mới thuộc NP-C bằng cách thu một bài toán đã biết là NP-C về bài toán đó nhờ một phép thu thời gian đa thức [1]. Định lý dưới đây cho biết vì sao một phép thu như thế chứng minh được bài toán đích là NP-C.1: Nếu bài toán P1 là NP-C, P2 là NP và có một phép thu thời gian đa thức từ P1 về P2 thì P2 cũng là NP-C.

Chứng minh: Ta cần chứng tỏ rằng mỗi ngôn ngữ L thuộc NP đều thu được P2 trong thời gian đa thức. Khi đó theo định nghĩa P2 sẽ thuộc NP-C. Thật vậy vì P1 là NP-C nên có một phép thu đa thức L về P1. Giả sử thời gian của phép thu này là P(n).

Vì thế một chuỗi W L có chiều dài n được biến đổi thành một chuỗi x P1 có chiều dài tối đa là P(n). Ta cũng biết rằng có một phép thu đa thức từ P1 về P2. Giả sử thời gian của phép thu này là q(m). Thế thì phép thu này biến đổi chuỗi x P1 về một chuỗi y nào đó thuộc P2 với thời gian tối đa là q(p(n)).

Vì thế phép biến đổi W L về y P2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.