1 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC VINH PHẠM VĂN SỸ NGHIÊN CỨU TÌM KIẾM CỤC BỘ CHO BÀI TỐN HƠN NHÂN ỔN ĐỊNH LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN Nghệ An, 2018 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC VINH PHẠM VĂN SỸ NGHIÊN CỨU TÌM KIẾM CỤC BỘ CHO BÀI TỐN HƠN NHÂN ỔN ĐỊNH Chun ngành: CƠNG NGHỆ THƠNG TIN Mã số: LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN Người hướng dẫn: TS HOÀNG HỮU VIỆT Nghệ An, 2018 LỜI CẢM ƠN Lời xin bày tỏ lòng cảm ơn biết ơn chân thành tới tất người hỗ trợ, giúp đỡ tơi q trình thực luận văn tốt nghiệp Tôi xin cảm ơn Ngành Công nghệ Thơng tin, Viện Kỹ thuật Cơng nghệ, Phịng sau đại học, Trường Đại học Vinh quý thầy cô giáo khoa giúp đỡ, tạo điều kiện thuận lợi nhất, hỗ trợ, giảng dạy giúp đỡ tơi q trình học tập thực luận văn tốt nghiệp Đặc biệt muốn gửi lời cảm ơn chân thành đến TS Hoàng Hữu Việt, người hướng dẫn, nhận xét, giúp đỡ để tơi hồn thành luận văn Tơi xin gửi lời cảm ơn đến gia đình, bạn b đ ng nghiệp bên cạnh động viên trình hồn thiện luận văn Nhân đây, tơi xin kính chúc quý Thầy, Cô giáo sức khỏe tiếp tục đạt nhiều thành công nghiên cứu khoa học nghiệp giảng dạy, chúc Viện Kỹ thuật Cơng nghệ ngày phát triển Mặc dù có nhiều cố gắng trình thực luận văn khơng thể tránh khỏi thiếu sót, tơi mong nhận ý kiến đóng góp bổ sung thầy cô giáo bạn để luận văn tơi hồn thiện Tơi xin chân thành cảm ơn! Nghệ An, tháng năm 2018 Học viên Phạm Văn Sỹ MỤC LỤC Trang LỜI CẢM ƠN MỞ ĐẦU Sự cần thiết vấn đề nghiên cứu Mục tiêu nghiên cứu 2.1 Mục tiêu tổng quát 2.2 Mục tiêu cụ thể Đối tượng phạm vi nghiên cứu 3.1 Đối tượng nghiên cứu 3.2 Phạm vi nghiên cứu Nội dung nghiên cứu Kết cấu luận văn 10 Chương TỔNG QUAN VỀ BÀI TỐN HƠN NHÂN ỔN ĐỊNH 12 1.1 Bài tốn nhân ổn định 12 1.1.1 Phát biểu toán 12 1.2.2 Các định nghĩa 13 1.2.3 Các biến thể tốn nhân ổn định 14 1.2.3.1 Bài tốn phân cơng giảng viên hướng dẫn sinh viên thực đề tài14 1.2.3.2 Bài tốn xếp phịng ký túc xá 15 1.2 Các hướng tiếp cận giải tốn nhân ổn định 15 1.3 Kết luận Chương 16 Chương THUẬT TOÁN GALE – SHAPLEY VÀ THUẬT TỐN VÉT CẠN CHO BÀI TỐN HƠN NHÂN ỔN ĐỊNH 18 2.1 Thuật toán Gale - Shapley 18 2.1.1 Mơ tả thuật tốn 18 2.1.2 Ví dụ minh họa 19 2.1.3 Ưu/nhược điểm thuật toán Gale - Shapley 22 2.2 Thủ tục phá vỡ hôn nhân 22 2.3 Thuật toán vét cạn tìm tất phép ghép ổn định 24 2.4 Kết luận chương 28 Chương TÌM KIẾM CỤC BỘ CHO BÀI TỐN HÔN NHÂN ỔN ĐỊNH 29 3.1 Thuật tốn tìm kiếm cục 29 3.2 Thuật tốn tìm kiếm cục chiều cho tốn nhân ổn định30 3.3 Thuật tốn tìm kiếm cục hai chiều cho tốn nhân ổn định32 3.4 So sánh thuật tốn tìm kiếm cục với thuật tốn vét cạn 38 3.4.1 Thực nghiệm với tốn nhân ổn định có kích thước 50 39 3.4.2 Thực nghiệm với tốn nhân ổn định có kích thước 10040 3.4.3 Thực nghiệm với tốn nhân ổn định có kích thược 20042 3.5 Một số đánh giá thuật toán 44 3.6 Kết luận chương 45 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 47 Kết luận 47 Kiến nghị hướng phát triển 48 TÀI LIỆU THAM KHẢO 50 DANH MỤC CÁC BẢNG, HÌNH VẼ Trang Bảng Bảng 2.1 Danh sách "thích" nam nữ 20 Bảng 2.2 Các ghép ổn định ví dụ 26 Bảng 3.1 Các phép ghép sinh ví dụ 2.1 theo thủ tục breakmarriage 36 Bảng 3.2 Thực nghiệm cho tốn nhân ổn định với kích thước 50 39 Bảng 3.4 Thực nghiệm cho tốn nhân ổn định với kích thước 200 42 Hình Hình 2.1 Cây mơ tả ghép ổn định sinh thuật toán vét cạn 28 Hình 3.1 Đ thị biểu diễn phép ghép sinh ví dụ 2.1 dựa thủ tục breakmarriage 38 Hình 3.2 Vết tìm kiếm thuật tốn tìm kiếm cục chiều cho ví dụ 2.1[5] 38 Hình 3.3 Thời gian thực thuật toán cho liệu kích thước 50 40 Hình 3.3 Thời gian thực thuật tốn cho liệu kích thước 100 42 MỞ ĐẦU Sự cần thiết vấn đề nghiên cứu Vấn đề hôn nhân ổn định (SM) vấn đề tiếng kết hợp nam giới phụ nữ bình đẳng để thỏa mãn ổn định định Vấn đề Gale Shapley giới thiệu lần gần nhận ý cộng đ ng nghiên cứu vai trò quan trọng loạt ứng dụng phân cơng cơng việc cho cơng nhân, xếp thời khóa biểu trường đại học, tuyển sinh đại học, cho nhận ghép tạng, phân công bác sĩ thường trú cho bệnh viện ghép đôi bác sĩ thực tập bệnh viện, học sinh tiểu học đến trường trung học giao dịch thị trường Trong tốn học khoa học máy tính, tốn nhân ổn định (SM) u cầu tìm cặp ghép ổn định phần tử hai tập hợp theo thứ tự ưu tiên phần tử Một cặp ghép ánh xạ từ phần tử tập hợp tới phần tử tập hợp Một cặp ghép ổn định hai điều kiện sau không đ ng thời xảy ra: (i) Một phần tử x tập hợp thứ thích phần tử y tập hợp thứ hai phần tử ghép với x (ii) y thích x phần tử ghép với y Nói cách khác, cặp ghép ổn định không t n cặp (x, y) x y thích phần tử phần tử ghép với chúng Bài tốn nhân ổn định thường phát biểu sau: Có n người đàn ông n phụ nữ người xếp hạng tất người khác giới từ đến n theo thứ tự ưu tiên cần tìm cách tổ thức hôn nhân cho không t n hai người khác giới yêu vợ/ch ng họ Nếu khơng t n người tất hôn nhân "ổn định" thực tế cho thấy nhân có số người đàn ông phụ nữ độc thân muốn kết Mỗi người có tiêu chuẩn riêng với người mà họ muốn kết hôn Với ràng buộc vậy, việc người kết hôn với người lý tưởng điều gần Vậy câu hỏi đặt làm để việc "ghép đôi" thực cách tốt Năm 1962 David Gale Lloyd Shapley nghiên cứu đưa thuật tốn giải cho tốn ghép đơi nhiều toán tương tự thu hút nhà nghiên cứu lĩnh vực khác tốn học, kinh tế học, lý thuyết trị chơi khoa học máy tính Tuy nhiên, thuật tốn Gale - Shapley tối ưu cho phía nghĩa tìm nghiệm tối ưu cho người đàn ông cho người phụ nữ Thuật toán Gale-Shapley áp dụng cho tốn có số lượng nam nữ Trong luận văn nghiên cứu thuật tốn tìm kiếm cục để tìm kiếm phép ghép ổn định bình đẳng phép ghép cân giới tính tốn nhân ổn định Mục tiêu nghiên cứu 2.1 Mục tiêu tổng qt Nghiên cứu thuật tốn tìm kiếm cục chiều thuật tốn tìm kiếm cục hai chiều giải tốn nhân ổn định với số lượng nam nữ 2.2 Mục tiêu cụ thể Đề tài tập trung vào mục tiêu sau: i) Nghiên cứu tổng quan tốn nhân ổn định ii) Nghiên cứu thuật toán Gale-Shapley iii) Nghiên cứu thuật toán vét cạn cho tốn nhân ổn định iv) Nghiên cứu thuật tốn tìm kiếm cục cho tốn nhân ổn định v) Cài đặt thuật tốn tìm kiếm cục cho tốn nhân ổn định đưa nhận xét đề xuất Đối tượng phạm vi nghiên cứu 3.1 Đối tượng nghiên cứu (a) Nghiên cứu lý thuyết Nghiên cứu tài liệu tốn nhân ổn định cơng bố ngồi nước; kết khảo sát có tính chất đánh giá nghiên cứu trước; tài liệu lập trình để thực thi thuật tốn (b) Nghiên cứu thực nghiệm Sử dụng ngơn ngữ lập trình Matlab để cài đặt thực thi thuật toán tìm kiếm vét cạn tìm kiếm cục cho tốn nhân ổn định Đánh giá thuật toán dựa thực nghiệm 3.2 Phạm vi nghiên cứu Trong phạm vi luận văn tập trung áp dụng thuật tốn tìm kiếm cục để giải tốn nhân ổn định với số lượng nam nữ Nội dung nghiên cứu - Nghiên cứu tốn nhân ổn định với số lượng nam nữ - Nghiên cứu thuật tốn Gale-Shapley cho tốn nhân ổn định 10 - Nghiên cứu tổng quan phương pháp giải tốn nhân ổn định - Nghiên cứu thuật tốn vét cạn, thuật tốn tìm kiếm cục cho tốn nhân ổn định - Cài đặt thuật tốn vét cạn, thuật tốn tìm kiếm cục cho tốn nhân ổn định - Đánh giá hiệu thuật toán vét cạn, thuật tốn tìm kiếm cục cho tốn hôn nhân ổn định Kết cấu luận văn Luận văn g m chương với nội dung chương sau: Chương Tổng quan tốn nhân ổn định: Chương giới thiệu tốn nhân ổn định định nghĩa tiêu chuẩn ổn định tối ưu tốn Chương trình bày biến thể tốn nhân ổn định hướng tiếp cận giải tốn nhân ổn định có Chương Thuật tốn Gale - Shapley thuật tốn vét cạn cho tốn nhân ổn định: Chương trình bày thuật tốn Gale-Shapley để tìm phép ghép tối ưu cho tập nam tập nữ tốn nhân ổn định Ngồi chương trình bày thủ tục phá vỡ nhân (breakmarriage) phép ổn định để sinh ghép ổn định khác Dựa thủ tục phá vỡ hôn nhân chương giới thiệu thuật tốn vét cạn để tìm tất phép ghép ổn định tốn từ tìm phép ghép ổn định tối ưu theo tiêu chuẩn Chương Tìm kiếm cục cho tốn nhân ổn định: Chương trình bày thuật tốn tìm kiếm cục thuật tốn tìm kiếm cục chiều thuật tốn tìm kiếm cục hai chiều cho tốn ơn nhân ổn 36 Bảng 3.1 Các phép ghép sinh ví dụ 2.1 theo thủ tục breakmarriage Stt Phép ghép Nam Tạo phép ghép Stt Phép ghép Nam Tạo phép ghép M0 M1 22 M9 M14 M0 M2 23 M4 M8 M0 M3 24 M4 M9 M1 M4 25 M10 M8 M1 M5 26 M10 M15 M1 M6 27 M11 M9 M2 M5 28 M11 M15 M2 M7 29 M11 M16 M3 M6 30 M12 M16 10 M3 M7 31 M13 M17 11 M4 M8 32 M14 M17 12 M4 M9 33 M8 M13 13 M5 M4 34 M9 M13 14 M5 M10 35 M9 M14 15 M5 M11 36 M15 M13 16 M6 M9 37 M15 M18 17 M6 M11 38 M16 M14 18 M7 M11 39 M16 M18 19 M7 M12 40 M13 M17 20 M8 M13 41 M14 M17 21 M9 M13 42 M18 M17 Giả sử xác suất để chọn nghiệm ngẫu nhiên tập nghiệm láng giềng Một minh họa thuật tốn tìm kiếm cục chiều cho ví dụ 2.1 việc tìm phép ghép ổn định cân giới tính sau Khởi tạo, 37 thuật toán gán Mleft cho M0 Mright cho M17 (xem bảng 2.1 để biết hàm đánh giá phép ghép) Ở vịng lặp 1, thuật tốn tìm nghiệm tốt láng giềng Mleft g m {M1,M2,M3} di chuyển Mleft tới M1 Thuật toán tìm nghiệm tốt láng giềng Mright g m {M18,M14,M8,M13} di chuyển Mright tới M8 Ở vịng lặp 2, thuật tốn tìm nghiệm tốt láng giềng Mleft g m {M4,M5,M6) di chuyển Mleft tới M4 Thuật toán tìm nghiệm tốt láng giềng Mright g m {M4,M10} di chuyển Mright tới M4 Ở vịng lặp 3, thuật tốn tìm nghiệm tốt láng giềng Mleft g m {M9,M8} di chuyển Mleft tới M9 Thuật tốn tìm nghiệm tốt láng giềng Mright g m {M5} di chuyển Mright tới M5 Sau thuật tốn kiểm tra sm(Mleft) > sm(Mright) thuật tốn dừng trả nghiệm tốt tìm thấy theo hướng M4 Rõ ràng so với thuật tốn vét cạn, thuật tốn tìm kiếm cục tìm thấy nghiệm xác tốn Hình 3.2 mơ tả vịng lặp thuật tốn 38 Hình 3.1 Đ thị biểu diễn phép ghép sinh ví dụ 2.1 dựa thủ tục breakmarriage Hình 3.2 Vết tìm kiếm thuật tốn tìm kiếm cục chiều cho ví dụ 2.1[5] 3.4 So sánh thuật tốn tìm kiếm cục với thuật tốn vét cạn Phần chúng tơi so sánh hiệu thuật tốn tìm kiếm cục với thuật tốn vét cạn cho tốn nhân ổn định Xác suất để chọn nghiệm ngẫu nhiên tập láng giềng thuật tốn tìm kiếm cục p = 0.05 Chúng tạo ngẫu nhiên ba liệu tốn nhân ổn định với kích thước n = 50, 100 200 Mỗi liệu tạo 15 tốn 39 nhân ổn định Sau chúng tơi chạy thuật tốn tìm kiếm vét cạn, thuật tốn tìm kiếm cục chiều thuật tốn tìm kiếm cục hai chiều cho toán để so sánh hàm đánh giá thời gian thực thuật toán 3.4.1 Thực nghiệm với toán nhân ổn định có kích thước 50 Bảng 3.2 mô tả kết thực nghiệm Cột c mô tả giá trị phép ghép ổn định tối ưu bình đẳng cột d mơ tả giá trị phép ghép ổn định tối ưu cân tìm thấy thuật tốn Thuật tốn vét cạn ln tìm giá trị hàm đánh giá phép ghép ổn định tối bình đẳng phép ghép ổn định tối ưu cân Tuy nhiên, thuật tốn tìm kiếm cục dạng thuật tốn xấp xỉ tối ưu nên số trường hợp, thuật tốn tìm phép ghép xấp xỉ tối ưu liệu thử nghiệm mà giá trị hàm đánh giá tô đậm gạch chân Cho trường hợp tìm nghiệm tối ưu bình đẳng tìm nghiệm tối ưu cần bằng, thuật tốn tìm kiếm cục chiều tìm 23/30 lần thực nghiệm tìm thấy 7/30 nghiệm cục bộ, thuật tốn tìm kiếm cục hai chiều tìm 27/30 lần thực nghiệm tìm thấy 3/30 nghiệm cục Như thuật tốn tìm kiếm cục chiều tìm nghiệm xác thuật tốn tìm kiếm cục chiều Bảng 3.2 Thực nghiệm cho tốn nhân ổn định với kích thước 50 Thuật tốn vét cạn Stt Thuật tốn tìm kiếm cục chiều Thuật tốn tìm kiếm cục hai chiều c d Thời gian (giấy) c d Thời gian (giấy) c d Thời gian (giấy) 709 0.311 713 79 0.197 709 0.202 654 0.123 654 0.052 654 0.054 40 701 0.111 701 0.091 701 0.084 733 0.255 733 0.159 733 0.091 718 73 0.098 718 73 0.069 718 73 0.064 696 32 0.115 696 32 0.168 696 32 0.116 697 0.136 697 180 0.112 697 0.133 599 0.143 599 18 0.104 599 18 0.088 668 94 0.115 668 94 0.093 668 94 0.070 10 655 0.074 655 0.044 655 0.076 11 607 45 0.062 607 45 0.067 607 45 0.035 12 595 19 0.123 640 72 0.064 595 72 0.049 13 702 0.073 702 0.021 702 0.022 14 706 31 0.245 713 31 0.107 713 31 0.055 15 703 0.172 703 0.077 703 0.035 *) Những giá trị in đậm gạch chận giá trị nghiệm cục Thời gian thực thuật toán biểu diễn đ thị hình 3.3 Dễ thấy thuật tốn tìm kiếm cục chiều tìm nghiệm nhanh thuật tốn tìm vét cạn tìm nghiệm lâu Hình 3.3 Thời gian thực thuật tốn cho liệu kích thước 50 3.4.2 Thực nghiệm với tốn nhân ổn định có kích thước 100 Bảng 3.3 mơ tả kết thực nghiệm Cho trường hợp tìm nghiệm tối ưu bình đẳng tìm nghiệm tối ưu cần bằng, thuật tốn tìm kiếm 41 cục chiều tìm 10/30 lần thực nghiệm tìm thấy 20/30 nghiệm cục bộ, thuật tốn tìm kiếm cục hai chiều tìm 20/30 lần thực nghiệm tìm thấy 10/30 nghiệm cục Một lần nữa, thực nghiệm thuật tốn tìm kiếm cục chiều tìm nghiệm xác thuật tốn tìm kiếm cục chiều Bảng 3.3 Thực nghiệm cho tốn nhân ổn định với kích thước 100 Thuật tốn vét cạn Stt Thuật tốn tìm kiếm cục chiều Thuật tốn tìm kiếm cục hai chiều c d Thời gian (giấy) c d Thời gian (giấy) c d Thời gian (giấy) 2046 27 1.437 2046 27 0.571 2046 27 0.308 2011 17 1.929 2042 17 0.765 2042 17 0.453 1928 104 1.551 2095 663 0.421 1928 104 0.290 1933 52 1.690 1933 77 0.434 1933 52 0.631 1989 58 1.039 1989 236 0.563 1989 58 0.448 1967 21 0.735 1988 172 0.325 1987 21 0.284 1865 14 0.828 1901 35 0.510 1865 14 0.346 1989 33 0.758 2007 119 0.228 2007 72 0.285 1859 1.736 1859 0.687 1859 0.442 10 1901 99 0.557 1936 198 0.172 1936 99 0.125 11 1860 11 1.182 1900 32 0.574 1899 32 0.309 12 1861 20 0.892 1861 20 0.522 1861 20 0.220 13 1960 50 0.999 2473 1321 0.299 1964 50 0.284 14 1879 0.755 1879 220 0.340 1879 220 0.145 15 1912 0.869 1942 16 0.331 1912 16 0.198 *) Những giá trị in đậm gạch chận giá trị nghiệm cục 42 Thời gian thực thuật toán biễu diễn đ thị hình 3.4 Dễ thấy thuật tốn tìm kiếm cục chiều tìm nghiệm nhanh thuật tốn tìm vét cạn tìm nghiệm lâu Thời gian tìm kiếm thuật tốn tìm kiếm cục lâu gấp khoảng lần thuật toán vét cạn chiều gấp khoảng lần thuật tốn tìm kiếm cục chiều Hình 3.3 Thời gian thực thuật tốn cho liệu kích thước 100 3.4.3 Thực nghiệm với tốn nhân ổn định có kích thược 200 Bảng 3.4 mơ tả kết thực nghiệm Cho trường hợp tìm nghiệm tối ưu bình đẳng tìm nghiệm tối ưu cần bằng, thuật tốn tìm kiếm cục chiều tìm 14/30 lần thực nghiệm tìm thấy 16/30 nghiệm cục bộ, thuật tốn tìm kiếm cục hai chiều tìm 22/30 lần thực nghiệm tìm thấy 8/30 nghiệm cục Một lần nữa, thực nghiệm thuật tốn tìm kiếm cục chiều tìm nghiệm xác thuật tốn tìm kiếm cục chiều Bảng 3.4 Thực nghiệm cho tốn nhân ổn định với kích thước 200 Thuật toán vét cạn Stt c d Thời gian (giấy) Thuật tốn tìm kiếm cục chiều Thuật tốn tìm kiếm cục hai chiều Thời gian (giấy) Thời gian (giấy) c d c d 43 5252 118 5.044 5252 118 3.266 5252 118 0.966 5524 10 9.991 5593 10 2.053 5593 10 1.243 5475 17 7.277 5621 1127 2.648 5475 70 1.175 5506 10 5.347 5529 10 3.066 5506 10 1.472 5661 214 12.223 5786 214 4.293 5786 214 0.931 5241 25.300 5241 37 9.179 5241 37 1.342 5273 61 8.610 5373 61 4.238 5373 61 1.010 5698 16.165 5705 7.651 5698 2.647 5784 78 15.602 5784 78 5.229 5784 78 2.448 10 5855 239 7.315 5874 1318 2.715 5855 596 1.011 11 5450 14 14.701 5450 3010 3.238 5450 14 1.584 12 5381 12.078 5471 5.008 5381 2.788 13 5842 56 12.206 5854 272 5.712 5842 56 1.015 14 5456 10 10.100 5456 37 3.120 5456 26 2.683 15 5311 7.580 5311 4.026 5311 1.682 *) Những giá trị in đậm gạch chận giá trị nghiệm cục Thời gian thực thuật toán biễu diễn đ thị hình 3.4 Một lần nữa, thực nghiệm thuật tốn tìm kiếm cục chiều tìm nghiệm nhanh thuật tốn tìm vét cạn tìm nghiệm lâu Thời gian tìm kiếm thuật tốn tìm kiếm cục lâu gấp khoảng lần thuật toán vét cạn chiều gấp khoảng lần thuật tốn tìm kiếm cục chiều Thuật tốn tìm kiếm cục chiều tìm nghiệm lâu gấp khoảng lần thuật tốn tìm kiếm cục chiều 44 Hình 3.4 Thời gian thực thuật toán cho liệu kích thước 200 3.5 Một số đánh giá thuật tốn rong q trình cài đặt thử nghiệm thuật tốn cho tốn nhân ổn định với danh sách "thích" tạo ngẫu nhiên, chung tơi có số nhận xét sau: - Thuật tốn vét cạn ln tìm nghiệm tốn kích thước tốn lớn thuật tốn vét cạn khơng hiệu mặt thời gian Do cần phải nghiên cứu thuật tốn tìm kiếm xấp xỉ để giải tốn với kích thước lớn - Thuật tốn tìm kiếm cục chiều thực nhanh nhiều thuật toán vét cạn nghiệm xấp xỉ tối ưu - Thuật tốn tìm kiếm cục hai chiều thuật tốn thực nhanh so với thuật toán vét cạn thuật tốn tìm kiếm cục chiều Thuật tốn tìm kiếm cục hai chiều tìm nghiệm xác cao có tỷ lệ cao thuật tốn tìm kiếm cục chiều Ngay thuật tốn tìm nghiệm xấp xỉ nghiệm tìm thấy thuật tốn tìm kiếm cục chiều tốt nghiệm tìm thấy thuật tốn tìm kiếm cục chiều 45 Điều thuật tốn tìm kiếm cục chiều có khơng gian tìm kiếm lớn khơng gian tìm kiếm thuật tốn tìm kiếm cục chiều khả tìm nghiêm tốt cao thuật tốn tìm kiếm cục chiều Mặc dù khơng gian tìm kiếm thuật tốn tìm kiếm cục chiều rộng thuật tốn tìm kiếm cục nhiều thuật tốn tìm kiếm cục chiều nhanh thuật toán tìm kiếm cục chiều tìm kiếm theo hướng chia đơi khơng gian tìm kiếm tốn -Với liệu kích thước lớn, thuật tốn vét cạn khơng hiệu thời gian thuật tốn tìm kiếm cục chiều cho thấy hiệu Các thực nghiệm thuật toán cục chiều thuật tốn áp dụng để giải tốn nhân ổn định với kích thước lớn 3.6 Kết luận chương Chương trình bày thuật tốn tìm kiếm cục thuật tốn tìm kiếm cục chiều thuật tốn tìm kiếm cục hai chiều cho tốn ôn nhân ổn định Đ ng thời chương mô tả kết thực nghiệm so sánh hiệu thuật tốn vét cạn, thuật tốn tìm kiếm cục chiều thuật tốn tìm kiếm cục chiều cho tốn nhân ổn định Đưa số đánh giá hiệu qủa thuật tốn thực thi cho tốn nhân ổn định Thuật tốn vét cạn ln tìm nghiệm tốn kích thước tốn lớn thuật tốn vét cạn khơng hiệu mặt thời gian Thuật tốn tìm kiếm cục chiều thực nhanh nhiều thuật toán vét cạn nghiệm xấp xỉ tối ưu huật tốn tìm kiếm cục hai chiều thuật toán thực nhanh so với thuật toán vét cạn thuật tốn tìm kiếm cục chiều Thuật tốn tìm kiếm cục hai chiều tìm nghiệm xác cao có tỷ lệ cao thuật tốn tìm 46 kiếm cục chiều Với liệu kích thước lớn, thuật tốn vét cạn không hiệu thời gian thuật tốn tìm kiếm cục chiều cho thấy hiệu 47 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Kết luận Sau thời gian thực luận văn với nỗ lực thân giúp đỡ tận tình giảng viên hướng dẫn, luận văn thực theo đề cương phê duyệt Luận văn nghiên cứu tốn nhân ổn định với số lượng nam nữ nhau, thuật tốn GaleShapley, thuật tốn vét cạn, thuật tốn tìm kiếm cục cho tốn nhân ổn định Lựa chọn số ví dụ ứng dụng thực tế tốn nhân ổn định để tiến hành cài đặt đưa kết luận, nhận xét đề xuất luận văn nghiên cứu tiến hành cài đặt mơ thuật tốn, đưa kết thực nghiệm đánh giá Bản thân tự đánh giá đạt số kết sau: a) Về mặt lý thuyết - Hiểu tốn nhân ổn định với số lượng nam nữ - Hiểu thuật tốn Gale-Shapley cho tốn nhân ổn định với số lượng nam nữ - Biết phương pháp giải toán hôn nhân ổn định với số lượng nam nữ - Hiểu thuật toán vét cạn giải tốn nhân ổn định dựa thủ tục breakmarriage - Hiểu thuật tốn tìm kiếm cục chiều thuật toán cục hai chiều áp dụng cho tốn nhân ổn định b) Về thực nghiệm - Cài đặt thuật toán vét cạn thuật tốn tìm kiếm cục chiều thuật toán cục hai chiều cho toán nhân ổn định ngơn ngữ lập trình Matlab 48 - Biết cách tạo số liệu thực nghiệm ngẫu nhiên để đánh giá hiệu thuật toán - Biết cách so sánh hiệu thuật toán dựa liệu thực nghiệm từ đưa đánh giá chung hiệu thuật tốn cho tốn nhân ổn định Kiến nghị hướng phát triển Từ kết nghiên cứu lý thuyết thực nghiệm thu nhận kiến thức hữu ích thuật toán vét cạn thuật toán tìm kiếm cục cho tốn nhân ổn định Tuy nhiên chúng tơi nhận thấy cịn nhiều vấn đề cần phải nghiên cứu biểu diễn tốn nhân ổn định theo dạng danh sách ngắn (short-lists) áp dụng danh sách ngắn cho việc lập trình thuật tốn để nâng cao hiệu thuật tốn Ngồi cần nghiên cứu áp dụng thuật tốn tìm kiếm cục cho tốn nhân ổn định với số lượng nam nữ khác hay áp dụng cho tốn ghép cặp khác tốn phân cơng giảng viên hướng dẫn sinh viên thực đề tài, tốn xếp phịng trọ ký túc xá, Trong thời gian thực luận văn với nỗ lực thân, giúp đỡ tận tình giảng viên hướng dẫn luận văn thực theo nhiệm vụ giao thời hạn theo yêu cầu uy nhiên với thân đề tài khó khơng thể tránh khỏi khiếm khuyết mong Quý hầy Cơ giáo đ ng nghiệp góp ý để tơi tiếp tục hồn thiện luận văn tốt Để hồn thành luận văn tơi xin bày tỏ lịng biết ơn chân thành tới hầy Cơ giáo Ngành Công nghệ hông tin Viện Kỹ thuật Công nghệ rường Đại học Vinh truyền thụ kiến thức kinh nghiệm giúp đỡ tơi q trình học tập Đặc biệt xin chân thành cảm ơn tới S Hồng Hữu Việt hướng dẫn tận tình trình thực hầy 49 Cơ giáo phản biện đóng góp ý kiến quý báu để luận văn hoàn thành 50 TÀI LIỆU THAM KHẢO [1] Gale, D., Shapley, L.S.: College admissions and the stability of marriage The American Mathematical Monthly 9(1), 9-15 (1962) [2] Abraham, D.J., Irving, R.W., Manlove, D.F.: The student-project allocation problem In: Proceedings of the 14th International Symposium, pp 474-484 Kyoto, Japan (2003) [3] Irving, R.W.: An ecient algorithm for the \stable roommates" problem Journal of Algorithms 6(1), 577-595 (1985) [4] Nakamura, M., Onaga, K., Kyan, S., Silva, M.: Genetic algorithm for sexfair stable marriage problem In: Circuits and Systems, 1995 ISCAS '95., 1995 IEEE International Symposium on, pp 509{512 Seattle, WA (1995) [5] Viet, H.H., Trang, L.H., Lee, S.G., Chung, T.C.: A bidirectional local search for the stable marriage problem In: Proceedings of the 2016 International Conference on Advanced Computing and Applications (ACOMP), pp 18-24 Can Tho City, VietNam (2016) [6] McVitie, D.G., Wilson, L.B.: The stable marriage problem Communication of ACM 14(7), 486-490 (1971) [7] Russel, S., Norvig, P.: Articial Intelligence A Modern Approach Pearson Education, 3nd Ed (2010) [8] Viet, H.H., Trang, L.H., Lee, S.G., Chung, T.C.: An empirical local search for the stable marriage problem In: Proceedings of the 14th Pacic Rim International Conference on Arti cial Intelligence - PRICAI 2016: Trends in Articial Intelligence, pp 556-564 Phuket, Thailand (2016) ... TỐN HƠN NHÂN ỔN ĐỊNH 29 3.1 Thuật tốn tìm kiếm cục 29 3.2 Thuật toán tìm kiếm cục chiều cho tốn nhân ổn định3 0 3.3 Thuật tốn tìm kiếm cục hai chiều cho tốn nhân ổn định3 2... vào mục tiêu sau: i) Nghiên cứu tổng quan tốn nhân ổn định ii) Nghiên cứu thuật tốn Gale-Shapley 9 iii) Nghiên cứu thuật toán vét cạn cho tốn nhân ổn định iv) Nghiên cứu thuật tốn tìm kiếm cục. .. tốn nhân ổn định - Nghiên cứu thuật tốn vét cạn, thuật tốn tìm kiếm cục cho tốn nhân ổn định - Cài đặt thuật tốn vét cạn, thuật tốn tìm kiếm cục cho tốn nhân ổn định - Đánh giá hiệu thuật toán