Tài liệu Phương pháp lai mạng nơ ron - giải thuật di truyền giải bài toán np-c và ứng dụng

  • Số trang: 66 |
  • Loại file: PDF |
  • Lượt xem: 108 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 27125 tài liệu

Mô tả:

ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN LÊ THANH BÌNH PHƯƠNG PHÁP LAI MẠNG NƠ RON GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN NP-C VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH THÁI NGUYÊN 2010 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN LÊ THANH BÌNH PHƯƠNG PHÁP LAI MẠNG NƠ RON GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN NP-C VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS- TS. ĐẶNG QUANG Á THÁI NGUYÊN 2010 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -i- MỤC LỤC TRANG PHỤ BÌA LỜI CAM ĐOAN MỤC LỤC ............................................................................................................... i DANH MỤC CÁC BẢNG…………………………………………….…...………iii DANH MỤC CÁC HÌNH ...................................................................................... iv LỜI NÓI ĐẦU………………………………………………………………………1 CHƢƠNG I: GIỚI THIỆU SƠ LƢỢC VỀ CÁC BÀI TOÁN NP-C......................... 3 1.1. Giới thiệu chung về bài toán NP-C ................................................................ 3 1.2. Cách tiếp cận giải bài toán NP-C ................................................................... 4 1.2.1. Một số khái niệm ................................................................................... 4 1.2.2. Giới thiệu một số thuật toán xấp xỉ giải bài toán NP-C .......................... 5 1.2.3. Các thuật toán gần đúng ........................................................................ 6 1.2.4. Tô mầu đồ thị với bài toán 4 mầu ........................................................ 13 1.2.5. Bài toán phẳng hóa đồ thị .................................................................... 15 1.3. Kết luận ......................................................................................................... 17 CHƢƠNG II : MẠNG NƠ RON VÀ THUẬT GIẢI DI TRUYỀN GIẢI BÀI TOÁN TỐI ƢU ................................................................................................................. 18 2.1. Giới thiệu về mạng nơ-ron ........................................................................... 18 2.1.1. Lịch sử phát triển................................................................................. 18 2.1.2. Mô hình mạng nơ-ron nhân tạo............................................................ 19 2.2. Phạm vi ứng dụng của mạng nơ-ron ........................................................... 23 2.2.1. Những bài toán thích hợp .................................................................... 23 2.2.2. Các lĩnh vực ứng dụng mạng nơ-ron .................................................... 23 2.2.3. Ƣu và nhƣợc điểm của mạng nơ-ron .................................................... 24 2.3. Mạng Hopfield .............................................................................................. 24 2.3.1. Mạng Hopfield rời rạc ......................................................................... 26 2.3.2 Mạng Hopfield liên tục ......................................................................... 27 2.4. Giới thiệu thuật giải di truyền ...................................................................... 28 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn - ii - 2.4.1. Các tính chất đặc thù của thuật giải di truyền ....................................... 29 2.4.2. Các bƣớc quan trọng trong việc áp dụng thuật giải di truyền ............... 29 2.4.3. Ví dụ minh họa .................................................................................... 31 2.4.4. Các phƣơng thức biến hóa của giải thuật di truyền .............................. 34 2.4.5. Các giải thuật di truyền lai ................................................................... 38 2.5. Giải thuật di truyền với bài toán tối ƣu ....................................................... 39 2.5.1. Ánh xạ hàm mục tiêu sang hàm phù hợp ............................................. 39 2.5.2. Tỷ lệ hoá giá trị phù hợp...................................................................... 40 2.5.3. Mã hoá tham biến nhờ véctơ nhị phân ................................................. 41 2.5.4. Bài toán tối ƣu ràng buộc..................................................................... 41 2.6. Mạng nơ ron Hopfield - giải thuật di truyền giải bài toán tối ƣu. .............. 42 2.7. Kết luận ......................................................................................................... 44 CHƢƠNG 3: ỨNG DỤNG THUẬT GIẢI DI TRUYỀN GIẢI BÀI TOÁN PHÂN CÔNG NHIỆM VỤ ............................................................................................... 45 3.1. Giới thiệu ...................................................................................................... 45 3.2. Đị nh nghĩa bài toán ...................................................................................... 47 3.3. Ứng dụng Thuật giải di truyền vào bài toán ............................................... 48 3.3.1. Mã hóa: ............................................................................................... 49 3.3.2. Toán tử chọn cá thể ............................................................................. 50 3.3.3. Toán tử lai ghép và toán tử đột biến..................................................... 51 3.3.4. Sƣ̉a chƣ̃a giải pháp .............................................................................. 52 3.3.5. Tìm kiếm cục bộ .................................................................................. 54 3.4. Thí nghiệm và nhận xét ................................................................................ 55 3.4.1. Thí nghiệm .......................................................................................... 55 3.4.2. Nhận xét .............................................................................................. 56 3.5. Kết luận ......................................................................................................... 57 KẾT LUẬN……………………..………………………………………………….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.lrc-tnu.edu.vn - iii - DANH MỤC BẢNG Bảng 3.1: Các ứng dụng toán tử lai ghép thực hiện trong GGA. 52 Bảng 3.2: Các ứng dụng toán tử đột biến thực hiện trong GGA. 52 Bảng 3.3: Ví dụ về các sở thích của sinh viên 53 Bảng 3.4: Ví dụ về các sở thích của sinh viên 54 Bảng 3.5: Số sinh viên trong nhóm thứ i trong những giải pháp đƣợc tìm thấy bởi GGA. Bảng 3.6: So sánh các kết quả thu đƣợc bằng GGA và thuật toán tham lam GRAH. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 56 57 http://www.lrc-tnu.edu.vn - iv - DANH MỤC CÁC HÌNH Hình 1.1: Bản dồ 9 nƣớc chƣa tô màu. 14 Hình 1.2: Bản dồ 9 nƣớc tô bởi 4 mầu. 14 Hình 1.3: Đồ thị 6 cạnh. 16 Hình 1.4: Hình (a) và (b) là đồ thị phẳng. 16 Hình 1.5: Đồ thị trên một hàng đơn. 17 Hình 2.1: Mô hình nơ ron sinh học. 19 Hình 2.2 : Mô hình một Nơ-ron . 21 Hình 2.3: Mô hình mạng Hopfield. 25 Hình 2.4: Lƣu đồ mô tả cấu trúc của giải thuật di truyền. 31 Hình 2.5: Lƣu đồ thuật toán của quá trình chọn lọc. 35 Hình 2.6: Lƣu đồ thuật toán quá trình lai ghép. 36 Hình 2.7: Lƣu đồ thuật toán của quá trình đột biến . 37 Hình 2.8: Lƣu đồ thuật toán của giải thuật lai. 42 Hình 2.9: Ví dụ về biểu diễn nơ ron của bài toán với N = 4. 44 Hình 3.1: Ví dụ về sở thích của các sinh viên trong 5 nhóm. 55 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -0- Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.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 đó. Ví dụ nhƣ: Bài toán tìm đƣờng đi ngắn nhất, bài toán tô màu bản đồ, bài toán vận tải... Xong các giải thuật đƣa ra thƣờng phức tạp mà chƣa có thuật toán đơn giản và hợp lý. Những năm gần đây trên thế giới đã đƣa ra phƣơng pháp lại mạng Nơ ron Hopfield và thuật giải di truyển 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ế, phân công nhiệm vụ 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 PGS .TS Đặng Quang Á em đã mạnh dạn nghiên cứu đề tài " Phương pháp lai mạng nơ ron - giải thuật di truyền giải bài toán NP-C và ứng dụng". 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 sơ lƣợc về một số bài toán NP-C, cách tiếp cận giải các bài toán NP-C nhƣ: bài toán tô mầu đồ thị, bài toán phẳng hóa đồ thị, bài toán chọn đồng tiền…, trình bầy các cách tiếp cận tới việc giải quyết các bài toán nêu trên. Chƣơng hai giới thiệu sơ lƣợc về mạng nơ ron, mạng nơ ron Hopfield, giải thuật di truyền. Đặc biệt trình bầy phƣơng pháp lai mạng Hopfield và giải thuật di truyền giải bài toán tối ƣu. Chƣơng ba ứng dụng giải thuật di truyền giải bài toán phân lịch thực hành tại các trƣờng Đại học. Đây là bài toán có tính ứng dụng thực tế cao trong nhiều lĩnh vực nhƣ phân công nhiệm vụ trong các đơn vị, xắp sếp lịch biểu... Bài toán thuộc lớp NP-C. Vì vậy, ứng dụng giải thuật di truyền trong Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -2- bài toán phân công nhiệm vụ trong hệ thống tính toán hỗn tạp sẽ hứa hẹn là một gải pháp khả thi góp phần nâng cao hiệu quả trong công việc phân công, điều hành của con ngƣời. Qua luận văn này em xin chân thành cảm ơn: PGS .TS Đặng Quang Á Viện Công nghệ thông tin đã tận tình giúp đỡ, động viên, định hƣớng, 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 khoa Công nghệ thông tin ĐH 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! Thái Nguyên, tháng 11 năm 2010 Ngƣời viết luận văn Lê Thanh Bình Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -3- CHƢƠNG I GIỚI THIỆU SƠ LƢỢC VỀ CÁC BÀI TOÁN NP-C 1.1. Giới thiệu chung về bài toán NP-C Quá trình khám phá các bài toán thuộc loại NP-C cho ta biết rằng có rất ít cơ hội phát triển đƣợc một thuật toán hiệu quả để giải nó. Điều đó khuyến khích ta tìm kiếm các heuristic, các lời giải từng phần, các xấp xỉ và những cách khác nhằm tránh giải trực diện bài toán. Mỗi lần đƣa thêm một bài toán vào danh sách các bài toán NP-C chúng ta lại củng cố thêm ý tƣởng rằng tất cả mọi bài toán NP-C đều đòi hỏi thời gian mũ. Định nghĩa 1.1: 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. Định lý 1.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. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -4- 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 mất thời gian tối đa là p(n) + q(p(n)). đây cũng là một đa thức. Nhƣ vậy, ta kết luận rằng L có thể thu về P2 trong thời gian đa thức. Định lý 1.2. Nếu có một bài toán nào đó là NP-C mà lại thuộc lớp P thì ta có P = NP. Chứng minh: Giả sử có bài toán Q ∈ NP-C và Q ∈ P. Thế thì mọi ngôn ngữ L trong NP đều thu đƣợc về Q trong thời gian đa thức. Nếu Q ∈ P thì L ∈ P. Nhƣ vậy NP ∈ P. Kết hợp với điều hiển nhiên là P ∈ NP ta đƣợc P = NP. Nhận xét: Chúng ta vẫn tin tƣởng rằng nhiều bài toán thuộc NP nhƣng không thuộc P nên chúng ta sẽ xem việc chứng minh một bài toán là NP-C có giá trị ngang với việc chứng minh rằng nó không thể giải đƣợc trong thời gian đa thức, và vì thế không có lời giải đúng nào bằng máy tính (và ta sẽ chỉ đi tìm lời giải gần đúng). 1.2. Cách tiếp cận giải bài toán NP-C 1.2.1. Một số khái niệm Nhƣ đã trình bầy ở phần trên việc tìm nghiệm của các bài toán NP-C với kích cỡ đầu vào n tƣơng đối lớn là rất khó khăn, thƣờng là không khả thi vì độ phức tạp có thể nói là hàm mũ. Đây là những bài toán nan giải hay còn gọi là Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -5- bất trị. Vì thế thay cho việc tìm lời giải đúng (lời giải tối ƣu) ngƣời ta phải tìm nghiệm gần đúng (lời giải gần tối ƣu) mà có thể chấp nhận đƣợc. - Giải thuật xấp xỉ: Xét trƣờng hợp dữ kiện I của bài toán tối ƣu P. Gọi F*(I) là giá trị của lời giải tối ƣu đối với I. Giải thuật G đƣợc gọi là giải thuật xấp xỉ cho bài toán P nếu nó luôn tạo ra một lời giải khả thi (feasible solution) mà giá trị 𝐹 (I) của lời giải này gần với F*(I) đối với mọi dữ liệu I của bài toán P. - Giải thuật xấp xỉ tuyệt đối: Giải thuật G đƣợc gọi là giải thuật xấp xỉ tuyệt đối cho bài toán P ↔ với mọi trƣờng hợp I của P tồn tại hằng số K |F*(I) - 𝐹 (I)| ≤ K ở đây 𝐹 (I) là giá trị của lời giải do G tạo ra đối với dữ kiện I. - Giải thuật f(n)-xấp xỉ: Giải thuật G đƣợc gọi là giải thuật f(n)-xấp xỉ cho bài toán P ↔ với mọi dữ kiện I của bài toán P thì |F ∗ I − 𝐹 (I)| 𝐹 (I) ≤𝑓 𝑛 , với n là kích thƣớc của I. - Giải thuật 𝜀 - xấp xỉ là giải thuật f(n)-xấp xỉ nếu f(n) ≤ 𝜀. 1.2.2. Giới thiệu một số thuật toán xấp xỉ giải bài toán NP-C a. Bài toán phủ đỉnh bé nhất (thuộc NP-C) Input: Đồ thị vô hƣớng G = (V,E). Output: Phủ đỉnh bé nhất. Thuật toán gần tối ƣu: Procedure ApproxVertexCover C := Ø {C là tập phủ đỉnh gần tối ƣu} E := Tập các cạnh của G While E ≠ Ø do Chọn (u, v) là một cạnh bất kỳ C := C U {u, v} {kết nạp 2 đỉnh u, v vào phủ đỉnh C} Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -6- Loại bỏ khỏi E cạnh uv và mọi cạnh liên thuộc với u hoặc v End do Return(C) b. Giải thuật tham lam giải các bài toán tối ưu hóa thuộc loại NP-C Giải thuật tham lam là một heuristic. GrA (Greedy Algorithm) không phải luôn luôn cho lời giải tối ƣu. Thƣờng nó chỉ cho lời giải gần tối ƣu. Khi nó cho lời giải tối ƣu thì việc chứng minh tính đúng đắn của thuật toán cũng không đơn giản. Để mô tả chính xác GrA cần mô tả chính xác môi trƣờng trong đó các bài toán tối ƣu đặt ra. Trong các bài toán tối ƣu trong ngữ cảnh GrA ngƣời ta có: - Tập (danh sách) các ứng viên, thí dụ, các nút, các cạnh trong đồ thị. - Tập các ứng viên đã sử dụng. - Một cách để kiểm tra liệu một tập các ứng viên đã cho có lời giải (không nhất thiết là tối ƣu) hay không? - Một hàm lựa chọn (selection function) để chọn các ứng viên chƣa đƣợc sử dụng. - Hàm mục tiêu gán giá trị cho các lời giải. 1.2.3. Các thuật toán gần đúng a. Heuristic đối với bài toán phủ đỉnh Bài toán: Cho đồ thị G = (V,E). Tìm tập đỉnh C nhỏ nhất phủ G theo nghĩa nếu cạnh uv ∈ E ⇒ u ∈ C hoặc v ∈ C. Thuật toán tham lam: Input: Đồ thị G = (V,E). Output: Phủ C của G gần với phủ nhỏ nhất. begin C := Ø; Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -7- while E ≠ Ø do Chọn trong V đỉnh có bậc cao nhất, loại nó ra khỏi G và bổ sung vào C. end; Vì mục đích của ta là phủ tất cả các cạnh của G bởi số ít đỉnh nhất nên chiến lƣợc chọn trên mỗi bƣớc một đỉnh phủ đƣợc nhiều cạnh nhất là hoàn toàn chấp nhận đƣợc. Tất nhiên vì bài toán là NP-C nên không hy vọng là thuật giải này hiệu quả để đạt đƣợc tập phủ đỉnh bé nhất. Câu hỏi là tập đỉnh tìm đƣợc gần với tập đỉnh tối ƣu đến mức nào? áp dụng giải thuật trên cho đồ thị sau: Đầu tiên chon một trong các đỉnh a1, a2 hoặc a3 có bậc bằng 5. Giả sử ta chọn a1, a2 rồi a3. Cuối cùng là c1, c2, c3, c4 và c5. Nhƣ vậy phủ đỉnh gồm 8 đỉnh. Nhƣng phủ đỉnh tối ƣu chỉ gồm 5 đỉnh là {b1, b2, b3, b4, b5} nếu mở rộng thí dụ này và xét đồ thị với n đỉnh loại a, n +2 đỉnh loại b và n +2 đỉnh loại c. Theo giải thuật 1 ta tìm đƣợc phủ gồm 2n + 2 đỉnh, nhƣng phủ tối ƣu chỉ gồm n + 2 đỉnh. Vì n không giới nội nên sai số có thể đạt gần tới 100%. Phải chăng đây là phƣơng pháp xấu nhất của giải thuật tham, hay có thể có sai số lớn hơn? Xét đồ thị: Đầu tiên chọn a7 với deg(a7) = 5 lớn nhất. Sau khi loại a7 thì a6 có bậc lớn nhất (bậc 4) rồi a5 (bậc 3),.. Trên mỗi bƣớc trong số các đỉnh có bậc lớn nhất có một đỉnh loại a, sau đó đƣợc loại bỏ. Cuối cùng phủ đỉnh đƣợc bổ sung các đỉnh loại c. Kết quả là ta đƣợc phủ đỉnh của G gồm 13 đỉnh, trong khi phủ tối ƣu chỉ gồm 6 đỉnh {b1, b2, b3, b4, b5, b6}. Nhƣ vậy sai số vƣợt quá 100%. Để tổng quát hóa phản ví dụ trên đầu tiên ta cần hiểu cấu trúc của nó. Có thể xem nó nhƣ 6 cạnh cibi (i = 1, 6), đƣợc bổ sung thêm các đỉnh loại a một cách thích hợp. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -8- Đầu tiên 6 cạnh loại b đƣợc phân thành 3 cặp và các đỉnh của mỗi cặp đƣợc nối với một đỉnh loại a. Sau đó các đỉnh loại b đƣợc chia thành hai bộ ba và tất cả các đỉnh của mỗi bộ ba nối với một đỉnh a mới. Cũng làm nhƣ vậy với mỗi bộ bốn, bộ năm.. * Thuật toán input và output nhƣ thuật toán 1. begin c:=Ø ; while E ≠ Ø do Chọn trong E cạnh bất kỳ (u, v), rồi loại bỏ các đỉnh u, v từ G và bổ sung nó vào C end; Định nghĩa 1.2. Giả sử A là bài toán tối ƣu với hàm giá trị c là nguyên dƣơng, A là thuật toán cho giá trị fA(I) đối với dữ kiện I, lời giải tối ƣu là 𝐹 (I). Khi đó thuật toán A đƣợc gọi là thuật toán 𝜖-xấp xỉ đối với bài toán A nếu ∃ 𝜖 ≥ 0 sao cho 𝑐 𝑓𝐴 𝐼 − 𝑐(𝐹 I ) ≤𝜖 𝑐𝐹 (I) ∀𝐼 Thí dụ: Thuật toán 2 là thuật toán 1-xấp xỉ, thuật toán 1 không phải là 𝜖 xấp xỉ ∀𝜖 > 0, vì sai số tƣơng đối của nó đối với các bài toán riêng biệt có thể lớn hơn hằng số bất kỳ. Để mô tả trƣờng hợp xấu nhất của thuật toán đôi khi ngƣời ta lấy 𝜖 = 𝜖(n). Thí dụ nếu n là số đỉnh trong bài toán phủ đỉnh ngƣời ta chỉ ra rằng thuật toán 1 là lnn-xấp xỉ. Có nghĩa là với mọi đồ thị G với n đỉnh thuật toán cho tập phủ C thỏa mãn 𝐶 − |𝐶 | |𝐶 | ≤ ln 𝑛, trong đó 𝐶 là phủ tối ƣu. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -9- b. Bài toán TSP Sử dụng các ý tƣởng của mục trƣớc vào bài toán này. Mục đích: xây dựng thuật toán hiệu quả cho kết quả gần đúng. Xét ma trận cỡ n x n các khoảng cách [dij ], dij > 0. Nhƣ thƣờng lệ ta giả thiết dij = dji và dii = 0. Ta nói ma trận (dij) thỏa mãn bất đẳng thức tam giác nếu dij + djk ≥ dik ∀1≤i, j, k ≤ n. Bất đẳng thức này thỏa mãn nếu dij là khoảng cách thông thƣờng giữa 2 điểm (xi, yi) và (xj , yj): dij = 𝑥𝑖 − 𝑥𝑗 2 + 𝑑𝑖 − 𝑑𝑗 2 Có thể có các ma trận (dij) khác thỏa mãn bất đằng thức tam giác. Bài toán: Hãy tìm cách nhận số tiền S đã cho dùng ít tờ tiền nhất với mệnh giá khác nhau. c. Thuật toán tham giải bài toán chọn đồng tiền input: Tổng số tiền S, tập các mệnh giá M = {m1,m2, ...,mn}. + Sắp xếp các mệnh giá theo thứ tự giảm dần. Giả sử đó là m1 > m2 > ... > mn. + Nếu mệnh giá bé nhất mn > S thì bài toán không có lời giải. Thuật toán kết thúc. Nếu khác (tức là mn ≤ S) thì chọn các đồng tiền theo thứ tự mệnh giá giảm cho đến khi đủ S hoặc không thể chọn thêm. begin k1 = [S/m1] (số đồng tiền mệnh giá m1). b=0 for i = 2 to n b = b + ki-1mi-1 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn - 10 - Si = S - b (số tiền còn lại sau khi đã chọn các đồng tiền mệnh giá m1, ...,mi-1) ki = [Si]/mi ( số đồng tiền mệnh giá mi) end; Thí dụ 1.1. S = 298, M = {50, 20, 10, 5, 2, 1} Bƣớc Mệnh giá mi Số đồng tiền 1 2 3 4 5 6 50 20 10 5 2 1 Tổng giá trị đã có Giá trị còn lại 250 290 290 295 297 298 48 8 8 3 1 0 Tổng giá trị đã có 30 30 40 Giá trị còn lại 10 10 0 5 2 0 1 1 1 Thuật toán cho lời giải tối ƣu Thí dụ 1.2. S = 40, M = {30, 20, 5, 2} Bƣớc mi 1 30 2 20 3 5 Tổng cộng: 3 tờ tiền Ki 1 0 2 Phƣơng án tối ƣu hơn: 2 tờ, mỗi tờ mệnh giá 20. Kết luận: Nhƣ vậy thuật toán tham không phải khi nào cũng cho lời giải tối ƣu. Nhƣng khi tập dữ liệu lớn thì thuật toán nhanh chóng cho lời giải tối ƣu hoặc gần tối ƣu. d. Bài toán ba lô nguyên (0-1) Giả sử ba lô có dung lƣợng là W. Có các vật b 1, ..., bn với dung lƣợng wi và giá trị pi (profit). Xếp các vật vào ba lô sao cho đạt tổng giá trị lớn nhất (giả thiết là các vật không thể chia nhỏ). Ký hiệu xi là biến quyết định (loại 0-1): Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn - 11 - xi = 1𝑛ế 𝑢 𝑐𝑕ọ 𝑛 𝑣ậ 𝑡 𝑏𝑖 0 𝑛ế 𝑢 𝑘𝑕á𝑐 Khi đó bài toán đƣợc phát biểu nhƣ sau: Tìm vector x = (x1, x2, ..., xn), xi 𝜖 {0, 1} sao cho ràng buộc 𝑛 𝑖=1 𝑝𝑖 𝑥𝑖 𝑛 𝑖=1 𝑝𝑖 𝑥𝑖 → 𝑚𝑎𝑥 với ≤ 𝑊. e. Các phương pháp tham (GrM) đối với bài toán ba lô 0-1 GrM dựa trên việc đặt các vật vào ba lô từng cái một. Các chiến lƣợc chọn vật đặt vào ba lô: * Greedy-by-profit: Tại mỗi bƣớc chọn trong các vật còn lại vật có giá trị lớn nhất (với điều kiện dung lƣợng của ba lô cho phép). * Greedy-by-weight: Tại mỗi bƣớc chọn vật có trọng lƣợng bé nhất trong các vật còn lại. Đặt càng nhiều vật vào ba lô càng tốt. * Greedy-by-profit-density: Tại mỗi bƣớc chọn trong số các vật còn lại vật có mật độ giá trị di = pi/wi lớn nhất. Thí dụ 1.3. Cho các vật trong bảng và W = 100. i wi pi 1 100 40 2 50 35 3 45 18 4 20 4 5 10 10 6 5 2 * Greedy-by-profit-density di = pi/wi 0.4 0.7 0.4 0.2 1.0 0.4 Step 0: x1 = x2 = ... = x + 6 = 0 Bƣớc Biến 1 2 3 4 x5 = 1 x2 = 1 x6 = 1 x4 = 1 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 𝒘𝒊 𝒙𝒊 10 60 65 85 𝒑𝒊 𝒙𝒊 10 45 47 51 http://www.lrc-tnu.edu.vn - 12 - * Greedy-by-profit Start: x1 = x2 = ... = x + 6 = 0 𝒘𝒊 𝒙𝒊 Bƣớc Biến 1 x1 = 1 𝒑𝒊 𝒙𝒊 100 40 * Greedy-by-weight 𝒘𝒊 𝒙𝒊 Bƣớc Biến 1 2 3 4 x6 = 1 x5 = 1 x4 = 1 x3 = 1 𝒑𝒊 𝒙𝒊 5 15 35 80 2 12 16 34 Nhận xét 1. Greedy-by-profit-density tốt hơn theo profit hoặc theo weight nhƣng còn xa mới tới giá trị tối ƣu khi W = 100 và profit = 55. Bảng dƣới đây trình bày 4 lời giải: i wi pi di G-profit G-weight G-density Optimal solution 1 2 3 4 5 6 100 50 45 20 10 5 40 35 18 4 10 2 0.4 0.7 0.4 0.2 1.0 0.4 1 0 0 0 0 0 100 40 0 0 1 1 1 1 80 34 0 1 0 1 1 1 85 51 0 1 1 0 0 1 100 55 Total weight Total profit Nhận xét 2. Bài toán ba lô 0-1 là bài toán NP-C, do đó có thể không có lời giải tối ƣu. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn - 13 - 1.2.4. Tô mầu đồ thị với bài toán 4 mầu a. Giới thiệu Lịch sử xuất hiện giả thuyết bốn màu còn nhiều điều chƣa rõ. Có ý kiến cho rằng Mobious đã biết bài toán này từ năm 1852 khi Francis Guthrie, một sinh viên trƣờng Tổng hợp London trình bày bài toán này cho Augustus De Morgan, và ông này đã mô tả nó trong thƣ gửi cho Hamilton. (Lại có ý kiến khác cho rằng bài toán này xuất hiện vào khoảng những năm 1850-1852 từ một nhà buôn ngƣời Anh là Gazri khi tô bản đồ hành chính nƣớc Anh đã cố gắng chứng minh rằng nó có thể tô bốn màu. Sau đó, năm 1952 ông ta đã viết thƣ cho DeMorgan để thông báo về giả thuyết này). Năm 1878 Kelly, nhà toán học nổi tiếng ngƣời Anh đã phát biểu trƣớc hội toán học London với thông báo rằng ông đã suy nghĩ nhiều ngày về bài toán bốn màu nhƣng không thể giải đƣợc. Tính hấp dẫn của bài toán này nằm ở tính dễ hiểu trong cách phát biểu bài toán : “Cần chứng minh rằng một đồ thị phẳng bất kỳ có thể tô bởi bốn màu sao cho hai đỉnh kề nhau có hai màu khác nhau”. Để giả bài toán này, có hai khuynh hƣớng : 1. Đối với một đồ thị phẳng bất kỳ, xây dựng thuật toán thực hiện việc tô màu các đỉnh bởi bốn màu. 2. Chứng minh sự tồn tại của phép tô màu đó. Tóm lại, bài toán bốn màu được phát biểu như sau: Phát biểu bài toán bốn màu: Cho một bản đồ trong đó có N nƣớc. Cần tô màu cho các nƣớc sao cho hai nƣớc kề nhau (tức là có chung biên giới) đƣợc tô bởi hai màu khác nhau, nhờ đó có thể phân biệt các vùng một cách dễ dàng. Bài toán sẽ không còn tồn tại nếu nhƣ có số lƣợng màu lớn. Tuy nhiên, sẽ thực sự khó khăn với ràng buộc rằng phải sử dụng số màu là nhỏ nhất. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- Xem thêm -