Nghiên cứu một số biến thể của bài toán hôn nhân ổn định theo tiếp cận heuristic

Nội dung tài liệu:

Luận án này tập trung nghiên cứu các thuật toán heuristic nhằm tìm kiếm các phép ghép ổn định với kích thước tối đa cho bài toán hôn nhân ổn định (Stable Marriage Problem – SMP) và các biến thể mở rộng của nó. Các biến thể được đề cập bao gồm bài toán hôn nhân ổn định với danh sách xếp hạng ngang bằng (SMT), bài toán hôn nhân ổn định với danh sách không đầy đủ (SMI), và bài toán hôn nhân ổn định với danh sách xếp hạng ngang bằng và không đầy đủ (SMTI). Nghiên cứu cũng xem xét các bài toán mở rộng như bài toán phân bổ sinh viên thực tập tại các bệnh viện (HRT) và bài toán phân bổ đề tài cho sinh viên (SPA). Luận án đề xuất các thuật toán heuristic mới để giải quyết hiệu quả các bài toán này, so sánh hiệu năng với các phương pháp hiện có, và đánh giá kết quả thực nghiệm.

Mục lục chi tiết:

• Lời cam đoan
• Lời cảm ơn
• Mục lục
• Danh mục các ký hiệu, các chữ viết tắt
• Danh mục các hình vẽ
• Danh mục các bảng biểu
• Chương 1: Tổng quan về bài toán hôn nhân ổn định
• Chương 2: Đề xuất thuật toán giải bài toán MAX-SMTI
• Chương 3: Đề xuất thuật toán giải bài toán MAX-HRT
• Chương 4: Đề xuất thuật toán giải bài toán MAX-SPA
• Kết luận
• Danh mục các công trình đã công bố của nghiên cứu sinh và cộng sự
• Tài liệu tham khảo
• Phụ lục A