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)= eE 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 -
.DOC 
77 
569 
70 
