Tài liệu Giải thuật di truyền bài toán cây steiner

  • Số trang: 77 |
  • Loại file: DOC |
  • Lượt xem: 199 |
  • Lượt tải: 0
nhattuvisu

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

Mô tả:

Giải thuật di truyền giải bài toán cây Steiner MỤC LỤC DANH MỤC HÌNH..................................................................................................4 DANH MỤC BẢNG................................................................................................6 LỜI MỞ ĐẦU..........................................................................................................7 CHƯƠNG 1..............................................................................................................8 GIỚI THIỆU BÀI TOÁN.......................................................................................8 1. MỘT SỐ CÁC KHÁI NIỆM CƠ SỞ...........................................................................8 1.1. Đồ thị...........................................................................................................8 1.2. Cấu trúc dữ liệu biểu diễn đồ thị................................................................10 2.3 Danh sách kề..............................................................................................12 1.3. Các thuật toán trên đồ thị...........................................................................13 1.4. Bài toán tối ưu............................................................................................19 2. BÀI TOÁN CÂY STEINER....................................................................................22 2.1. Lịch sử bài toán cây Steiner.......................................................................22 2.2. Lời giải cho bài toán 3 điểm của Fermat....................................................23 2.3. Hệ số Steiner cho trường hợp ba điểm.......................................................26 2.4. Mô tả bài toán cây Steiner trên đồ thị........................................................27 2.5. Một số ứng dụng của bài toán....................................................................28 2.6. Các thuật toán giải đúng............................................................................31 CHƯƠNG 2............................................................................................................34 GIẢI THUẬT DI TRUYỀN..................................................................................34 1. GIỚI THIỆU VÀ LỊCH SỬ PHÁT TRIỂN.................................................................34 2. CÁC KHÁI NIỆM CƠ BẢN...................................................................................34 2.1. Nhiễm sắc thể (Chromosome)...................................................................34 2.2. Quần thể (Population)................................................................................34 2.3. Chọn lọc (Selection)...................................................................................35 2.4. Lai ghép (CrossOver)................................................................................35 2.5. Đột biến (Mutation)...................................................................................35 2.6. Hàm thích nghi (Fitness Function)............................................................35 3. KHÔNG GIAN TÌM KIẾM (SEARCH SPACE).........................................................35 4. MÔ TẢ GA........................................................................................................35 5. CÁC THAM SỐ CỦA GA.....................................................................................37 5.1. Kích thước quần thể...................................................................................37 5.2. Xác suất lai ghép........................................................................................37 5.3. Xác suất đột biến........................................................................................37 6. KHỞI TẠO QUẦN THỂ BAN ĐẦU VÀ CHỌN LỌC CÁ THỂ......................................37 6.1. Khởi tạo quần thể.......................................................................................37 6.2. Hàm tính độ thích nghi..............................................................................38 6.3. Chọn lọc.....................................................................................................38 Nguyễn Thanhh Tùng-KHMT-K48 1 Giải thuật di truyền giải bài toán cây Steiner 7. CÁC TOÁN TỬ DI TRUYỀN.................................................................................40 7.1. Mã hóa nhiễm sắc thể................................................................................40 7.2. Lai ghép (CrossOver)................................................................................42 7.3. Đột biến (Mutation)...................................................................................45 8. CHIẾN LƯỢC NẠP LẠI QUẦN THỂ.......................................................................46 8.1. Nạp lại hoàn toàn.......................................................................................46 8.2. Nạp lại ngẫu nhiên.....................................................................................46 8.3. Nạp lại theo mô hình cá thể ưu tú..............................................................46 9. ĐIỀU KIỆN DỪNG CỦA GA................................................................................47 10. ĐẶC ĐIỂM VÀ ỨNG DỤNG CỦA GA.................................................................47 10.1. Đặc điểm..................................................................................................47 10.2. Ứng dụng.................................................................................................48 CHƯƠNG 3............................................................................................................49 GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN CÂY STEINER.......................49 1. MÃ HÓA LỜI GIẢI..............................................................................................49 2. PHƯƠNG PHÁP KHỞI TẠO QUẦN THỂ BAN ĐẦU..................................................50 3. CHỌN LỌC.........................................................................................................51 3.1. Chọn lọc xếp hạng tuyến tính....................................................................51 3.2. Chọn lọc xếp hạng phi tuyến......................................................................51 3.3. Chọn lọc cạnh tranh...................................................................................51 4. LAI GHÉP..........................................................................................................51 4.1. Lai ghép hai cha mẹ...................................................................................51 4.2. Lai ghép nhiều cha mẹ...............................................................................52 5. ĐỘT BIẾN..........................................................................................................52 5.1. Đột biến chuẩn...........................................................................................52 5.2. Đột biến đổi chỗ.........................................................................................53 5.3. Phép đột biến đảo đoạn..............................................................................54 5.4. Phép đột biến thêm đỉnh............................................................................54 5.5. Phép đột biến xóa đỉnh...............................................................................54 6. TỐI ƯU CÂY......................................................................................................54 CHƯƠNG 4............................................................................................................56 KẾT QUẢ THỰC NGHIỆM................................................................................56 1. DỮ LIỆU THỬ NGHIỆM.......................................................................................56 1.1. Nguồn dữ liệu............................................................................................56 1.2. Đặc điểm dữ liệu........................................................................................56 1.3. Định dạng file dữ liệu vào..........................................................................57 2. MÔI TRƯỜNG THỬ NGHIỆM...............................................................................58 3. CÀI ĐẶT THỬ NGHIỆM.......................................................................................59 3.1. Các tham số................................................................................................59 3.2.Các hàm chính trong chương trình..............................................................62 Nguyễn Thanhh Tùng-KHMT-K48 2 Giải thuật di truyền giải bài toán cây Steiner 4. KẾT QUẢ THỬ NGHIỆM......................................................................................63 4.1.Các bảng kết quả.........................................................................................63 4.2.So sánh các kết quả.....................................................................................70 CHƯƠNG 5............................................................................................................73 HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH....................................................73 1.CHƯƠNG TRÌNH.................................................................................................73 2. CHẠY CHƯƠNG TRÌNH GIẢI BÀI TOÁN CHO MỘT FILE DỮ LIỆU VÀO..................73 3. CHẠY CHƯƠNG TRÌNH GIẢI BÀI TOÁN CHO NHIỀU FILE DỮ LIỆU VÀO...............73 KẾT LUẬN............................................................................................................74 TÀI LIỆU THAM KHẢO.....................................................................................75 Nguyễn Thanhh Tùng-KHMT-K48 3 Giải thuật di truyền giải bài toán cây Steiner DANH MỤC HÌNH HÌNH 1.1. ĐỒ THỊ VÔ HƯỚNG (TRÁI) VÀ ĐỒ THỊ CÓ HƯỚNG (PHẢI).. .8 HÌNH 1.2. ĐỒ THỊ VÔ HƯỚNG LIÊN THÔNG.................................................9 HÌNH 1.3. CÂY........................................................................................................9 HÌNH 1.4. ĐỒ THỊ VÀ CÂY KHUNG..................................................................9 HÌNH 1.5. ĐỒ THỊ VÀ CÂY KHUNG NHỎ NHẤT..........................................10 HÌNH 1.6. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN KỀ....................................11 HÌNH 1.7. BIỂU DIỄN ĐỒ THỊ BẰNG DANH SÁCH CẠNH CUNG.............12 HÌNH 1.8. DANH SÁCH KỀ VÀ MA TRẬN KỀ TƯƠNG ỨNG.....................12 HÌNH 1.9. ĐƯỜNG ĐI NGẮN NHẤT ĐẾN CÁC ĐỈNH CÒN LẠI.................17 HÌNH 1.10. ĐỒ THỊ CÓ HƯỚNG KHÔNG CÓ CHU TRÌNH ÂM.................18 HÌNH 1.11. MẠCH LOGIC, ĐẦU VÀO ĐƯỢC NHẬP TỪ BÊN TRÁI VÀ ĐẦU RA Ở BÊN PHẢI.........................................................................................20 HÌNH 1.12. CÁC LỚP BÀI TOÁN P, NP VÀ CO-NP.......................................21 HÌNH 1.13. PHÂN LỚP TẠM THỜI CÁC BÀI TOÁN.....................................22 HÌNH 1.14. BÀI TOÁN CỦA FERMAT VỚI N=3.............................................23 HÌNH 1.15. GIẢI PHÁP CỦA TORRICELLI....................................................24 HÌNH 1.16. GIẢI PHÁP CỦA SIMPSON...........................................................24 HÌNH 1.17. ĐIỀU KIỆN VỀ GÓC.......................................................................25 HÌNH 1.18. CÂY STEINER CHO BA ĐIỂM....................................................27 HÌNH 1.19. MINH HỌA CHO LỜI GIẢI BÀI TOÁN TÌM HỆ SỐ STEINER. ................................................................................................................................. 27 HÌNH 1.20. CÂY STEINER TRÊN ĐỒ THỊ LƯỚI...........................................30 HÌNH 2.1. XÁC SUẤT CỦA MỖI NST THEO KIỂU LỰA CHỌN ROULET. ................................................................................................................................. 39 HÌNH 2.2. TRẠNG THÁI QUẦN THỂ TRƯỚC KHI SẮP XẾP (ĐỒ THỊ THEO HÀM THÍCH NGHI)................................................................................39 HÌNH 2.3. TRẠNG THÁI QUẦN THỂ SAU KHI SẮP XẾP (ĐỒ THỊ THEO THỨ TỰ)................................................................................................................ 40 HÌNH 2.4. LAI GHÉP MỘT ĐIỂM CẮT MÃ HÓA NHỊ PHÂN......................43 HÌNH 2.5. LAI GHÉP HAI ĐIỂM CẮT MÃ HÓA NHỊ PHÂN.......................43 HÌNH 2.6. LAI GHÉP ĐỒNG NHẤT MÃ HÓA NHỊ PHÂN............................43 Nguyễn Thanhh Tùng-KHMT-K48 4 Giải thuật di truyền giải bài toán cây Steiner HÌNH 2.7. LAI GHÉP SỐ HỌC MÃ HÓA NHỊ PHÂN.....................................44 HÌNH 2.8. LAI GHÉP VỚI LƯU TRỮ CẤU TRÚC CÂY................................44 HÌNH 2.9. PHÉP ĐỘT BIẾN VỚI MÃ HÓA CẤU TRÚC CÂY......................45 HÌNH 2.10. CHIẾN LƯỢC NẠP LẠI HOÀN TOÀN........................................46 HÌNH 2.11. CHIẾN LƯỢC NẠP LẠI NGẪU NHIÊN.......................................46 HÌNH 2.12. NẠP THEO MÔ HÌNH CÁ THỂ ƯU TÚ......................................46 HÌNH 3.1. ĐỒ THỊ CON VÀ MÃ TƯƠNG ỨNG..............................................49 HÌNH 3.2. HAI TRONG SỐ NHIỀU ĐỒ THỊ CON TƯƠNG ỨNG VỚI CHUỖI MÃ 1110110.............................................................................................50 HÌNH 3.3. MINH HỌA NHIỄM SẮC THỂ HỢP LỆ........................................50 HÌNH 3.4. LAI GHÉP HAI CHA MẸ..................................................................52 HÌNH 3.5. LAI GHÉP NHIỀU CHA MẸ............................................................52 HÌNH 4.1. ĐỒ THỊ MINH HỌA CHO FILE DỮ LIỆU....................................57 HÌNH 4.2. ĐỒ THỊ SO SÁNH HIỆU QUẢ LÀM VIỆC CỦA CÁC PHÉP LAI GHÉP.....................................................................................................................70 HÌNH 4.3. ĐỒ THỊ SO SÁNH HIỆU QỦA LÀM VIỆC CỦA CÁC PHÉP ĐỘT BIẾN....................................................................................................................... 71 HÌNH 4.4. ĐỒ THỊ SO SÁNH HIỆU QUẢ CỦA CÁC PHÉP CHỌN LỌC....72 Hình 5.1. Giao diện chương trình.........................................................................73 Nguyễn Thanhh Tùng-KHMT-K48 5 Giải thuật di truyền giải bài toán cây Steiner DANH MỤC BẢNG BẢNG 1.1. MỘT SỐ GIẢI THUẬT GẦN ĐÚNG CHO BÀI TOÁN TRÊN ĐỒ THỊ......................................................................................................................... 29 BẢNG 2.1. MÃ HÓA NHỊ PHÂN ĐỘ DÀI 20 BIT............................................40 BẢNG 2.2: MÃ HÓA HOÁN VỊ 2 NST A&B.....................................................41 BẢNG 2.3: MÃ HÓA GIÁ TRỊ CÁC NST A,B,C...............................................41 BẢNG 2.4: MÃ HÓA NST A THEO CẤU TRÚC CÂY....................................42 BẢNG 2.5: MẶT NẠ LAI GHÉP ĐỒNG NHẤT................................................43 BẢNG 2.6: LAI GHÉP MỘT ĐIỂM CẮT MÃ HÓA HOÁN VỊ.......................44 BẢNG 2.7: PHÉP ĐẢO BIT MÃ HÓA NHỊ PHÂN...........................................45 BẢNG 2.8. HOÁN VỊ THỨ TỰ MÃ HÓA HOÁN VỊ........................................45 BẢNG 2.9. THAY ĐỔI GIÁ TRỊ TRONG MÃ HÓA GIÁ TRỊ........................45 BẢNG 4.1. KẾT QUẢ SO SÁNH CÁC PHÉP LAI GHÉP TRÊN BỘ DỮ LIỆU I160......................................................................................................................... 63 BẢNG 4.2. KẾT QUẢ SO SÁNH GLMIN VỚI MỘT SỐ GIẢI THUẬT GẦN ĐÚNG KHÁC TRÊN BỘ DỮ LIỆU I160............................................................64 BẢNG 4.3. KẾT QUẢ SO SÁNH CÁC PHÉP LAI GHÉP TRÊN BỘ DỮ LIỆU I320......................................................................................................................... 65 BẢNG 4.4. KẾT QUẢ SO SÁNH GLMIN VỚI MỘT SỐ GIẢI THUẬT GẦN ĐÚNG KHÁC TRÊN BỘ DỮ LIỆU I320............................................................66 BẢNG 4.5. KẾT QUẢ SO SÁNH CÁC PHÉP LAI GHÉP TRÊN BỘ DỮ LIỆU I640......................................................................................................................... 67 BẢNG 4.6. KẾT QUẢ SO SÁNH CÁC PHÉP LAI GHÉP TRÊN BỘ DỮ LIỆU I640(TIẾP).............................................................................................................68 BẢNG 4.7. KẾT QUẢ SO SÁNH CÁC PHÉP LAI GHÉP TRÊN BỘ DỮ LIỆU THỰC TẾ............................................................................................................... 69 Bảng 4.8. Kết quả so sánh GLmin với một số giải thuật gần đúng khác trên bộ dữ liệu thực tế........................................................................................................69 Nguyễn Thanhh Tùng-KHMT-K48 6 Giải thuật di truyền giải bài toán cây Steiner LỜI MỞ ĐẦU Bài toán cây Steiner trong đồ thị là một bài toán NP-khó trong nhóm các bài toán thiết kế mạng (network designed problem). Bài toán tìm cây Steiner nhỏ nhất trên đồ thị được ứng dụng trong nhiều lĩnh vực thực tế như thiết kế mạng viễn thông, thiết kế vi mạch hay nghiên cứu sự tiến hóa trong sinh học…. Do tầm quan trọng của bài toán, rất nhiều hướng tiếp cận để giải xấp xỉ bài toán đã được đề xuất với mục đích đưa ra lời giải xấp xỉ tốt nhất với thời gian chấp nhận được. Trong đồ án này trình bày cách giải quyết bài toán theo thuật toán di truyền, đây là một hướng giải quyết khá thành công. Cấu trúc đồ án gồm có năm chương như sau:  Chương 1. Trình bày lý thuyết cơ sở về đồ thị và bài toán Cây Steiner.  Chương 2. Trình bày lý thuyết cơ bản về giải thuật di truyền.  Chương 3. Trình bày thuật toán di truyền giải bài toán Cây Steiner trên đồ thị.  Chương 4. Các kết quả thực nghiệm.  Chương 5. Hướng dẫn sử dụng chương trình. Để có được kết quả này, em xin gửi lời cảm ơn chân thành nhất đến cô giáo Ths.Huỳnh Thị Thanh Bình bộ môn khoa học máy tính, cô đã tận tình hướng dẫn, chỉ bảo em trong quá trình thực tập và làm đồ án. Em xin gửi lời cảm ơn đến thầy Nguyễn Việt Huy bộ môn khoa học máy tính, thầy đã nhiệt tình giúp đỡ em trong việc tìm hiểu bài toán. Em xin gửi lời cảm ơn đến tất cả các thầy cô trong bộ môn khoa học máy tính, các thầy cô đã giúp chúng em có rất nhiều kiến thức rất bổ ích. Cuối cùng, em xin gửi lời cảm ơn đến gia đình và bạn bè, mọi người là nguồn động viên tinh thần rất lớn cho em! Hà nội, tháng 5 năm 2008 Sinh viên Nguyễn Thanh Tùng Nguyễn Thanhh Tùng-KHMT-K48 7 Giải thuật di truyền giải bài toán cây Steiner CHƯƠNG 1 GIỚI THIỆU BÀI TOÁN 1. Một số các khái niệm cơ sở 1.1. Đồ thị 1.1.1. Định nghĩa đồ thị Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này, các loại đồ thị được phân biệt bởi sự khác biệt giữa kiểu cũng như số lượng cạnh nối các đỉnh của đồ thị. Trong các tài liệu, khái niệm về đồ thị đôi khi được đề cập không đồng nhất, dưới đây đưa ra một số định nghĩa về đồ thị [32]. Hình 1.1. Đồ thị vô hướng (trái) và đồ thị có hướng (phải). Định nghĩa 1: Đơn đồ thị vô hướng G=(V, E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là cạnh. Định nghĩa 2: Đa đồ thị vô hướng G=(E, V) bao gồm V là tập các đỉnh và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh. Đồ thị có trọng số là một khái niệm hết sức quan trọng trong các nghiên cứu lý thuyết về đồ thị bởi tính ứng dụng rộng dãi của nó. Ví dụ, một mạng máy tính mô phỏng bằng đồ thị thì trọng số có thể là khoảng cách vật lý hoặc thông lượng truyền dữ liệu giữa hai máy tính được nối trực tiếp trong mạng, một mạng lưới giao thông có thể được mô phỏng bằng một đồ thị có trọng số trong đó trọng số của mỗi cạnh nối hai đỉnh có thể được dùng để biểu diễn khoảng cách vật lý của đoạn đường nối hai điểm này… Trên thực tế, có rất nhiều bài toán được mô phỏng rất mềm dẻo trên đồ thị và đã cho những kết quả lời giải rất tốt. 1.1.2. Đường đi và chu trình Định nghĩa 1 : Cho đồ thị G = (V, E). Đường đi từ đỉnh s đến đỉnh t trên G là dãy các đỉnh : Pst : s = v0, v1, v1, …, vk-1,vk = t Trong đó : (vi-1, vi)  E  i = 1,..k k : độ dài đường đi Pst ( bằng số lượng cạnh trên đường đi) Nguyễn Thanhh Tùng-KHMT-K48 8 Giải thuật di truyền giải bài toán cây Steiner Đường đi Pst được biểu diễn theo dãy cạnh (v0,v1), (v1,v2), …, (vk-1,vk Đinh nghĩa 2 : Chu trình là một đường đi không có cạnh nào bị lặp lại và cóđỉnhđầutrùng đỉnh cuối. 1.1.3. Đồ thị vô hướng và liên thông Định nghĩa : Đồ thị vô hướng G = (V, E) gọi là liên thông nếu luôn tồn tại đường đi giữa mọi cặp đỉnh phân biệt trên đồ thị. Hình 1.2. Đồ thị vô hướng liên thông. 1.1.4. Cây Định nghĩa : Cây là một đơn đồ thị vô hướng, liên thông không chứa chu trình. Bậc của đỉnh: là số cạnh xuất phát hoặc kết thúc tại đỉnh đó. Hình 1.3. Cây. 1.1.5. Cây khung của đồ thị Hình 1.4. Đồ thị và cây khung. Nguyễn Thanhh Tùng-KHMT-K48 9 Giải thuật di truyền giải bài toán cây Steiner Định nghĩa : Cho G = (V, E) là một đơn đồ thị vô hướng liên thông với |V| = n đỉnh và |E| = m cạnh. Cây T = (V, F) với F  E được gọi là cây khung của đồ thị G. ( Khi đó |F| = m-1 ). Cây khung có bậc bị chặn (Degree-constrained Spanning Tree): Cho số nguyên d  2, cây khung có bậc bị chặn là cây khung T trên đồ thị G mà bậc của mỗi đỉnh của nó không vượt quá d. Trọng số của cạnh : Mỗi cạnh e trên G được gán một giá trị w(e) được gọi là trọng số của cạnh. Trọng số của cây khung: Trọng số của cây khung sẽ là tổng trọng số của các cạnh trên cây khung đó. Trọng số cây khung T của G được tính bởi : W (T )  �w(e) e�T Cây khung nhỏ nhất (MST- Minimum Spanning Tree): Cây khung nhỏ nhất của G là cây khung T có trọng số nhỏ nhất. 4 6 2 5 3 7 1 8 Hình 1.5. Đồ thị và cây khung nhỏ nhất. 1.2. Cấu trúc dữ liệu biểu diễn đồ thị 1.2.1 Ma trận kề, ma trận trọng số Trong phương pháp biểu diễn đồ thị bằng ma trận, mỗi đồ thị sẽ được biểu diễn bằng một ma trận vuông tương ứng với cấu trúc dữ liệu mảng hai chiều trong máy tính (cũng có thể dùng mảng 1 chiều). Xét đơn đồ thị vô hướng G=(V, E), với tập đỉnh V={1, 2, 3……n}, tập cạnh E= {e 1, e2, e3……em}. Ma trận kề của đồ thị G là một ma trận nhị phân(các phần tử trong ma trận chỉ là 0 hoặc 1) có kích thước n x n A={aij: i,j=1, 2, 3……,n} có các phần tử được xác định theo quy tắc sau: aij=0 nếu (i, j)  E i,j = 1, 2, 3……n aij = 1 nếu (i, j)  E i,j = 1, 2, 3……n Với lưu ý rằng (u, v)  (v, u) trên đồ thị vô hướng thì dễ dàng nhận ra ma trận kề biểu diễn đồ thị vô hướng là một ma trận đối xứng tức là a[i, j] = a[j, i] (với mọi i, j = 1, 2, 3……n). Ngược lại, mỗi một ma trận đối xứng cấp n sẽ tương ứng với một đồ thị vô hướng. Với phương pháp biểu diễn nhị phân này thì tổng của hàng i(côt j) chính là bậc của đỉnh i(cột j). Đối với đồ thị có định hướng, phương pháp lưu trữ bằng ma trận kề được tiến hành tương tự với đồ thị vô hướng, sự khác biệt nằm ở việc ma trận kề của đồ thị có hướng không phải là một ma trận đối xứng bởi trong đồ thị có hướng cung (u, v)  (v, u). Nguyễn Thanhh Tùng-KHMT-K48 10 Giải thuật di truyền giải bài toán cây Steiner Hình 1.6. Biểu diễn đồ thị bằng ma trận kề. Với một chút thay đổi trong quy ước, đa đồ thị có thể được biểu diễn bằng ma trận kề nếu thay vì điền 1 vào a[i, j] ta sẽ điền chính xác số cạnh nối đỉnh i với j. Một điều cần lưu ý là ma trận kề biểu diễn đa đồ thị vô hướng là ma trận đối xứng còn ma trận kề của đa đồ thị có hướng không phải là ma trận đối xứng, tương tự như trong trường hợp của đơn đồ thị. Nếu đồ thị đang nghiên cứu là một đồ thị trọng số thì phương pháp biểu diễn sẽ được tiến hành tương tự như sau: Cho một đồ thị trọng số G=(V, E, c(i,j)) trong đó c(i, j) là giá trị trọng số của cạnh (i, j). Khi đó ma trận C biểu diễn đồ thị này vẫn là một ma trận vuông cấp n được xác định: c[i, j] = c(i, j) trong trường hợp (i, j)  E c[i, j] =  nếu (i, j)  E , trong đó  tùy trường hợp cụ thể mà có thể chọn những giá trị sau: 0, +  , -  . Ưu điểm nổi bật nhất của phương pháp biểu diễn bằng ma trận thể hiện khi bài toán cần trả lời câu hỏi hai đỉnh i và j có kề với nhau trên đồ thị hay không, thời gian để trả lời câu hỏi này là hằng số không phụ thuộc vào kích thước của ma trận, với những thuật toán có yêu cầu thường xuyên chèn thêm hoặc loại bỏ các cạnh(cung) của thì cấu trúc dữ liệu này cũng tỏ ra khá thích hợp. Tuy vậy, cấu trúc dữ liệu này có một nhược điểm lớn nhất là dùng quá nhiều bộ nhớ, mỗi ma trận luôn phải dùng n2 bộ nhớ để biểu diễn không phụ thuộc vào số cạnh của đồ thị, đặc biệt trong trường hợp biểu diễn cho đồ thị vô hướng thì số ô nhớ lãng phí ít nhất là n2  n , hơn thế nữa nếu muốn tìm danh sách những đỉnh kề với một đỉnh bất kỳ thì 2 sẽ phải duyệt qua tất cả các đỉnh của đồ thị 1.2.2. Danh sách cạnh, cung Trong những trường hợp bài toán luôn làm việc với những đồ thị thưa (đồ thị có số cạnh m và số đỉnh n thỏa mãn bất đẳng thức m<6n) thì cấu trúc dữ liệu ma trận kề, ma trận trọng số tỏ ra không thích hợp bởi có quá nhiều ô nhớ bị lãng phí, trong trường hợp này, cấu trúc dữ liệu danh sách cạnh(cung) được sử dụng. Theo phương pháp lưu trữ này, mỗi cạnh (cung) e của đồ thị sẽ được lưu trữ bằng hai biến Dau[e] và Cuoi[e]. Các biến Dau và Cuoi có thể là các phần tử của một vector hoặc là một node của một danh sách nối đơn, tùy thuộc vào số lượng cạnh (cung) của đồ thị có thay đổi thường xuyên trong quá trình tiến hành thuật toán hay không. Với đồ thị có trọng số, ngoài việc sử dụng 2m đơn vị bộ nhớ để lưu trữ danh sách các cạnh thì còn cần tới m đơn vị bộ nhớ để lưu trữ thêm trọng số của các cạnh(cung). Ưu điểm dễ thấy nhất của phương pháp này là việc tích kiệm được bộ nhớ, tuy vậy, không phải với đồ thị thưa nào cách lưu trữ này cũng tốt mà với Nguyễn Thanhh Tùng-KHMT-K48 11 Giải thuật di truyền giải bài toán cây Steiner những đồ thị nhỏ(n<18) thì cách lưu trữ này còn lãng phí bộ nhớ nhiều hơn lưu trữ bằng ma trận. Hơn thế nữa phương pháp lưu trữ này luôn gây khó khăn trong việc duyệt tìm kiếm các đỉnh kề của một đỉnh bất kỳ, để duyệt được các đỉnh kề này, trong mọi trường hợp luôn phải duyệt qua tất cả các cạnh của đồ thị. Hình 1.7. Biểu diễn đồ thị bằng danh sách cạnh cung. 2.3 Danh sách kề Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị, chúng ta lưu trữ danh sách các đỉnh kề với nó. Ký hiệu adj(v) là danh sách các đỉnh kề với v adj(v)  {u �V , (v, u ) �E} . Danh sách kề có thể được biến đổi để biểu diễn đồ thị có trọng số. Khi đó adj(v)  {(u, cvu ), u �V , (v, u ) �E , cvu  c (v, u )} . Danh sách kề có các tính chất sau đáng quan tâm: Đối với đồ thị có hướng, tổng số phần tử phải lưu trong các danh sách kề là | E|, với đồ thị vô hướng, giá trị này là 2|E|. Cho cả đồ thị có hướng và vô hướng, để lưu trữ danh sách kề của đồ thị, cần bộ nhớ (V + E). Các thao tác trên cạnh đòi hỏi phải duyệt danh sách kề nên tốn thời gian. Hạn chế này có thể khắc phục trong một số trường hợp khi danh sách kề được biểu diễn bằng mảng tĩnh, thay vì danh sách liên kết. Như vậy, ưu điểm đòi hỏi không gian lưu trữ nhỏ của cách biểu diễn danh sách kề phải trả giá bằng thao tác xử lý tốn thời gian. Hình 1.8. Danh sách kề và ma trận kề tương ứng. Việc chọn cách biểu diễn nào còn tùy thuộc vào từng trường hợp cụ thể. Trong hầu hết các ứng dụng, cách biểu diễn đồ thị bằng ma trận kề thường dùng trong trường hợp đồ thị kích thước nhỏ hay là đồ thị dày, tức là đồ thị có số cạnh lớn gần bằng nửa bình phương số đỉnh. Trong trường hợp ngược lại nên chọn cách biểu diễn bằng danh sách kề. Nguyễn Thanhh Tùng-KHMT-K48 12 Giải thuật di truyền giải bài toán cây Steiner 1.3. Các thuật toán trên đồ thị 1.3.1. Thuật toán duyệt đồ thị a. Thuật toán tìm kiếm theo chiều sâu Tư tưởng chính của thuật toán là: Cho đồ thị G(V,E). Từ một đỉnh u hiện thời nào đó đỉnh kề v của u sẽ được thăm và quá trình được lặp lại đối với đỉnh v. ở bước tổng quát, giả sử hiện tại đang xét đỉnh u0, có hai khả năng sẽ xảy ra: - Nếu như tồn tại một đỉnh v0 kề với u0 mà chưa được thăm thì đỉnh v0 đó sẽ trở thành đỉnh đã thăm và quá trình tìm kiếm lại bắt đầu từ đỉnh v0 đó. - Ngược lại, nếu mọi đỉnh kề với u0 đều đã thăm thì ta sẽ quay trở lại đỉnh mà trước đó ta đến đỉnh u0 để tiếp tục quá trình tìm kiếm. Như vậy, trong quá trình thăm đỉnh bằng thuật toán tìm kiếm theo chiều sâu, đỉnh được thăm càng muộn càng sớm được duyệt xong (Cơ chế Last In First Out Vào sau ra trước). Thuật toán DFS có thể được xây dựng bằng một thủ tục đệ quy như sau: 1.Procedure DFS(u); 2. Begin 3. Visit(u); 4. Daxet[u]:=True; 5. For v  Kề(u) do 6. if not Daxet[v] then DFS(v); 7. End; Và thủ tục duyệt hệ thống toàn bộ đỉnh của đồ thị sẽ là: 1.Procedure Find; 2. Begin 3. Fillchar(Daxet,SizeOf(Daxet),False); 4. For u  V do 5. If not Daxet[u] then DFS(u); 6. End; Sau mỗi lần gọi DFS(u) thì toàn bộ các đỉnh cùng thành phần liên thông với u sẽ được thăm. Thủ tục Visit(u) là thao tác trên đỉnh u trong từng bài toán đặt ra cụ thể. b. Thuật toán tìm kiếm theo chiều rộng Thuật toán này thực ra là sự cải biến về thứ tự duyệt đỉnh trên đồ thị của tìm kiếm theo chiều sâu bằng cách thay vì dùng một STACK thì ta lại dùng một hàng đợi QUEUE để kết nạp đỉnh được thăm. Như vậy, đỉnh được thăm càng sớm sẽ càng sớm trở thành duyệt xong (cơ chế First In First Out - Vào trước ra trước). Thủ tục được mô tả dưới đây: 1. Procedure BFS(u); 2. Begin 3. Queue:=Empty Nguyễn Thanhh Tùng-KHMT-K48 13 Giải thuật di truyền giải bài toán cây Steiner 4. Kết nạp u vào Queue; 5. Daxet[u]:=True; 6. While Queue<>Empty do 7. Begin 8. Lấy v từ Queue; 9. 10. 11. Visit(v); For w  Kề(v) do If not Daxet[w] then Begin 12. 13. Kết nạp w vào Queue; 14. Daxet[w]:=True; 15. End; 16. End; 17. End; Thủ tục tìm kiếm theo chiều rộng như sau: 1. Procedure Find; 2. Begin 3. Fillchar(Daxet,SizeOf(Daxet),False); 4. For u  V do 5. If not Daxet[u] then BFS(u); 6. End; Tương tự như thuật toán tìm kiếm theo chiều sâu, ở thuật toán này mỗi lần gọi thủ tục BFS(u) thì mọi đỉnh cùng thành phần liên thông với u sẽ được thăm. Thủ tục Visit(u) như đã nói ở trên. 1.3.2. Bài toán cây khung cực tiểu Bài toán: Giả sử G=(V, E) là đồ thị vô hướng liên thông với trọng số trên cạnh w(e), e  E. Cây T=(V, ET) với ET  E được gọi là cây khung của đồ thị G. Độ dài cây khung T là tổng trọng số trên các cạnh của nó w(T)=  eE w(e) . Cây khung nhỏ nhất(viết tắt là MST) của đồ thị G là cây khung có độ dài nhỏ nhất trong số các cây khung của đồ thị. Bài toán đặt ra là tìm cây khung nhỏ nhất. a.Thuật toán Kruskal Tư tưởng: Để xây dựng tập n-1 cạnh của cây khung nhỏ nhất? tạm gọi là tập K, Kruskal đề nghị cách kết nạp lần lượt các cạnh vào tập đó theo nguyên tắc như sau: Ưu tiên các cạnh có trọng số nhỏ hơn, kết nạp cạnh khi nó không tạo chu trình với tập cạnh đã kết nạp trước đó. Đó là một nguyên tắc chính xác và đúng đắn, đảm bảo tập K nếu thu đủ n-1 cạnh sẽ là cây khung nhỏ nhất. - Khi lập trình để có được sự ưu tiên, cách tốt nhất là sắp xếp trước các cạnh theo trọng số tăng dần. Vì vậy, cấu trúc dữ liệu được sử dụng trong giải thuật Kruskal là danh sách cạnh. Nguyễn Thanhh Tùng-KHMT-K48 14 Giải thuật di truyền giải bài toán cây Steiner - Để kiểm tra xem cạnh đang xét có tạo chu trình không với tập cạnh đã kết nạp, một phương pháp đặc biệt mỗi khi kết nạp được sử dụng đó là: cho một đỉnh trở thành 'dad' của đỉnh kia. Với 2 đỉnh x, y bất kỳ, nếu 'dad cao nhất' của chúng bằng nhau thì cạnh nối x, y sẽ tạo nên chu trình (chu trình này đi qua parent chung đó). Thuật toán Kruskal được miêu tả như sau: in Đồ thị vô hướng G = (V,E) n đỉnh với ma trận trọng số c. out Cây khung nhỏ nhất T của đồ thị G. 1. BEGIN 2. T = ; 3. 4. E là danh sách cạnh sắp xếp theo thứ tự không giảm của trọng số; while (|T|< n-1 AND E  ) 5. 6. 7. 8. 9 10. 11. 12. 13. 14. Chọn e là cạnh đầu tiên trong E; E = E \ {e}; if (T U {e} không chứa chu trình) T = T U {e}; endif endwhile if (|T| < n-1) Ghi nhận đồ thị không liên thông; endif END Thuật toán Kruskal tìm cây khung nhỏ nhất của đồ thị với thời gian O(elogn) với e và n tương ứng là số cạnh và đỉnh của đồ thị. b. Thuật toán Prim Thuật toán Kruskal làm việc kém hiệu quả với những đồ thị dày (đồ thị với số cạnh m» n(n-1)/2). Trong trường hợp đó thuật toán Prim tỏ ra hiệu quả hơn. Thuật toán Prim còn được gọi là phương pháp lân cận gần nhất. Trong phương pháp này bắt đầu từ một đỉnh tuỳ ý của đồ thị, đầu tiên ta nối s với đỉnh lân cận gần nó nhất, chẳng hạn là đỉnh y. Nghĩa là trong số các cạnh kề của đỉnh s, cạnh (s,y) có độ dài nhỏ nhất. Tiếp theo trong số các cạnh kề với hai đỉnh s hoặc y ta tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thứ ba z, và ta thu được cây bộ phận gồm 3 đỉnh và 2 cạnh. Quá trình này sẽ tiếp tục cho đến khi ta thu được cây gồm n đỉnh và n-1 cạnh sẽ chính là cây khung nhỏ nhất cần tìm. Giả sử đồ thị cho bởi ma trận trọng số C = { c[i,j], i, j= 1, 2, . . . , n} . trong quá trình thực hiện thuật toán, ở mỗi bước để có thể nhanh chóng chọn đỉnh và cạnh cần bổ sung vào cây khung, các đỉnh của đồ thị sẽ được gán cho các nhãn. Nhãn của một đỉnh v sẽ gồm hai phần và có dạng [d[v], near[v]], trong đó d[v] dùng để ghi nhận độ dài của cạnh có độ dài nhỏ nhất trong số các cạnh nối với đỉnh v với các Nguyễn Thanhh Tùng-KHMT-K48 15 Giải thuật di truyền giải bài toán cây Steiner đỉnh của cây khung đang xây dựng (ta sẽ gọi là khoảng cách từ đỉnh v đến tập đỉnh của cây khung), còn near[v] ghi nhận đỉnh của cây khung gần v nhất (near[v]:=z). Thuật toán Prim được xây dựng như sau: in Đồ thị vô hướng G = (V,E) n đỉnh với ma trận trọng số c. out Cây khung nhỏ nhất (H,T) của đồ thị G. 1. BEGIN 2. Chọn một đỉnh tùy ý s; 3. H = {s}; T = ; near[s] = s; d[s] = 0; 4. for v  V \ H 5. 6. 7. 8. 9. d[v] = c(s,v); near[v] = s; endfor while (TRUE) Tìm u  V\H là đỉnh có d[u] = min{d[v]: v  V\H}; 10. 11. 12. 13. 14. 15. H = H U {u}; T = T U {(u,near[u])}; if (|H| == n) Ghi nhận cây khung nhỏ nhất (H, T); break; else for v  V \ H 16. if (d[u] > c(u,v) 17. d[u] = c(u,v); 28. near[u] = v; 29. endif 20. endfor 21. endif 22. endwhile 23. END 1.3.3. Tìm đường đi ngắn nhất a. Đường đi ngắn nhất từ một đỉnh Cho đồ thị G = (V, E) với hàm trọng số c không âm trên cạnh. Bài toán đặt ra là tìm đường đi ngắn nhất giữa hai đỉnh u, v cho trước trên đồ thị G. Dijkstra đưa ra thuật toán hiệu quả với ý tưởng gán nhãn tạm thời cho các đỉnh được thăm trong quá trình duyệt đồ thị. Nhãn tạm thời của mỗi đỉnh cho biết cận trên của độ dài đường đi ngắn nhất từ u đến nó. Trong mỗi bước lặp, sẽ có một đỉnh được gán nhãn cố định, khi đó nhãn của đỉnh chính là độ dài đường đi ngắn nhất từ u. Trong Hình 1.9, số đánh tại mỗi đỉnh là độ dài của đường đi ngắn nhất từ s đến đỉnh đó. {(s, t), (t, y), (y, x), (x, z)} là dãy các cạnh trên đường đi ngắn nhất. Nguyễn Thanhh Tùng-KHMT-K48 16 Giải thuật di truyền giải bài toán cây Steiner Hình 1.9. Đường đi ngắn nhất đến các đỉnh còn lại. Thuật toán Dijstra Input: Đồ thị G=(V,E) có n đỉnh, hàm trọng số không âm c trên cạnh, đỉnh xuất phát s. output: Đường đi ngắn nhất từ s đến các đỉnh còn lại. 1. BEGIN 2. for v  V 3. d(v) = c(s,v); 4. p(v) = s; 5. endfor; 6. d(s)=0; 7. T = V \ {s}; //T là tập chứa các đỉnh gán nhãn tạm thời 8. while (T  ) 9. Tìm u  T thỏa mãn d(u) = min; 10. T = T \ {u}; 11. for v  T 12. if (d(v) > d(u) + c(u,v)) 13. d(v) = d(u) + c(u,v); 14. p(v) = u; 15. endif; 16. endfor; 17. endwhile; 18. END Trong thuật toán trên, d là mảng chứa độ dài đường đi ngắn nhất, d(v) là độ dài đường đi ngắn nhất từ s đến v, p là mảng lưu đỉnh kề trước trong đường đi ngắn nhất tìm được, p(v) là đỉnh ngay trước v trong đường đi ngắn nhất từ s đến v. Thuật toán Dijkstra tìm được đường đi ngắn nhất trên đồ thị sau thời gian O(n2). b. Đường đi ngắn nhất giữa tất cả các cặp đỉnh Nguyễn Thanhh Tùng-KHMT-K48 17 Giải thuật di truyền giải bài toán cây Steiner Bài toán đường đi ngắn nhất giữa tất cả các cặp đỉnh là một mở rộng của bài toán tìm đường đi ngắn nhất từ một điểm đến các đỉnh còn lại nên rất tự nhiên nếu sử dụng nhiều lần thuật toán Dijkstra để thu được kết quả mong muốn. Với đồ thị có n đỉnh, cần áp dụng thuật toán Dijkstra n lần, tổng thời gian chạy thuật toán đạt cỡ O(n3). Cũng có độ phức tạp như vậy, thuật toán quy hoạch động Floyd-Warshall được áp dụng để giải bài toán đường đi ngắn nhất giữa tất cả các cặp đỉnh không yêu cầu trọng số của đồ thị phải không âm nhưng có điều kiện đồ thị không tồn tại chu trình âm. Hình 1.10. Đồ thị có hướng không có chu trình âm. Thuật toán Floyd-Warshall in Đồ thị G = (V,E) n đỉnh với ma trận trọng số c. out Ma trận d ghi nhận độ dài đường đi ngắn nhất, ma trận p ghi nhận đường đi. 1. BEGIN 2. Với mọi (i,j), gán d(i,j) = c(i,j) và p(i,j) = i; 3. Với mọi i, gán d(i,i) = 0 và p(i,i) = -1; 4. for i=1 to n 5. for j=1 to n 6. for k=1 to n 7. if (d(i,j) > d(i,k) + d(k,j)) 8. d(i,j) = d(i,k) + d(k,j); 9. p(i,j) = p(k,j); 10. endif 11. endfor //k 12. endfor //j 13. endfor //i 14. END Trong thuật toán Floyd-Warshall, d(i, j) lưu giá trị độ dài đường đi ngắn nhất từ đỉnh i đến đỉnh j trong đồ thị, p(i, j) lưu đỉnh nằm trước đỉnh j trên đường đi ngắn nhất từ i đến j. Dựng lại đường đi ngắn nhất giữa cặp đỉnh (i, j) như sau: Xây dựng lại đường đi ngắn nhất từ đỉnh i đến đỉnh j của đồ thị Nguyễn Thanhh Tùng-KHMT-K48 18 Giải thuật di truyền giải bài toán cây Steiner 1. Getpath(i,j) 2. k = p(i,j); 3. if (k==i) 4. Mark(k); //ghi nhận đỉnh k 5. return; 6. endif 7. Getpath(i,k); 8. Getpath(k,j); 9. End. Thuật toán Floyd-Warshall tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị sau thời gian cỡ O(n3). 1.4. Bài toán tối ưu 1.4.1. Một số khái niệm a. Độ phức tạp của thuật toán Là đánh giá lượng tài nguyên các loại mà các thuật toán đòi hỏi sử dụng. Có hai loại tài nguyên quan trọng là thời gian và bộ nhớ. Đánh giá độ phức tạp tính toán của bài toán là đưa ra thời gian tính của thuật toán tốt nhất tổng số các thuật toán giải bài toán đã và chưa biết. b. Thuật toán có thời gian tính đa thức Là thuật toán mà độ phức tạp thời gian của nó trong trường hợp xấu nhất được giới hạn trên bởi một hàm đa thức của kích thước dữ liệu đầu vào (kích thước dữ liệu đầu vào được tính bằng số bit cần thiết để biểu diễn nó). Tức là nếu n là kích thước dữ liệu đầu vào, thì luôn tồn tại một đa thức p  n  sao cho W  n   O p n   . Ví dụ: Các thuật toán có độ phức tạp thời gian trong trường hợp xấu nhất sau đều có thời gian tính đa thức. O(p(n)) = 2n, O(p(n)) = 3n3, O(p(n)) = 5n+n10, O(p(n)) = nlgn … Các thuật toán có độ phức tạp thời gian trong trường hợp xấu nhất sau không có thời gian tính đa thức. O(f(n)) = 2n, O(p(n)) = 20.01n, O(p(n)) = n! … Có hai cách tiếp cận chính để đánh giá độ phức tạp tính toán: - Đánh giá cận dưới độ phức tạp bài toán. - Chỉ ra mức độ khó của nó có thể so sánh với bất ký bài toán khó hiện đã biết. c. Bài toán quyết định Là bài toán mà đầu ra của nó chỉ có thể là yes hoặc no ( 0 hoặc 1 , đúng hoặc sai, …). Một số bài toán quyết định:  Bài toán về tính nguyên tố sau là bài toán quyết định. “Hỏi số nguyên n có là số nguyên tố hay không?” Nguyễn Thanhh Tùng-KHMT-K48 19 Giải thuật di truyền giải bài toán cây Steiner Với dữ liệu vào lời là no . n 23 thì câu trả lời là yes, còn với dữ liệu vào n 24 thì câu trả  Bài toán tổng con (Subset sum): “Cho tập I số nguyên dương a1, a2…an và một số nguyên dương T. Hỏi có thể tìm được một tập con S của I mà tổng các số trong S = T?”  Bài toán Hamilton dạng quyết định: Cho đồ thị vô hướng G = (V,E) có chứa chu trình Hamilton hay không? 1.4.2. Các bài toán tối ưu Trước những năm 1970, phương pháp chủ yếu để giải các bài toán tối ưu là xây dựng phương pháp giải đúng. Nhưng kinh nghiệm tính toán cũng như phân tích tính hiệu quả của phương pháp này cho thấy rất nhiều hạn chế của nó, nhất là về mặt thời gian tính toán. Phương pháp giải đúng chỉ được áp dụng khi giải bài toán với kích thước nhỏ và trung bình. Từ rất sớm, các nhà khoa học về lý thuyết máy tính như Steve Cook và Dick Karp đã quyết định rằng yêu cầu tối thiểu của bất cứ một bài toán tối ưu nào là thời gian chạy đa thức: O n c  , với c là hằng số. Tuy nhiên, không phải mọi bài toán đều có thể được giải quyết một cách nhanh chóng. Rất khó xác định bài toán nào có thể giải quyết một cách nhanh chóng, bài toán nào không thể. Bởi vậy Cook, Karp, và một số nhà khoa học khác định nghĩa ra lớp bài toán NP-khó, đó là những bài toán không thể giải quyết được trong thời gian đa thức. Hình 1.11. Mạch logic, đầu vào được nhập từ bên trái và đầu ra ở bên phải. Bài toán về tính thực hiện của được của mạch CIR-SAT (Circuit satisfiability) là một ví dụ điển hình của bài toán mà chúng ta chưa biết cách để giải nó trong thời gian đa thức. Trong bài toán này, cho một mạch logic bao gồm một tập các cổng AND, OR, và NOT được kết nối với nhau bởi dây dẫn. Đầu vào cho mạch này là tập m giá trị logic (true/false) x1 , x2 ,..., xm (xem hình 1.12). Đầu ra là một giá trị logic đơn TRUE/FALSE. Cho một bộ giá trị đầu vào, có thể tính được đầu ra trong thời gian đa thức (thực tế là tuyến tính) sử dụng tìm kiếm theo chiều sâu và đánh giá đầu ra của mỗi cổng trong thời gian tuyến tính. Bài toán về tính thực hiện của mạch đặt ra rằng, cho một mạch bất kỳ, liệu rằng có một bộ đầu vào làm cho đầu ra của mạch luôn là TRUE, hoặc ngược lại, luôn là FALSE hay không. Chưa ai biết được cách giải quyết bài toán này nhanh hơn cách thử tất cả 2 m đầu Nguyễn Thanhh Tùng-KHMT-K48 20
- Xem thêm -